給一個二維串列 grid，每格代表一種道路，其值可以對應下表，要回傳是否能從左上角走到右下角。

1 which means a street connecting the left cell and the right cell.
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.

對於這種地圖或是面積的圖像問題，我總是感到棘手，也許有一套通用思路，不過可能需要很多經驗值累積才能解得順手。

從左上角開始，但是沒有規定左上角一定是從外面延伸進來，如果是 grid[0][0]  == 5，一開始就死局。如果等於 4，那一開始就會有兩條路線。

要怎麼解決起始有兩條路線的問題，就會是一個難題。又或者拋開心中虛擬的小車車，直接用遞迴 + memo 去從(0, 0)拔起所有合格座標，再看看右下角是否存在。

街道有六種形式，而且具有方向問題，困難點在此，要怎麼妥善解決轉向，這就值得思考。

每一種街道只能接受兩種方向，例如 street 1，如果從右邊來，通過後方向朝左邊；如果從左邊來，通過後方向朝右邊。如果從其他方向，那就代表無法接到一起。

街道對應的方向就只能老實打出，無法再快，這是題目的定義。

如果在當前位置向右走，對下一個位置是從左來，對於制定方向前進的人，要留意方向上的切換。

思考一下之後，使用遞迴拔出所有與(0,0)連接的街道會比較泛用。

class Solution:
    def hasValidPath(self, grid):
        """
        1 which means a street connecting the left cell and the right cell.
        2 which means a street connecting the upper cell and the lower cell.
        3 which means a street connecting the left cell and the lower cell.
        4 which means a street connecting the right cell and the lower cell.
        5 which means a street connecting the left cell and the upper cell.
        6 which means a street connecting the right cell and the upper cell.
        """   
        # 0 up 1 left 2 down 3 right        
        streets = {1:(1,3), 2:(0,2), 3:(1,2), 4:(3,2), 5:(1,0), 6:(3,0)}

        path = set()
        rows, cols = len(grid), len(grid[0]) 

        def searchMap(y,x):
            if y < 0 or x < 0: return 
            if y == rows or x == cols: return
            path.add((y,x))
            ds = streets[grid[y][x]]
   
            for d in ds:
                x2,y2=x,y
                if d == 0:                    
                    y2 = y-1
                elif d == 1:
                    x2 = x-1
                elif d == 2:
                    y2 = y+1
                else:
                    x2 = x+1
                d = (d+2)%4 #換方向(下一個位置的相對方向)
                if (y2, x2) not in path:
                    if y2 < 0 or x2 < 0 or y2 == rows or x2 == cols: 
                        continue
                    elif d in streets[grid[y2][x2]]:
                        searchMap(y2,x2)

        searchMap(0,0)
        return (rows-1, cols-1 ) in path

給一個 n，代表 (n , 3) 的二維串列，每個位置可以填入R、G、Y三色，而每個顏色不能相鄰(上下左右)相同，要求出一共有幾種填法。

這是我第二次做到要取餘的題目，代表方法數真的很大。

如果 n = 7，就會超時。

我左右一看，感覺到這只是個數學問題，可以代公式求解，不用真的計算。結果真的找到公式，代上去只用 一百多毫秒 就能通過測試。

在我心中，用公式解，就像拋棄電腦強大計算能力不用，背棄了用程式語言邏輯去解決問題的宗旨，跟作弊是沒兩樣的。

於是我還是老實地寫出一個合格的解法。

先看題目，第一層有12種組合。每一層的所有組合，都在這12種之內。

第二層有多少種組合，取決於第一層，也就是最後一層相鄰的那一層。

每種組合後面能接上的組合是固定的，只要找出來，就不必去費心再去搜尋下一層有甚麼可能。

所有A組合能接的下一層組合，都加上A組合的數目。n層的總和就是n層所有組合的加總。

不論是三種顏色還是四種顏色，寬三格還是四格，都可以套用這樣的邏輯去處理。

class Solution:
    def numOfWays(self, n: int) -> int:
        # 建立第一層
        memo = dict()
        memo["now"] = {}
        memo["next"] = {}
        colors = set(["r","g","y"])
        # 找到所有顏色組合
        def findColorSet(stats):
            if len(stats) == 3:
                memo["now"][stats] = 1
                return 
            for c in colors:
                if not stats or c != stats[-1]:
                    findColorSet(stats+c)
        findColorSet("")

        # 
        c2c = {}
        for c1 in memo["now"]:
            c2c[c1] = []
            for c2 in memo["now"]:
                isLegal = True
                for ch1, ch2 in zip(c1,c2):
                    if ch1 == ch2:
                        isLegal = False
                        break
                if isLegal:
                    c2c[c1].append(c2)
        #
        if n > 1:
            keys = memo["now"].keys()
            for row in range(2,n+1):
                memo["next"] = {}.fromkeys(keys,0)
                for key in keys:
                    v = memo["now"][key]
                    for key2 in c2c[key]:
                        memo["next"][key2] += v
                memo["now"].update(memo["next"])
                
        return sum(memo["now"].values()) % (10**9+7)   

這樣子符合要求我自身要求，用程式邏輯找到答案。

下面附贈公式解，也是我第一個想出來的解法。

class Solution2:
    def numOfWays(self, n: int) -> int:
        self.ans = 0
        table = dict()
        table2 = dict()
        table2[1] = 12
        table[1] = 0
        table2[2] = table2[1]*9//2+table[1]
        table[2] = 3
        
        if n >= 3:
            for i in range(3, n+1):
                table2[i] = table2[i-1]*9//2+table[i-1]                
                table[i] = table2[i-2]+table[i-1]                
        
        return table2[n] % (10**9+7)

給一串數列，取出最大的兩個相減，如果結果非零，而把結果加回數列，重複進行，直到剩一個元素或是沒有元素，回傳該元素的值，若無而回傳 0。

一說到要取出最大的兩個，就會想到用 sort() 排列。 ※注意 sort() 是從小而大排列，想要反敘可以這樣寫 sort(reverse = True)。

每一次取出前兩個對減，加回去再重新排列，重複步驟直到不能再進行，這是最直覺的方式。

排列之後會照大小排列，如果取出兩元素相減後還 >= 剩下的第一個元素，代表兩者是當前最大的兩元素，就可以繼續相減。

條件不符合加回去再重新排列，這樣可以減少不必要的排列次數。

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:        
        n = len(stones)        
        while n > 1:
            stones.sort(reverse = True)
            v = stones.pop(0)
            while n > 1 and v >= stones[0]:
                v -= stones.pop(0)
                n -= 1
            if v == 0: n-= 1
            else: stones.append(v)        
        if stones: return stones[-1]
        else: return 0

給一串二元樹，問直徑，也就是節對節之間的最長距離。

如果以 root 來看，通過 root 的最長距離，就是 root.left 的最大深度加上 root.right 的最大深度。

於是方向很清晰，我們要用一個函數去取得該node的最大深度。這樣就能進而找出各個距離，再找出最長距離。

要寫遞迴函數，而且會從最深的地方開始，而最深的地方會往上層層回傳最大深度。

因此回傳的值是「深度」，如果沒有node，就回傳 0。

如果有node，要往上回傳最大深度，就需要知道 node.left 與 node.right 的深度，最大深度是從二者選著大的，然後加上自身 +1。

當我們得到 node.left 與 node.right 的深度時，兩者相加後，就能得到通過該 node 的最長距離。

這樣就能用 max() 去更新最大值，等待遞迴函數跑完，此時的最大值就是該二元樹的最長距離。

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.maxDM = 0        
        def getMaxDepth(node):
            if node:
                left_depth = getMaxDepth(node.left)
                right_depth = getMaxDepth(node.right)
                DM = left_depth + right_depth
                self.maxDM = max(self.maxDM, DM)
                return 1 + max(left_depth, right_depth)
            else:
                return 0
        getMaxDepth(root)
        return self.maxDM

設計一個 stack，而且能在 O(1) 時間內回傳最小值。

stack是後進先出，如果眼前有書疊，要拿也是會從最上方拿起，最上方的書也是最後放的。

要實現stack，用list儲存資料就可以。

stack新增資料，用list.append()。 stack.pop => list.pop()。用list實現stack基本功能是沒有問題的。

這個 Min Stack 特別之處，在 O(1) 時間內回傳最小值，如果用 min()，而時間複雜度會是 O(n)。

因此在 Min Stack 的類別下，要有一個保存最小值的屬性，這樣才能第一時間回傳最小值。

用 int 保存可以嗎？

如果最後面加入的是最小值，然後被pop()掉，此時如果要調出此時的最小值，要怎麼處理？

如果連續加入兩個最小值，然後被pop()掉一個，又要怎麼處理最小值呢？

要是pop()掉的值是最小值，此時再用min()重新定位最小值，如果剛剛pop()掉的是僅剩的那一個元素呢？

如果考慮到stack的後進先出，這裡有個更妙的處理方式。就是使用一個minStack(list)。

加入的資料要是小於minStack[-1]的值，該值就順便加入到minStack。由於後進先出的特性，pop()掉的值一定會先遇到minStack[-1]，才會到[-2]、[-3]…

返還最小值，也只要回傳minStack[-1]就可以了。

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack=[]
        self.mini_stack=[]

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.mini_stack or x<=self.mini_stack[-1]:
            self.mini_stack.append(x)        

    def pop(self) -> None:
        if self.stack.pop() == self.mini_stack[-1]:
            self.mini_stack.pop()        
        
    def top(self) -> int:
        return self.stack[-1]        

    def getMin(self) -> int:
        return self.mini_stack[-1]

給一個字符串，如果遇到「#」，就等於按下Backspace鍵去修改字符串。

如果直接直譯規則書寫，寫起來就是那麼樸實無華且枯燥，這樣也能通過。

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        newS = ""
        for char in S:
            if char == "#":
                if newS: newS = newS[:-1]
            else:
                newS += char
        newT = ""
        for char in T:
            if char == "#":
                if newT:
                    newT = newT[:-1]
            else:
                newT += char    
        return newS == newT

不過呢，題目希望我們能在 O(N)時間 並 O(1)空間 完成。

由於倒退符是往前刪除，因此由後往前對比就可以遇到#字再往前挪動。

指派一個 counter ，遇到 # 就 +1 ，非# 則 -1，使用 while 要跑到 counter 為 0 或是 跑到出界 為止。

這樣就無需使用到 O(N) 空間，用 O(1) 空間。同時也只需要跑一遍 N，花上 O(N) 時間。

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool: 
        # 回車函式
        def getPrev(text, pos):
            backspaceCounter = 1
            while backspaceCounter and pos >= 0:
                pos -= 1                    
                if text[pos] == "#": 
                    backspaceCounter += 1
                else:
                    backspaceCounter -= 1
            if pos >= 0: return pos           
            return -1

        SP, TP = getPrev(S, len(S)), getPrev(T, len(T))

        while SP > -1 and TP > -1:
            if S[SP] != T[TP]: break
            SP, TP = getPrev(S, SP), getPrev(T, TP)

        if TP == -1 and SP == -1: return True
        return False

要回傳 Linked List 中間的節點，如果長度是偶數，則中間偏右那一個。

有兩種解法：

第一種是跑完一遍得到長度，計算距離，再從頭跑到中間即可。前進距離是 length //2 。

第二種是用快慢指針，每回合快針走兩步，慢針走一步。當到了快針不能再走的回合，慢針會在中間的位置。

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        if not head: return head
        FP, SP = head, head
        while FP and FP.next:
            FP = FP.next.next
            SP = SP.next
        return SP

給一個數列，如果元素其值 +1 也在數列內的個數。如果有重複，則分開計算。

不多說甚麼，順一下解題邏輯。

如果要得知元素其值+1是否也存在於數列內，就得找完所有數列，並記錄元素是否有出現。

如果有重複出現，像是 1 1 2 2， 1 出現兩次且 2 在數列內，所以答案要加兩次。

於是記錄元素出現的時候，就要順便把其出現次數記錄下來。

最後跑完 memo 的鍵，鍵就是出現過的元素，若元素+1也在 memo 裡，答案就加上該元素的出現次數。

class Solution:
    def countElements(self, arr: List[int]) -> int:
        memo = dict()
        for num in arr:
            if num in memo: memo[num] += 1
            else: memo[num] = 1
        result = 0
        for key in memo:
            if key+1 in memo:
                result += memo[key]
        return result

Alice 跟 Bob 進行石頭遊戲，把石頭排成一排，一人一次拿 1 ~ 3 個，每個石頭都各有其分數，最後雙方誰持有的石頭分數總和高者勝。

這是 contest 的題目，在時限內沒有解出這一題，可惜。

雙方都會不會放水，採取最佳策略進行。這樣的情況下，如果是 Alice 贏就回傳 Alice，Bob 贏則 Bob，平手則 Tie。

這是一個博奕問題：有雙方，互相採取行動，兩者互相對抗。

當看到雙方都採取一樣的策略之時，雙方的判斷都是一樣的，因此用一個邏輯函數，就要能指出該下哪一步。

以拿走三顆石頭的時候來看，不論是此時是輪到 A 或者是 B ，兩者當前的最佳解都是一樣的。先後順序不影響決定最佳解，局面進行到哪裡才是。

因此，用一個 memo 記錄所有情形，其鍵會是拿走的數量或是剩餘的數量。這memo紀錄的分數對雙方都是一樣的。

接下來講一點博奕心理。

在選擇行動時，不一定會選擇當下分數最高的，如果最後要贏對手，採取行動原則是為了要讓自己領先對手加大差距，距離變化才是關鍵。

像是 -1 -2 -3 ，如果選擇分數最高的行動只拿 -1 ，對手會只拿 -2 ，最後你不得已只能拿 -3 而輸掉。

考量到對手的行動，你拿 -1 對手拿 -2 整體反倒被 對手拉近 1 的距離，若拿 -1 -2 對手會只能拿 -3，整體差距並沒有縮小，反到是更有利的選擇。

不過這沒提到後手再後手。你拿 -1 要思考對手的下一步， 而對手會思考對手的下一步再下一步，行動連鎖直到結束。連鎖到底，這種特性是遞迴。

整理一下觀察到的線索，推導出邏輯函數會是一個考慮拉大對手差距的遞迴函數。

那這個遞迴函數要回傳甚麼？

回到 -1 -2 -3 的例子，當你拿 -1，對手會採取最佳解，也就是剩下 -2 -3 的最佳拿法的分數。拿 -1 -2，也需要對手的最佳解。然後在三種選擇中，拿 -1 -2 是最佳解。

於是你可以找出當前狀況最佳解，回傳分數，遞迴往前傳，就能把最佳解一路往前推導。

最後來到起點，雙方一動也沒動的時候，此時由 Alice 先手，因此沒動過的最佳解，就是 Alice 的最佳下法的分數，如果為正的，意味著到最後 Alice 會贏那些分數。0則平手，負則輸掉。

class Solution:
    def stoneGameIII(self, stoneValue):     
        stones = len(stoneValue)
        pos = 0
        memo = {} # 使用座標當標籤

        def searchMaxRelativeScore(pos):   
            if pos in memo: return memo[pos]
            # 計算出當前剩餘個數            
            score = 0
            scores = []
            remains = min(stones - pos, 3)
            for i in range(remains):
                scores.append(sum(stoneValue[pos:pos+i+1]) - searchMaxRelativeScore(pos+i+1))
            if scores: score = max(scores)
            memo[pos] = score
            return score

        searchMaxRelativeScore(0)

        if memo[0] > 0: return "Alice"
        elif memo[0] == 0: return "Tie"
        else: return "Bob"