0355. 设计推特【中等】

1. 📝 题目描述
2. 🎯 s.1 - 模拟

1. 📝 题目描述

leetcode

设计一个简化版的推特(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 的用户。

示例：

输入：["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] [[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
输出：[null, null, [5], null, null, [6, 5], null, [5]]
解释

txt

Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5)
twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文
twitter.follow(1, 2);    // 用户 1 关注了用户 2
twitter.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6)
twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5]。推文 id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的
twitter.unfollow(1, 2);  // 用户 1 取消关注了用户 2
twitter.getNewsFeed(1);  // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2

提示：

1 <= userId, followerId, followeeId <= 500
0 <= tweetId <= 10^4
所有推特的 ID 都互不相同
postTweet、getNewsFeed、follow 和 unfollow 方法最多调用 3 * 10^4 次
用户不能关注自己

2. 🎯 s.1 - 模拟

cjspy

// 简化实现：使用数组存储推文和关注关系
#define MAX_TWEETS 10000
#define MAX_FOLLOWS 1000

typedef struct {
    int users[MAX_TWEETS];
    int tweets[MAX_TWEETS];
    int tweetCount;
    int followers[MAX_FOLLOWS];
    int followees[MAX_FOLLOWS];
    int followCount;
} Twitter;

Twitter* twitterCreate() {
    Twitter* obj = (Twitter*)calloc(1, sizeof(Twitter));
    return obj;
}

void twitterPostTweet(Twitter* obj, int userId, int tweetId) {
    obj->users[obj->tweetCount] = userId;
    obj->tweets[obj->tweetCount] = tweetId;
    obj->tweetCount++;
}

int* twitterGetNewsFeed(Twitter* obj, int userId, int* returnSize) {
    int* res = (int*)malloc(sizeof(int) * 10);
    *returnSize = 0;
    for (int i = obj->tweetCount - 1; i >= 0 && *returnSize < 10; i--) {
        if (obj->users[i] == userId) {
            res[(*returnSize)++] = obj->tweets[i];
            continue;
        }
        for (int j = 0; j < obj->followCount; j++) {
            if (obj->followers[j] == userId && obj->followees[j] == obj->users[i]) {
                res[(*returnSize)++] = obj->tweets[i];
                break;
            }
        }
    }
    return res;
}

void twitterFollow(Twitter* obj, int followerId, int followeeId) {
    for (int i = 0; i < obj->followCount; i++) {
        if (obj->followers[i] == followerId && obj->followees[i] == followeeId) return;
    }
    obj->followers[obj->followCount] = followerId;
    obj->followees[obj->followCount] = followeeId;
    obj->followCount++;
}

void twitterUnfollow(Twitter* obj, int followerId, int followeeId) {
    for (int i = 0; i < obj->followCount; i++) {
        if (obj->followers[i] == followerId && obj->followees[i] == followeeId) {
            obj->followers[i] = obj->followers[obj->followCount - 1];
            obj->followees[i] = obj->followees[obj->followCount - 1];
            obj->followCount--;
            return;
        }
    }
}

void twitterFree(Twitter* obj) { free(obj); }

var Twitter = function () {
  this.tweets = [] // [userId, tweetId, time]
  this.follows = new Map() // userId -> Set of followeeIds
  this.time = 0
}

/**
 * @param {number} userId
 * @param {number} tweetId
 * @return {void}
 */
Twitter.prototype.postTweet = function (userId, tweetId) {
  this.tweets.push([userId, tweetId, this.time++])
}

/**
 * @param {number} userId
 * @return {number[]}
 */
Twitter.prototype.getNewsFeed = function (userId) {
  const followees = this.follows.get(userId) || new Set()
  const res = []
  for (let i = this.tweets.length - 1; i >= 0 && res.length < 10; i--) {
    if (this.tweets[i][0] === userId || followees.has(this.tweets[i][0])) {
      res.push(this.tweets[i][1])
    }
  }
  return res
}

/**
 * @param {number} followerId
 * @param {number} followeeId
 * @return {void}
 */
Twitter.prototype.follow = function (followerId, followeeId) {
  if (!this.follows.has(followerId)) this.follows.set(followerId, new Set())
  this.follows.get(followerId).add(followeeId)
}

/**
 * @param {number} followerId
 * @param {number} followeeId
 * @return {void}
 */
Twitter.prototype.unfollow = function (followerId, followeeId) {
  if (this.follows.has(followerId))
    this.follows.get(followerId).delete(followeeId)
}

class Twitter:
    def __init__(self):
        self.tweets = []  # (time, userId, tweetId)
        self.follows = defaultdict(set)
        self.time = 0

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets.append((self.time, userId, tweetId))
        self.time += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        followees = self.follows[userId]
        res = []
        for i in range(len(self.tweets) - 1, -1, -1):
            if len(res) >= 10:
                break
            if self.tweets[i][1] == userId or self.tweets[i][1] in followees:
                res.append(self.tweets[i][2])
        return res

    def follow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].discard(followeeId)

时间复杂度：postTweet/follow/unfollow 为 $O (1)$ ，getNewsFeed 为 $O (T)$ 其中 $T$ 是总推文数
空间复杂度： $O (T + F)$ ，其中 $F$ 是关注关系数

算法思路：

用全局时间戳记录推文发布顺序
getNewsFeed 时从最新推文往回扫描，收集自己和关注人的推文，至多返回 10 条

⏰0355. 设计推特【中等】

0355. 设计推特【中等】 ​

1. 📝 题目描述 ​

2. 🎯 s.1 - 模拟 ​

0355. 设计推特【中等】

1. 📝 题目描述

2. 🎯 s.1 - 模拟