Processing math: 100%

算法leetcode

【设计难题】力扣355-设计推特

字数统计: 1.5k字   |   阅读时长: 5分
115
, ,

摘要: 设计推特。链表+哈希表

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文看一个设计题。从社交产品中抽象出的一些功能，整体的算法框架是链表和哈希表。

$1 题目

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

实现 Twitter 类：

  • Twitter() 初始化简易版推特对象
  • void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId 。
  • List 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
2
3
4
1 <= userId, followerId, followeeId <= 500
0 <= tweetId <= 1e4
所有推特的 ID 都互不相同
postTweet、getNewsFeed、follow 和 unfollow 方法最多调用 3e4 次

示例：
输入
[“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]]
解释
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

$2 题解

算法：链表+哈希映射

要实现 4 个功能。关注，取关，检索最近的十条推文，发推文。所有的动作都围绕着用户展开，首先用一个 HashMap(C++ 中为 unordered_map) 把用户 id 和需要的信息存起来。在做动作时，首先通过用户 id，O(1) 地取到用户相关的信息，然后执行动作。下面分析需求的动作。

发推文

需要存用户 id 对应的“我发过的推文”。发推文的动作就是首先在哈希表中找到用户 id ，然后取到对应的推文列表, 然后将推文 id 插入进去。这里需要一个数据结构用作推文列表。推文但是按顺序插入的，没有删除，修改，查找，因此用线性结构很合适，链表(c++ 中为 list)，数组(c++ 中为 vector) 都可以，若使用 STL 的 list 和 vector，不用考虑扩容的问题。

关注和取关

需要保存用户 id 对应的“我关注的人”。首先在哈希表中找到用户 id ，然后取到对应的“我关注的人”，对于关注，就是将关注对象的用户 id 插入，对于取关，就是将关注对象的用户 id 删除，这里需要一个数据结构保存我关注的人的集合。关注对象是不带顺序插入的，需要支持查找和删除，因此用哈希集合 HashSet(C++ 中为 unordered_set) 最合适

检索最近的十条推文

首先在哈希表中找到用户 id ，取到所有的关注对象的用户 id，然后取到这些关注对象的推文列表，再加上自己的推文列表，构成了候选列表集。目标是在这若干个候选列表集合中选排在前面的 10 个。对应某一个列表，它对应这某个用户发过的推文，本身就是按照顺序插入的，所以单个列表是有序的，在这若干个有序的列表中选出前 10 个，相当于有序链表的 k 路归并的问题(23. 合并K个排序链表)加上一个 10 的限制，有序链表的 k 路归并问题有很多解法，也有很多扩展和应用场景，这是一个单独的话题，这里用堆来实现有序链表的 k 路归并。参考文章 力扣23-合并K个升序链表。

通过以上分析，在 HashMap 中用户 id 需要保存的信息用一个结构体 UserInfo 维护，结构体中有一个 HashSet 维护的关注对象集合和一个链表维护的推文列表。

1
2
3
4
5
6
7
8
9
10
struct UserInfo
{
    UserInfo()
    {
        followees = unordered_set<int>();
        twitters = list<TwitterInfo>();
    }
    unordered_set<int> followees; // 当前用户关注的用户集合
    list<TwitterInfo> twitters; // 当前用户推特列表，越靠前越新
};

由于检索 10 条最近的推文的需求需要推文的时间信息，因此链表中除了保存推文 id 还需要推文的发送时间，用一个结构体 TwitterInfo 维护。

1
2
3
4
5
6
struct TwitterInfo
{
    TwitterInfo(int tweetid=-1, int time=-1): tweetid(tweetid), time(time) {}
    int tweetid;
    int time;
};

代码(C++)

  • 其中有序链表多路归并的部分在题目 23. 合并K个排序链表 的代码上加上 10 的限制条件即可。
  • 用一个全局的计数器来表示推文的发送时间，这可以表示推文的前后关系。
  • 检索最近 10 条推文的时候，用vector*> cand保存所有候选推文列表的指针交给多路归并的辅助函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <vector>
#include <queue>
#include <list>
#include <unordered_set>
#include <unordered_map>

struct TwitterInfo
{
    TwitterInfo(int tweetid=-1, int time=-1): tweetid(tweetid), time(time) {}
    int tweetid;
    int time;
};

struct UserInfo
{
    UserInfo()
    {
        followees = unordered_set<int>();
        twitters = list<TwitterInfo>();
    }
    unordered_set<int> followees; // 当前用户关注的用户集合
    list<TwitterInfo> twitters; // 当前用户推特列表，越靠前越新
};

class Twitter {
public:
    Twitter() {
        usersinfo = unordered_map<int, UserInfo>();
        twitter_cnt = 0;
    }

    void postTweet(int userId, int tweetId) {
        // 若用户id没见过则新建用户
        if(usersinfo.find(userId) == usersinfo.end())
            usersinfo[userId] = UserInfo();
        // 在用户信息中更新当前推特
        usersinfo[userId].twitters.push_front(TwitterInfo(tweetId, twitter_cnt));
        ++twitter_cnt;
    }

    vector<int> getNewsFeed(int userId) {
        vector<list<TwitterInfo>*> cand;
        cand.push_back(&usersinfo[userId].twitters);
        for(int followee_id: usersinfo[userId].followees)
            cand.push_back(&usersinfo[followee_id].twitters);
        return _mergeKLists(cand);
    }

    void follow(int followerId, int followeeId) {
        // 若用户id没见过则新建用户
        if(usersinfo.find(followerId) == usersinfo.end())
            usersinfo[followerId] = UserInfo();
        if(usersinfo.find(followeeId) == usersinfo.end())
            usersinfo[followeeId] = UserInfo();
        // 处理关注
        unordered_set<int> &followees = usersinfo[followerId].followees;
        if(followerId == followeeId || followees.find(followeeId) != followees.end())
            return;
        usersinfo[followerId].followees.insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        // 若用户id没见过则新建用户
        if(usersinfo.find(followerId) == usersinfo.end())
            usersinfo[followerId] = UserInfo();
        if(usersinfo.find(followeeId) == usersinfo.end())
            usersinfo[followeeId] = UserInfo();
        // 处理取关
        unordered_set<int> &followees = usersinfo[followerId].followees;
        if(followerId == followeeId || followees.find(followeeId) == followees.end())
            return;
        usersinfo[followerId].followees.erase(followeeId);
    }

private:
    unordered_map<int, UserInfo> usersinfo;
    int twitter_cnt; // 记录次序

    using lTi = list<TwitterInfo>::iterator;
    using PLL = pair<lTi, lTi>;

    vector<int> _mergeKLists(const vector<list<TwitterInfo>*>& lists) {
        if(lists.empty()) return {};
        priority_queue<PLL, vector<PLL>, Cmp> pq;
        for(list<TwitterInfo> *l : lists)
        {
            if(!(l -> empty()))
                pq.push(PLL({l -> begin(), l -> end()}));
        }
        if(pq.empty()) return {};
        vector<int> result;
        while(!pq.empty())
        {
            PLL top = pq.top();
            pq.pop();
            result.push_back(top.first -> tweetid);
            if((int)result.size() == 10)
                return result;
            ++top.first;
            if(top.first != top.second)
                pq.push(top);
        }
        return result;
    }

    struct Cmp
    {
        bool operator () (const PLL& left, const PLL& right)
        {
            // > 是小顶堆；< 是大顶堆
            return (left.first -> time) < (right.first -> time); 
        }
    };
};
Share