本文例題來(lái)自355-Design Twitter

題目

355-Design Twitter

分析

本題非常貼近于程序員碼代碼的日常需求，剔除了與DB和其他接口的交互叔锐，所以唯一要考慮的就是不同的數(shù)據(jù)挪鹏，用何種數(shù)據(jù)類型來(lái)處理。
提煉題目愉烙，發(fā)現(xiàn)了至少需要如下兩個(gè)數(shù)據(jù)類型

• 隸屬于個(gè)人的推文列表讨盒，為了方便取最新的十筆推文，使用隊(duì)列DEQUE是個(gè)好辦法步责。
• 隸屬于個(gè)人分關(guān)注列表返顺，為了剔除重復(fù)性使用集合SET

個(gè)人的解法

無(wú)

評(píng)論的力量

評(píng)論有個(gè)解法非常優(yōu)秀禀苦，本分分析即源自此解法

關(guān)注列表用set實(shí)現(xiàn)，添加和刪除都比較簡(jiǎn)單 #推文列表用list實(shí)現(xiàn)遂鹊，時(shí)間戳+推文組成元組加入列表（初始方案振乏，不行） 推文列表用雙端隊(duì)列（deque）實(shí)現(xiàn)，時(shí)間戳+推文組成元組加入隊(duì)列頭 最復(fù)雜的是獲取推文秉扑，用最大堆實(shí)現(xiàn)十條推文的獲取昆码。hepq.merge可以多輸入單輸出排序，再用itertools.islice(iterable, stop) 切片邻储。
by LJ001
python

collections.defaultdict

字典dict的子類赋咽，放到面對(duì)對(duì)象來(lái)說(shuō)，即繼承了字典吨娜，并實(shí)現(xiàn)了額外的方法——提供了一個(gè)工廠函數(shù)脓匿，為字典查詢提供一個(gè)默認(rèn)值。
1.何為工廠函數(shù)
這是一個(gè)面向?qū)ο缶幊痰母拍罨略嬖诘囊饬x就是當(dāng)你調(diào)用此函數(shù)時(shí)陪毡，就建立了一個(gè)對(duì)應(yīng)的對(duì)象，而這個(gè)對(duì)象的形式和你的調(diào)用函數(shù)和傳入值有關(guān)勾扭，工廠會(huì)根據(jù)你的調(diào)用生成指定的對(duì)象毡琉，而調(diào)用者無(wú)需去管理工廠里面用的哪些接口。詳細(xì)可以看設(shè)計(jì)模式——工廠模式
2.為字典查詢提供一個(gè)默認(rèn)值是什么意思
簡(jiǎn)單點(diǎn)來(lái)說(shuō)妙色，當(dāng)字典不存在此鍵值對(duì)時(shí)桅滋，defaultdict提供了初始化，并給予了默認(rèn)值身辨，最明顯的結(jié)果如下：

#!/usr/bin/python3
> d = collections.defaultdict(list)
#defaultdict(<class 'list'>, {})
> print(d)
#[]
> print(d['JACK'])
#defaultdict(<class 'list'>, {'JACK': []})
> print(d)

不需要?jiǎng)?chuàng)建即有了鍵值對(duì)丐谋。用處不言而喻，跳過(guò)了可能的存在性檢查煌珊，不存在即創(chuàng)建号俐。一定程度上代替了如下兩種方法：

dict的miss定義

dict的內(nèi)置方法setdefault

同時(shí)defaultdict還給我們提供了用lambda初始化的方法

#!/usr/bin/python3
d = collections.defaultdict(lambda : '1')

heapq.merge

堆排序算法其中之一的工具

heapq.merge

解釋下*，表示對(duì)iterable變量定義為可變變量

itertools.islice

itertools.islice

class Twitter:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.tweets=collections.defaultdict(collections.deque)
        self.followlist=collections.defaultdict(set)
        self.timestamp=2**31
    def postTweet(self, userId, tweetId):
        """
        Compose a new tweet.
        :type userId: int
        :type tweetId: int
        :rtype: void
        """
        self.timestamp-=1
        self.tweets[userId].appendleft((self.timestamp,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]
        """
        tweets = heapq.merge(*(self.tweets[u] for u in self.followlist[userId] | {userId}))
        return [t for _, t in itertools.islice(tweets, 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.followlist[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.followlist[followerId].discard(followeeId)