355. 设计推特

🟠   🔖  设计 哈希表 链表 堆（优先队列）  🔗 力扣 LeetCode

题目

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.

Implement the Twitter class:

• Twitter() Initializes your twitter object.
• void postTweet(int userId, int tweetId) Composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId.
• List<Integer> getNewsFeed(int userId) Retrieves 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 themself. Tweets must be ordered from most recent to least recent.
• void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId.
• void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.

Example 1:

Input

["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]

[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]

Output

[null, null, [5], null, null, [6, 5], null, [5]]

Explanation

Twitter twitter = new Twitter();

twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5).

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

twitter.follow(1, 2); // User 1 follows user 2.

twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6).

twitter.getNewsFeed(1); // 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.unfollow(1, 2); // User 1 unfollows user 2.

twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5], since user 1 is no longer following user 2.

Constraints:

• 1 <= userId, followerId, followeeId <= 500
• 0 <= tweetId <= 10^4
• All the tweets have unique IDs.
• At most 3 * 10^4 calls will be made to postTweet, getNewsFeed, follow, and unfollow.

题目大意

设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近 10 条推文。

实现 Twitter 类：

• Twitter() 初始化简易版推特对象
• void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId 。
• List<Integer> getNewsFeed(int userId) 检索当前用户新闻推送中最近 10 条推文的 ID 。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须 按照时间顺序由最近到最远排序 。
• void follow(int followerId, int followeeId) ID 为 followerId 的用户开始关注 ID 为 followeeId 的用户。
• void unfollow(int followerId, int followeeId) ID 为 followerId 的用户不再关注 ID 为 followeeId 的用户。

解题思路

可以使用哈希表和优先队列（或者堆）来存储用户的推文和关注关系。

1. 可以使用一个哈希表来存储用户的推文。哈希表的键是用户的 ID，值是一个优先队列（或者堆），用于按照时间戳存储用户的推文。每个推文可以包含推文的 ID 和时间戳。

2. 当用户发布推文时，将推文添加到相应用户的优先队列中。为了保证推文按照时间顺序排序，可以使用时间戳作为排序的依据。

3. 获取新闻推送时，需要获取当前用户关注的人的推文，并将这些推文进行合并。为了方便合并，我们可以使用一个大顶堆，每次从堆中取出最大的时间戳的推文，同时将该推文所属用户的其他推文加入堆中。

4. 用户关注和取消关注可以通过维护关注关系的哈希表来实现。哈希表的键是关注者的 ID，值是一个集合，包含该关注者关注的人的 ID。

代码

class Twitter {
	constructor() {
		this.tweets = new Map(); // 用户推文的哈希表
		this.following = new Map(); // 关注关系的哈希表
		this.timestamp = 0; // 时间戳，用于推文的排序
	}

	postTweet(userId, tweetId) {
		if (!this.tweets.has(userId)) {
			this.tweets.set(userId, []);
		}
		this.tweets.get(userId).push({ tweetId, timestamp: this.timestamp++ });
	}

	getNewsFeed(userId) {
		const heap = new MaxHeap();

		// 加入自己的推文
		if (this.tweets.has(userId)) {
			this.tweets.get(userId).forEach((tweet) => heap.insert(tweet));
		}

		// 加入关注者的推文
		if (this.following.has(userId)) {
			this.following.get(userId).forEach((followeeId) => {
				if (this.tweets.has(followeeId)) {
					this.tweets.get(followeeId).forEach((tweet) => heap.insert(tweet));
				}
			});
		}

		const result = [];
		while (!heap.isEmpty() && result.length < 10) {
			const tweet = heap.extractMax();
			result.push(tweet.tweetId);
		}

		return result;
	}

	follow(followerId, followeeId) {
		if (!this.following.has(followerId)) {
			this.following.set(followerId, new Set());
		}
		this.following.get(followerId).add(followeeId);
	}

	unfollow(followerId, followeeId) {
		if (this.following.has(followerId)) {
			this.following.get(followerId).delete(followeeId);
		}
	}
}

class MaxHeap {
	constructor() {
		this.heap = [];
	}

	insert(value) {
		this.heap.push(value);
		this.heapifyUp();
	}

	extractMax() {
		if (this.isEmpty()) {
			return null;
		}

		const max = this.heap[0];
		const last = this.heap.pop();

		if (this.heap.length > 0) {
			this.heap[0] = last;
			this.heapifyDown();
		}

		return max;
	}

	isEmpty() {
		return this.heap.length === 0;
	}

	heapifyUp() {
		let cur = this.heap.length - 1;

		while (cur > 0) {
			const parent = Math.floor((cur - 1) / 2);
			if (this.heap[cur].timestamp > this.heap[parent].timestamp) {
				[this.heap[cur], this.heap[parent]] = [
					this.heap[parent],
					this.heap[cur]
				];
				cur = parent;
			} else {
				break;
			}
		}
	}

	heapifyDown() {
		let cur = 0;

		while (true) {
			const leftChild = 2 * cur + 1;
			const rightChild = 2 * cur + 2;
			let next = null;

			if (
				leftChild < this.heap.length &&
				this.heap[leftChild].timestamp > this.heap[cur].timestamp
			) {
				next = leftChild;
			}

			if (
				rightChild < this.heap.length &&
				this.heap[rightChild].timestamp > this.heap[cur].timestamp
			) {
				next =
					this.heap[rightChild].timestamp > this.heap[leftChild].timestamp
						? rightChild
						: leftChild;
			}

			if (
				next !== null &&
				this.heap[cur].timestamp < this.heap[next].timestamp
			) {
				[this.heap[cur], this.heap[next]] = [this.heap[next], this.heap[cur]];
				cur = next;
			} else {
				break;
			}
		}
	}
}

相关题目

题号	标题	题解	标签	难度
1500	设计文件分享系统 🔒		设计 哈希表 数据流 2+