heap

355. Design Twitter

Difficulty: Medium

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user's news feed. Your design should support the following methods:

postTweet(userId, tweetId): Compose a new tweet.

getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.

follow(followerId, followeeId): Follower follows a followee.

unfollow(followerId, followeeId): Follower unfollows a followee.

Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).

twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].

twitter.getNewsFeed(1);

// User 1 follows user 2.

twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).

twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].

// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.

twitter.getNewsFeed(1);

// User 1 unfollows user 2.

twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],

// since user 1 is no longer following user 2.

twitter.getNewsFeed(1);

Hide Company Tags Amazon Twitter

思路：设计数据结构很关键。这里用了很多python 的库，值得学习。

class Twitter(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.timer = itertools.count(step=-1)
        self.tweets = collections.defaultdict(collections.deque)
        self.followee = collections.defaultdict(set)

    def postTweet(self, userId, tweetId):
        """
        Compose a new tweet.
        :type userId: int
        :type tweetId: int
        :rtype: void
        """
        self.tweets[userId].appendleft((next(self.timer), tweetId))

    def getNewsFeed(self, userId):
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        :type userId: int
        :rtype: List[int]
        """
        tweet = heapq.merge(*(self.tweets[u] for u in self.followee[userId] | {userId}))
        return [t for _, t in itertools.islice(tweet, 10)]


    def follow(self, followerId, followeeId):
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        :type followerId: int
        :type followeeId: int
        :rtype: void
        """
        self.followee[followerId].add(followeeId)

    def unfollow(self, followerId, followeeId):
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        :type followerId: int
        :type followeeId: int
        :rtype: void
        """
        self.followee[followerId].discard(followeeId)


# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)

451. Sort Characters By Frequency

Difficulty: Medium

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input: "tree"

Output: "eert"

Explanation:

'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input: "cccaaa"

Output: "cccaaa"

Explanation:

Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.

Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: "Aabb"

Output: "bbAa"

Explanation:

"bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters.

Hide Company Tags Amazon Google

思路：看着题长，其实不难，就是统计出每个字母个数，把（个数，字母）tuple放到heapq里，每次弹出来一个组成新的字符串，但最后记得要reverse一下。

class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        store = {}
        res = ''
        for i in s:
            store[i] = store.get(i, 0) + 1
        heap = []
        for k, v in store.items():
            heapq.heappush(heap, (v, k))
        while heap:
            cur = heapq.heappop(heap)
            res += cur[1] * cur[0]
        return res[::-1]

373. Find K Pairs with Smallest Sums

Difficulty: Medium

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

Example 1:

Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3

Return: [1,2],[1,4],[1,6]

The first 3 pairs are returned from the sequence:

[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

Given nums1 = [1,1,2], nums2 = [1,2,3], k = 2

Return: [1,1],[1,1]

The first 2 pairs are returned from the sequence:

[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

Given nums1 = [1,2], nums2 = [3], k = 3

Return: [1,3],[2,3]

All possible pairs are returned from the sequence: [1,3],[2,3]

思路：像这种找第几小的一般都是用heapq。先把array1的第一个数和array2中每个数分别相加的和放到heapq里，之后每次pop一个，再把array1第i+1个和array2 pop出来的坐标的值相加，push进去。因为两个array都是排序的，所以数的和也是递增的。

class Solution(object):
    def kSmallestPairs(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[List[int]]
        """
        if not nums1 or not nums2:
            return []
        heap = [(nums1[0]+nums2[j], 0, j) for j in range(len(nums2))]
        heapq.heapify(heap)
        ans = []
        while k > 0 and heap:
           val, i, j = heapq.heappop(heap)
           ans.append([nums1[i], nums2[j]])
           if i + 1 < len(nums1):
               heapq.heappush(heap, (nums1[i + 1] + nums2[j], i+1, j))
           k -= 1
        return ans