Tag Archives: 优先队列

LeetCode Design Twitter

LeetCode Design Twitter

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:

  1. postTweet(userId, tweetId): Compose a new tweet.
  2. 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.
  3. follow(followerId, followeeId): Follower follows a followee.
  4. 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);

设计一个Twitter系统,实现三个接口,postTweet发文,follow某人,unfollow某人,getNewsFeed从自己以及follow的人中取出最近发表的三篇推文,按时间从近到远排序。比较麻烦的是getNewsFeed函数的实现。
先来个暴力版本,用unordered_map<int, unordered_set<int>>保存某个人follow的所有人,这样follow和unfollow的操作都可以在O(1)实现。
用vector<Tweet>保存所有推文,而且是最新postTweet的推文都push_back到末尾,所以该容器保存了全局从远到近的所有推文。那么getNewsFeed时,直接从容器末尾往前遍历所有推文,判断该推文是否是自己或者自己follow的用户发表的,如果是,则收集起来,直到收集到10篇推文。
思路和实现都非常简单,代码如下:

class Twitter {
private:
	struct Tweet {
		int userId;
		int tweetId;
		Tweet(int u, int t) :userId(u), tweetId(t) {};
	};
	vector<Tweet> Tweets;
	unordered_map<int, unordered_set<int>> following;
public:
	/** Initialize your data structure here. */
	Twitter() {
	}
	/** Compose a new tweet. */
	void postTweet(int userId, int tweetId) {
		Tweets.push_back({ userId,tweetId });
	}
	/** 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. */
	vector<int> getNewsFeed(int userId) {
		vector<int> ans;
		for (int i = Tweets.size() - 1; i >= 0; --i) {
			int &uid = Tweets[i].userId;
			if (uid == userId || following[userId].find(uid) != following[userId].end()) {
				ans.push_back(Tweets[i].tweetId);
				if (ans.size() == 10)break;
			}
		}
		return ans;
	}
	/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
	void follow(int followerId, int followeeId) {
		following[followerId].insert(followeeId);
	}
	/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
	void unfollow(int followerId, int followeeId) {
		following[followerId].erase(followeeId);
	}
};

本代码提交AC,用时143MS。
上面的版本比较慢,主要是每次getNewsFeed时都要遍历全局所有的推文。讨论区有一种做法是把每个人发表的推文也保存到一个unordered_map<int, vector<Tweet>>中,那么在getNewsFeed时,只需要拿出自己或自己follow的用户发表的推文,放到一个优先队列中,优先队列自动按时间先后顺序排序了,从优先队列中取出10条推文即可。
为了按时间排序,需要一个全局时间戳,并且重载优先队列的比较运算符。
代码如下:

class Twitter {
private:
	int timestamp;
	struct Tweet {
		int tweetId;
		int timestamp;
		Tweet(int tid, int ts) :tweetId(tid), timestamp(ts) {};
		bool operator<(const Tweet& t)const {
			return timestamp < t.timestamp;
		}
	};
	unordered_map<int, vector<Tweet>> Tweets;
	unordered_map<int, unordered_set<int>> following;
public:
	/** Initialize your data structure here. */
	Twitter() :timestamp(0) {
	}
	/** Compose a new tweet. */
	void postTweet(int userId, int tweetId) {
		Tweets[userId].push_back({ tweetId,timestamp++ });
	}
	/** 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. */
	vector<int> getNewsFeed(int userId) {
		priority_queue<Tweet> pq;
		for (const auto& uid : following[userId]) {
			for (const auto& t : Tweets[uid]) {
				pq.push(t);
			}
		}
		for (const auto& t : Tweets[userId]) {
			pq.push(t);
		}
		vector<int> ans;
		while (!pq.empty() && ans.size() < 10) {
			ans.push_back(pq.top().tweetId);
			pq.pop();
		}
		return ans;
	}
	/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
	void follow(int followerId, int followeeId) {
		if (followerId != followeeId)following[followerId].insert(followeeId); // map中不考虑自己follow自己,因为getNewsFeed单独考虑了
	}
	/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
	void unfollow(int followerId, int followeeId) {
		following[followerId].erase(followeeId);
	}
};

本代码提交AC,用时33MS,快了好几倍!

LeetCode Smallest Range

LeetCode Smallest Range
You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.
We define the range [a,b] is smaller than range if b-a < d-c or a < c if b-a == d-c.
Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:

  1. The given list may contain duplicates, so ascending order means >= here.
  2. 1 <= k <= 3500
  3. -105 <= value of elements <= 105.
  4. For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.

给定k个升序数组,求一个整数区间,该区间能至少包括所有数组的一个元素,且该区间最小。最小的定义是区间长度最小,如果区间长度相同,则区间起始点小则小。
参考Find smallest range containing elements from k lists这篇博客,突然发现GeeksforGeeks网站上的题比Leetcode上的多好多,而且都有详细题解和代码,好棒。
要求区间最小,则区间只包括每个数组的一个元素最好,所以我们要找k个数组中的k个数,使得这k个数的最大值和最小值的差最小,那么这个区间的两个端点就是这个最大值和最小值。
所以我们对k个数组维护k个指针,初始时都指向每个数组的首元素,然后找到这k个数的最大值和最小值,得到一个区间及其长度。然后我们不断循环:向前移动k个指针中的最小者,在新的k个数中求最大值和最小值及其区间长度。直到某个数组遍历结束,则返回得到的最小区间。
以样例为例。

  1. i,j,k分别指向三个数组的开头,即i=j=k=0,相当于在[4,0,5]中找最大值和最小值,构成区间[0,5],长度为5。
  2. 最小值为j所在数组,所以++j,在新的数组[4,9,5]中找最大值和最小值,构成区间[4,9],长度为5。
  3. 最小值为i所在数组,所以++i,在新的数组[10,9,5]中找最大值和最小值,构成区间[5,10],长度为5。
  4. ++k,新数组[10,9,18],区间[9,18],长度为9。
  5. ++j,新数组[10,12,18],区间[10,18],长度为8。
  6. ++i,新数组[15,12,18],区间[12,18],长度为6。
  7. ++j,新数组[15,20,18],区间[15,20],长度为5。
  8. ++i,新数组[24,20,18],区间[18,24],长度为6。
  9. ++k,新数组[24,20,22],区间[20,24],长度为4。
  10. ++j,第二个数组遍历完毕,结束,遍历过程中,得到的长度最短的区间是[20,24]。

完整代码如下:

class Solution {
public:
	vector<int> smallestRange(vector<vector<int>>& nums) {
		int ansmin = 0, ansmax = 0, ansrange = INT_MAX, k = nums.size();
		vector<int> ptr(k, 0);
		while (true) {
			bool done = false;
			int curmin = INT_MAX, curmax = INT_MIN, minid = 0;
			for (int i = 0; i < k; ++i) {
				if (ptr[i] >= nums[i].size()) {
					done = true;
					break;
				}
				if (nums[i][ptr[i]] < curmin) {
					curmin = nums[i][ptr[i]];
					minid = i;
				}
				if (nums[i][ptr[i]] > curmax) {
					curmax = nums[i][ptr[i]];
				}
			}
			if (done)break;
			if (curmax - curmin < ansrange) {
				ansrange = curmax - curmin;
				ansmin = curmin;
				ansmax = curmax;
			}
			++ptr[minid];
		}
		return{ ansmin,ansmax };
	}
};

本代码提交AC,用时1016MS。
因为每一轮都需要从k个数组中找最大值和最小值,线性查找的复杂度为O(k)。最坏情况下,需要遍历k个数组的每个元素,假设k个数组所有元素个数为n,则总的时间复杂度为O(nk)。
求k个数组的最大值和最小值的过程,可以用大小为k的优先队列(最小堆)来优化,复杂度可以降为O(nlgk)。代码如下:

class Solution {
private:
	struct Node {
		int value;
		int idx;
		int nxt;
		Node(int v, int i, int n) :value(v), idx(i), nxt(n) {};
		bool operator<(const Node& nd) const {
			return value > nd.value;
		}
		bool operator>(const Node& nd) const {
			return value < nd.value;
		}
	};
public:
	vector<int> smallestRange(vector<vector<int>>& nums) {
		int ansmin = INT_MAX, ansmax = INT_MIN, ansrange = INT_MAX, k = nums.size();
		priority_queue<Node> pq;
		for (int i = 0; i < k; ++i) {
			pq.push(Node(nums[i][0], i, 1));
			if (nums[i][0] < ansmin) {
				ansmin = nums[i][0];
			}
			ansmax = max(ansmax, nums[i][0]);
		}
		int curmax = ansmax;
		while (true) {
			int curmin = pq.top().value;
			int minidx = pq.top().idx;
			int minnxt = pq.top().nxt;
			pq.pop();
			if (curmax - curmin < ansrange) {
				ansrange = curmax - curmin;
				ansmin = curmin;
				ansmax = curmax;
			}
			if (minnxt < nums[minidx].size()) {
				curmax = max(curmax, nums[minidx][minnxt]);
				pq.push(Node(nums[minidx][minnxt], minidx, minnxt + 1));
			}
			else break;
		}
		return{ ansmin,ansmax };
	}
};

本代码提交AC,用时56MS。
 

LeetCode Course Schedule III

LeetCode Course Schedule III
There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.
Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.
Example:

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation:
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Note:

  1. The integer 1 <= d, t, n <= 10,000.
  2. You can't take two courses simultaneously.

给定一系列课程,每门课有持续时间以及该课程关闭时间。从0时刻开始,问最多能完成多少门课程。注意不能同时上多门课程。
使用贪心的思路, 首先根据经验,越早结束的课程,越早选修并结束该课程越好,因为这样可以留出更多的时间选修其他课程。所以我们首先对所有课程按关闭时间从小到大排序,每次我们贪心的选择最早关闭的课程。
如果now+duration<=closed,即当前时间加该课程的持续时间不超过课程的关闭时间,则贪心选修该课程,并且把该课程的持续时间插入到一个优先队列中(最大堆)。
如果不能选修该课程,且优先队列中堆顶的持续时间比当前课程还大,则可以把堆顶课程删掉,换成该门课程,这样该门课程肯定可以选修并完成,同时使得新的now比之前的now要小,更有利于选修更多的课程。
举个例子,假设已经按关闭时间排序了[3,8],[7,10],[5,14],[8,17],now=0。

  1. 选修第一门课程,now=3<8,优先队列堆顶为3
  2. 选修第二门课程,now=3+7=10<=10,优先队列堆顶为7
  3. 选修第三门课程,now=10+5=15>14,失败;发现堆顶课程的持续时间是7,大于当前课程的持续时间5,所以可以把堆顶课程换成该门课程,则新的now=10-7+5=8,堆顶为5。因为该门课程的持续时间比堆顶短,且关闭时间已排序,所以大于堆顶的关闭时间,所以把堆顶课程换成该课程,该课程肯定能过完成。且新的now=8比先前的now=10要小,使得可以完成第四门课程。
  4. 选修第四门课,now=8+8=16<17,优先队列为8。

完整代码如下:

class Solution {
public:
	int scheduleCourse(vector<vector<int>>& courses) {
		auto cmp = [](vector<int>& c1, vector<int>& c2) {return c1[1] < c2[1]; };
		sort(courses.begin(), courses.end(), cmp);
		int now = 0, ans = 0;
		priority_queue<int> pq;
		for (const auto& c : courses) {
			if (now + c[0] <= c[1]) {
				++ans;
				now += c[0];
				pq.push(c[0]);
			}
			else if (!pq.empty() && c[0] < pq.top()) {
				now = now - pq.top() + c[0];
				pq.pop();
				pq.push(c[0]);
			}
		}
		return ans;
	}
};

本代码提交AC,用时162MS。

LeetCode Task Scheduler

LeetCode Task Scheduler
Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.
Example 1:

Input: tasks = ['A','A','A','B','B','B'], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

  1. The number of tasks is in the range [1, 10000].

CPU需要处理一系列任务,限制条件是两个相同的任务被处理的时间至少需要间隔n时刻,问CPU最少需要多长时间能处理完所有任务。
比赛没做出来,参考讨论区
根据题意,两个任务被处理至少需要间隔n时刻,所以我们可以认为CPU处理一批任务的循环周期是n+1,比如0时刻处理了任务'A',则至少要到n+1时刻才能再次处理任务'A',中间间隔了n时刻。
假设数量最多的任务的数量是k,则我们至少需要k个周期才能把这个任务处理完。为了让CPU处理的空闲时间更少,我们在一个周期内尽量让CPU处理的任务更丰富。所以想象一下,我们有k个桶,相当于k个周期,每个周期,我们把频率最高的任务拿出来,分发到这最多k个桶中。如果所有不同任务都分发完了还没有填满一个桶,则说明该桶内(周期内)CPU需要空闲等待。
比如样例中,最高频的任务是A和B,都是3,所以我们至少需要3个桶。每个桶的容量是n+1=3,相当于相同任务的距离是3。每次我们把A和B扔到不同的桶中,前两个桶各有一个空闲等待,第三个桶因为结束了,所以不需等待。
因为每次都需要取出最高频的任务去分发,所以用一个优先队列来实时更新频率排名。
完整代码如下:

class Solution {
public:
	int leastInterval(vector<char>& tasks, int n) {
		map<char, int> count;
		for (const auto& c : tasks)++count;
		priority_queue<pair<int, char>> pq;
		for (const auto& p : count)pq.push({ p.second,p.first });
		int cycle = n + 1, time = 0;
		while (!pq.empty()) {
			vector<pair<int, char>> tmp;
			int tsk = 0;
			for (int i = 0; i < cycle; ++i) {
				if (!pq.empty()) {
					tmp.push_back(pq.top());
					pq.pop();
					++tsk;
				}
			}
			for (auto& t : tmp) {
				if (--t.first) {
					pq.push(t);
				}
			}
			time += pq.empty() ? tsk : cycle;
		}
		return time;
	}
};

本代码提交AC,用时95MS。

LeetCode Find K Pairs with Smallest Sums

LeetCode Find K Pairs with Smallest Sums
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]

给定两个从小到大排列的数组,要求选出k个数对(u_i,v_i),其中u_i来自第一个数组nums1,v_i来自第二个数组v_i,使得这k个数对的和最小。
要使得k各数对的和最小,那么这k个数对本身肯定是前k个最小的。遇到要选前k个最小或者最大的问题,一般都用优先队列(堆)来做,比如维护一个大小为k的大顶堆,当堆中元素大于k时,弹出堆顶的最大的元素,也就是堆中维护的一直是当前最小的前k个元素。当所有元素都遍历完时,返回堆中所有元素即可。
优先队列采用STL中的priority_queue,需要自定义比较运算符。
完整代码如下:

class Solution {
private:
	struct P {
		int x, y;
		P(int x_, int y_) :x(x_), y(y_) {};
		bool operator<(const P& p) const{
			return (this->x + this->y) < (p.x + p.y);
		}
		bool operator>(const P& p) const {
			return (this->x + this->y) > (p.x + p.y);
		}
	};
public:
	vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
		priority_queue<P> pq; // 大顶堆
		for (int i = 0; i < nums1.size(); ++i) {
			for (int j = 0; j < nums2.size(); ++j) {
				P p(nums1[i], nums2[j]);
				pq.push(p);
				if (pq.size() > k)pq.pop(); // 弹出最大元素
			}
		}
		vector<pair<int, int>> ans;
		while (!pq.empty()) { // 保留的都是最小元素
			ans.push_back(pair<int, int>(pq.top().x, pq.top().y));
			pq.pop();
		}
		return ans;
	}
};

本代码提交AC,用时99MS。