首先 609. Find Duplicate File in System (medium)
https://leetcode.com/problems/find-duplicate-file-in-system/

題目會給你一個paths的list，裡面的每份資料第一個段落都是他們的目錄名稱，後面的段落就是檔案名稱以及內容。
題目要求要把相同內容的資料分為一類，並儲存至同一個串列當中，其中資料名稱要包含目錄名稱但不需要包含內容。
若沒有重複內容的檔案不需要return回來。

當我看到這題的第一個想法就是dict吧，利用內容當作key，名字當成value並儲存至串列當中。
想法：

1. 建立空dict
2. 迭代paths，並將目錄名稱與檔案名稱分開，其中檔案名稱變成另一個串列temp
3. 迭代temp，想辦法讀出content之後建置至dict裡面
4. 迭代dict.values()，把不只一個內容的丟到ans的list裡

class Solution:
    #分類再分類的題目
    #必須偵測括弧內的文字進行分類
    #要把只有一種的刪除掉，所以如果每一個都只有一種回傳[]給他
    #不難但是煩
    def findDuplicate(self, paths: List[str]) -> List[List[str]]:
        d = {}
        c = 0#計算種類用
        for i in paths:
            temp = i.split(" ")
            root = temp.pop(0)
            for j in temp:
                s = j.index('(')
                docContent = j[s+1:-1]
                if docContent not in d:
                    d[docContent] = [root+"/"+j[:s]]
                else:
                    d[docContent].append(root+"/"+j[:s])
                c+=1
        ans = []
        for i in d.values():
            if len(i)>1:
                ans.append(i)
        return ans

基本上就以上這樣吧，我想不到更好的辦法了

下一題 653. Two Sum IV - Input is a BST (easy)
https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

簡單來說要在BST裡面找到兩個數字n1,n2，加起來可以變成k。

當我看到這題的時候瞬間就寫了這個方法

class Solution:
    #白癡法
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        valL = []
        def dfs(root):
            if root is None:
                return
            valL.append(root.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        
        for i in range(len(valL)):
            n = k - valL[i] 
            if n in valL and valL.index(n) != i:
                return 1
        return 0

直接把它簡化成 1. Two Sum 但想當然爾，這樣寫效率極差，但對於剛寫BST相關題目的人而言，應該算是方法之一吧。

後來我就稍微認真思考一下，基本上想法還是跟1. Two Sum 差不多。
想法：

1. 建立dict用來儲存，n2當key然後n1當value(不可反過來)
2. 檢查root.val是否已經存在dict哩，是的話代表有解回傳1
   因此變成以下：

class Solution:
    # 正常寫法
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        r = {}
        def dfs(root):
            if root is None:
                return 0
            if root.val in r:
                return 1
            r[k-root.val] = root.val
            return dfs(root.left) or dfs(root.right)
        return dfs(root)

當稍微思考後覺得可以更改，畢竟他不需要儲存是由哪兩個數字相加，因此只需要確認有沒有即可，所以修改成set版本

class Solution:
    #小改，用set紀錄要找的數字
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        r = set()
        def dfs(root):
            if root is None:
                return 0
            if root.val in r:
                return 1
            r.add(k-root.val)
            return dfs(root.left) or dfs(root.right)
        return dfs(root)

大致上這樣子這題就完成了

下一題 657. Robot Return to Origin (easy)
https://leetcode.com/problems/robot-return-to-origin/

題目會給一個字串moves，裡面每個文字代表對機器人下的指令，R向右、L向左、U向上、D向下。問說最後是否可以到返回起點。

我看到這題時，覺得就數R、L、U、D數量即可，不需要真的去跑座標。所以直接這樣寫

class Solution:
    #檢測是否可以回到原點
    def judgeCircle(self, moves: str) -> bool:
        a,b,c,d = moves.count("R"),moves.count("L"),moves.count("U"),moves.count("D")
        return a == b and c == d

然後就沒再思考了，反正無論怎麼寫對於Python而言都不難。

下一題 661. Image Smoother (medium)
https://leetcode.com/problems/image-smoother/

很煩的題目

簡單說好了，有一個matrix，要計算matrix[i][j] 四周的平均值(包含自己)為和，然後存回matrix[i][j]
題目裡什麼3x3 smooth的，是來擾亂思緒用的。

想法1：
1.建立 d matrix用來儲存上、下、左、右、上左、上右、下左、下右的位移
2.迭代matrix，把四周跑過一遍，然後把平均值存在新的matrix當中
3.期間可能要注意數過多少格子，特別是在邊界的地方不可算錯。

class Solution:
    #總之大概懂了，反正就是一個3x3的格子會進行位移，然後全部都要算平均值
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        L,W = len(img),len(img[0])
      # r = [[0]*W]*L #這邊不小心忘記 * 的話會記錄到一樣的空間
        r = [[0]*W for i in range(L)]
        d = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        #原本想說按照規則移動，但其實直接按照題目裡紅色的方式移比較簡單
        for i in range(0,L):
            for j in range(0,W):
                t,c = img[i][j],1 #t計算總合,c計算有幾個格子
                for a,b in d:
                    x,y = i+a,j+b
                    if 0<=x<L and 0<=y<W:
                        t+=img[x][y]
                        c+=1
                r[i][j] = t//c#題目有說直接無條件捨去
        return r

大致上就變成這樣，但由於跑的時間一直沒辦法減少，所以參考了一下別人的寫法
直接把d用if else進行手刻，但我個人不是很愛....覺得易讀性變差

class Solution:
    #手刻版，就為了降低時間複雜度
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        L,W = len(img),len(img[0])
        r = [[0]*W for i in range(L)]
        for i in range(L):
            for j in range(W):
                t,c = img[i][j],1
                if i-1 >= 0:
                    if j-1 >= 0:
                        t += img[i-1][j-1]
                        c += 1
                    t += img[i-1][j]
                    c += 1
                    if j+1 < W:
                        t += img[i-1][j+1]
                        c += 1
                if i+1 < L:
                    if j-1 >= 0:
                        t += img[i+1][j-1]
                        c += 1
                    t += img[i+1][j]
                    c += 1   
                    if j+1 < W:
                        t += img[i+1][j+1]
                        c += 1
                if j-1 >= 0:
                    t += img[i][j-1]
                    c += 1
                if j+1 < W:
                    t += img[i][j+1]
                    c += 1
                r[i][j] = t//c
        return r 

以上就是今天的練習謝謝大家