Hi 大家好，今天要繼續來分享歸類在Design的題目。這種模擬實際系統中的核心功能的題目在python中最常用到的資料結構就是list, dictionary, deque, linked list（可以參考前面的篇章中的LRU Cache）。

Leetcode 359. Logger Rate Limiter

題目敘述：
設計一個日誌系統可以依時序接受訊息。每一種訊息要等至少10秒才能再印出相同的訊息。
需要完成"bool shouldPrintMessage(int timestamp, string message)"回傳True如果這類型的訊息在這個時間點是可以印出來的，否則就回傳False。

Example1:

Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");  // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar");  // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo");  // 3 < 11, return false
logger.shouldPrintMessage(8, "bar");  // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21

分析：
使用hashmap去對應不同的訊息和下一次訊息可以被印出的時間點，如果現在出現的訊息尚未被紀錄在hashmap中代表是第一次發出這種訊息，或著發出這個訊息的時間點已經比儲存在hashmap中所規定的時間點久了。上述兩種情況更新hash map並且回傳True。

class Logger:

    def __init__(self):
        self.record = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message not in self.record or timestamp >= self.record[message]:
            self.record[message] = timestamp + 10
            return True
        else:
            return False



# Your Logger object will be instantiated and called as such:
# obj = Logger()
# param_1 = obj.shouldPrintMessage(timestamp,message)

Leetcode 1472. Design Browser History

設計一個瀏覽器中可以根據歷史紀錄去瀏覽網站的功能。

• 首先設定一個首頁
• 可以利用visit()去描述從某個網站跳轉到另一個網站，但是會清除掉所有從當前網站按「下一頁就」可以去拜訪的網站的歷史紀錄
• string back(int steps):描述使用者按了「幾次上一頁」後會到達哪一個網站。
• string forward(int steps)：有上一頁的功能當然就會有下一頁的功能，可以讓使用者從從目前已被紀錄的歷史紀錄的網站往前跳轉，最多回到歷史紀錄中最新記錄下來的網站。

分析：

• 首先要有一個可以記錄歷史紀錄的容器，我們使用list，並且也要記錄下當前網站會在這個list的哪一個index，所以需要一個index變數。
• visit會清除掉所有的forward history，所以我們會根據目前的index去清除在這index後儲存在list中的元素。再加入現在想去拜訪的網站。
• back以及forward只需要移動index，並且index最多可以往前、往後移動多少則要根據list中的邊界值決定。

class BrowserHistory:

    def __init__(self, homepage: str):
        self.sites = [homepage]
        self.curr = 0

    def visit(self, url: str) -> None:
        if self.curr != len(self.sites) - 1:
            for _ in range(self.curr + 1, len(self.sites)):
                self.sites.pop()
        self.sites.append(url)
        self.curr += 1

    def back(self, steps: int) -> str:
        count = 0
        while self.curr > 0 and count < steps:
            self.curr -= 1
            count += 1
        
        return self.sites[self.curr]

    def forward(self, steps: int) -> str:
        count = 0
        while self.curr < len(self.sites) - 1 and count < steps:
            self.curr += 1
            count += 1
        
        return self.sites[self.curr]
        


# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)

1166. Design File System

題目敘述：
建造一個可以創建新的路徑以及和這個路徑對應的值得File system。
需要有父路徑，才能有子路徑，否則在建造時回傳False。只有成功建造出某路徑時才回傳True。
如果要建造的路徑已經存在也回傳False。
可以去存去和路徑對應的值。（這邊的值應該就是對應真實檔案系統中的檔案）

Example1:

Input: 
["FileSystem","createPath","createPath","get","createPath","get"]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]
Output: 
[null,true,true,2,false,-1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/leet", 1); // return true
fileSystem.createPath("/leet/code", 2); // return true
fileSystem.get("/leet/code"); // return 2
fileSystem.createPath("/c/d", 1); // return false because the parent path "/c" doesn't exist.
fileSystem.get("/c"); // return -1 because this path doesn't exist.

從上面的範例中可以看出因為沒有先建立"/c"就想建立"/c/d"，所以回傳False。

分析：

• 利用hashmap去紀錄已經建立的路徑和對應的值。
• 當要建立某條路徑時，先去比對最底層的資料夾之前的路徑是否已經存在於hashmap中（有沒有parent path）；之後再去比較整條路徑是否存在於hashmap中（是否已經建立過此路徑）

class FileSystem:

    def __init__(self):
        self.fs = {"": 0}

    def createPath(self, path: str, value: int) -> bool:
        path = path.split('/')
        directory = '/'.join(path[:-1])
        
        if directory not in self.fs:
            return False
        
        if directory + '/' + path[-1] in self.fs:
            return False
        
        self.fs[directory + '/' + path[-1]] = value
        return True

    def get(self, path: str) -> int:
        path = path.split('/')
        path = '/'.join(path)
        if path not in self.fs:
            return -1
        return self.fs[path]


# Your FileSystem object will be instantiated and called as such:
# obj = FileSystem()
# param_1 = obj.createPath(path,value)
# param_2 = obj.get(path)

Leetcode 297. Serialize and Deserialize Binary Tree

題目敘述：許多時候會將資料結構轉換成某種序列，方便儲存在檔案或是記憶體緩衝中，也可能是為了利用網路傳輸。並且之後再將這列序列重新建回原本的資料結構。今天要轉換的是二元樹，把二元樹轉換成字串後，再利用這個字串轉換回一模一樣的二元樹。

Example1:

(圖源:leetcode)

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

中間要轉換成什麼格式的字串，可以由programmer自行決定。

分析：

1. 利用preorder的方式去拜訪：先儲存root再去拜訪左子樹再來是右子樹。
2. Base case是遇到None，就回傳'N'來作為代表符號。
3. 再次將轉換後的字串以preorder的順序去建出二元樹，不過我們需要一個全域變數去紀錄目前使用到原先字串中的哪一個index。
   

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        res = []

        def dfs(node):
            if not node:
                res.append('N')
                return
            
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        
        dfs(root)
        return ','.join(res)

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        
        data = data.split(',')
        self.i = 0

        def dfs():
            if data[self.i] == 'N':
                self.i += 1
                return None
            
            node = TreeNode(int(data[self.i]))
            self.i += 1
            node.left = dfs()
            node.right = dfs()
            return node
        
        return dfs()

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

今天是鐵人賽的最後一篇。能夠連續30天完成這個主題，我心中還是有點小小的成就感，雖然不管是向他人表達自己的解題脈絡或著解題的技巧我都還有很大的進步空間，但會繼續加油的。明年的話也想要來挑戰不同的主題。希望大家都能一起進步！