給一串數列，取出最大的兩個相減，如果結果非零，而把結果加回數列，重複進行，直到剩一個元素或是沒有元素，回傳該元素的值，若無而回傳 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"

給一串 Doubly Linked List ，其中某節可能有 child ，要求你把這串 Doubly Linked List 平坦化，而 child 會插入在 該節 與 下一節 之間。

A – B – C – D – E        => A – B – F – G – C – D – E
      F  – G

寫一個遞迴函數，如果遇到 child ，你需要它的頭尾，針對這兩點修改就好。
(尾)G.next = B.next,  G.next.prev = G 、B.next = F(頭) , B.next.prev = B

於是遞迴函數的回傳值，就設定是 head 與 tail。

頭是搜尋的起點，有頭才能夠搜尋，而尾在尚未搜尋前是未知的，於是遞迴函數的回入值是頭節。

這樣在一路到底搜尋時，若是碰到 child，則把 child node 傳給遞迴函數，取得該子串的頭尾，然後插入當前的位置與下一位置的中間。

空間複雜度為 O(1)

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        def nextNode(node):
            head = tail = node            
            while tail:
                if tail.child:
                    ch, ct = nextNode(tail.child)
                    if tail.next:
                        ct.next = tail.next
                        ct.next.prev = ct
                    tail.next = ch
                    tail.next.prev = tail
                    tail.child = None
                    tail = ct                   
                else:
                    if tail.next:
                        tail = tail.next
                    else:
                        break            
            return head, tail            
        return nextNode(head)[0]

另外一種則是先遍歷，記錄順序，最後再重組。

class Solution:    
    def flatten(self, head: 'Node') -> 'Node':
        nodes = []
        def nextNode(node):
            if node:
                nodes.append(node)
                nextNode(node.child)                
                nextNode(node.next)
        nextNode(head)
        p = None
        for each in nodes:
            each.child = None
            each.prev = p
            if p: p.next = each
            p = each
        return head

判別 Linked List 的值是否為回文。

凡是回文問題，就一定要知道長度，才能知道哪裡是分水嶺。

如果想用紀錄數值，最後再判別是否回文，由於該值可能為雙位數或是負數，如果想用 str 紀錄數值，就必須做特殊處理。

使用 list 紀錄，等過了分水嶺之後，就是該值與紀錄逐一對比，不符合就不是回文，找完就是回文。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head: return True
        len_head = 1
        SP = FP = head
        while FP.next:
            len_head += 1
            FP = FP.next            
        #
        stack = []
        for _ in range(len_head//2):
            stack.append(SP.val)
            SP = SP.next
        if len_head%2==1: SP = SP.next
        while stack:
            if SP.val != stack.pop():
                return False
            SP = SP.next
                
        return True

簡化回文的判斷，使用 stack == stack[::-1]，這樣只需要比較一次，不用記錄長度，空間複雜度仍是 O(n)。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:     
        stack = []
        while head:
            stack.append(head.val)
            head = head.next      
        return stack == stack[::-1]

如果利用循環的概念，快指針走 長度-1 、 慢指針走 1 ，兩兩相相比，不相等就不是，直到快指針追到慢指針結束。

但是這樣會超時。

如果空間複雜度局限於 O(1)，就要使用 reverse 的概念，不論是把分水嶺前面的或後面的 reverse 都可以。反序完再兩兩比較。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head: return True
        len_head = 1
        SP = FP = head
        while FP.next:
            len_head += 1
            FP = FP.next            
        #
        for _ in range(len_head//2):
            FP = SP
            SP = SP.next
            FP.next = head
            head = FP           
        if len_head%2==1: SP = SP.next
        while SP:
            if SP.val != head.val:
                return False
            SP = SP.next
            head = head.next
                
        return True

最近我的leetcode總是跑得比別人慢，即使是一樣的代碼，就是遜一節，不知道為什麼。