Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

簡單來說，把數列中的零移到最後方，其他各數字的順序維持不變。

依舊很簡單，不過題目有要求：in-place。在數列直接修改，試著不用其他空間或是複製排好的數列。

如果用 for 且順序，那麼遇到0使用 append( pop() )會出錯。詳情不寫，改用倒敘法，這樣遇到 0 就能使用append( pop() )。

一次取出一次加到最後面，嫌太麻煩？不如用個 空串列 保存 pop() 出來的 0，最後再 extend() 保存 0 的串列即可恢復數列。

不過這樣沒有順著題目所期望的解法前進，用了額外的空間保存數列。

A two-pointer approach could be helpful here. The idea would be to have one pointer for iterating the array and another pointer that just works on the non-zero elements of the array.

這裡說用兩個指針，一個是迭代數列，另一個針對非0的元素。

針對迭代數列不用多心，要跑完數列自然就會用上。另外一個針對非0元素的要怎麼寫？

說到要針對非0元素，想必就要使用 if 去區分出來。遇到不是0的要怎麼處理？遇到0的又要怎麼處理？

如果要把 0 移動到最後方，路線有兩種：
1. 把0元素移動到最後方。
2. 把非0元素往前移動到最前方。

說到移動，就是把元素兩兩交換。交換就是一種 in-place 的作法，那要如何交換呢？

這裡使用 順序 去迭代數列，由前而後，所以被往前換的數字是不會再被迭代到而換到。

因此選擇把非0元素往前換，接下來只要不要動到換去前面的非0元素順序，最後就能把 0 都移動到最後方。

往前換，要往前多少？

從頭模擬起，如果一開始沒有碰到 0，就不需要換。接下來要是碰到0，也不用交換。在 0 之後又碰到非0元素，要往前換，要跟前面的0交換。

在遇到非0元素前，碰到一次0，跟前一格(0)換，碰到兩次0，跟前兩格的0交換。推理出，往前交換的位置跟碰到 0 次數是相同的。

碰到 0 ，指針 +1 。碰到 非0 ，就交換。132

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zeroPointer = 0
        for i, num in enumerate(nums):
            if num == 0:
                zeroPointer += 1
            else:
                nums[i], nums[i-zeroPointer] = nums[i-zeroPointer], nums[i]

以下是我看其他大神的最貼切題目要求的寫法。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        last_nnz = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[last_nnz], nums[i] = nums[i], nums[last_nnz] 
                last_nnz += 1

給一串數列，要找出當中各連續部分(contiguous subarray)的最大總和為何。

數字的範圍是甚麼？整數，包含正負整數。

按照題目規則，先用暴力破解法的思維：找出所有連續子串的總和，再從中找出最大值即可。
這樣時間複雜度會是 O(n(n-1)/2) → O(n**2)。

至少能夠先有一個可行的方法，接著繼續思考有沒有比 O(n**2) 更少次的方法？

Follow up:
「If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.」

存在著 O(n) 的方法，不過題目希望能夠拆散數列再各個處理的方式(分治法)。

先提 O(n) 的方法。

既然是 O(n)，架構通常是一個「 for in 」，先寫上去再思考就好。需要回傳最大總和，所以可以命名一個 largestSum，最後 return largestSum。

如果要跑完一回就能找到答案，得在過程中記錄甚麼，或是判斷甚麼。

觀察一下數列，思考：遇到正的就累加起來，如果數列都是正整數，加完就是最大總和。那遇到負的部分呢？

這裡想到了累加，所以命名一個 accu 的變數，存放當前累加的結果。

如果遇到負整數，會使得當前累加會減少，所以先把當前的累加值保存下來，然後再把數字加上去。

將下來再做一些細部條件判斷，就能完成 O(n) 的解法。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:       
        largestSum = nums.pop(0) 
        nowAccu = largestSum 
        for num in nums:
            if num < 0:
                if nowAccu < 0: 
                    largestSum = max(largestSum, num)
                else:
                    largestSum = max(largestSum, nowAccu)
                    nowAccu += num
            else:
                if nowAccu < 0: nowAccu = num
                else: nowAccu += num                
        largestSum = max(largestSum, nowAccu) #最後一項
        return largestSum

至於分治法要怎麼寫？覺得麻煩就跳過。目前的概念是分成正負組合，再處理成各區域最大總和，從中回傳最大值。
。

給一個整數，按照十進位分切出各單個數字，這些數字的平方加總後，繼續分切…，如果最後總合等於 1，就是快樂數字。

好吧，到底哪裡快樂我也不知道。這依舊是一個非常簡單的題目。

可以分成三個步驟：
1.分切數字
2.數字平方和
3.判斷為1，否則回到步驟1.

要是碰到無限循環怎麼辦？把出現的數字記錄下來，只要有數字重複出現那就是無限循環。

用一個 memo ，字典或是集合(set)，之後用 in 就能看出是否有重複出現過。

還有更偷機的做法，就是把False的數字回收進memo。這樣會相當Happy。

class Solution:
    def isHappy(self, n: int) -> bool:           
        memo = {2: False, 3: False, 4: False, 5: False, 6: False, 8: False, 9: False,
                11: False, 12: False, 14: False, 15: False, 16: False, 17: False, 18: False,
                20: False, 21: False, 22: False, 24: False, 25: False, 26: False, 27: False,
                29: False, 30: False, 33: False, 34: False, 35: False, 36: False, 37: False,
                38: False, 39: False, 40: False, 41: False, 42: False, 43: False, 45: False,
                46: False, 47: False, 48: False, 50: False, 51: False, 52: False, 53: False,
                54: False, 55: False, 56: False, 57: False, 58: False, 59: False, 60: False,
                61: False, 62: False, 63: False, 64: False, 65: False, 66: False, 67: False,
                69: False, 71: False, 72: False, 73: False, 74: False, 75: False, 76: False,
                77: False, 78: False, 80: False, 81: False, 83: False, 84: False, 85: False,
                87: False, 88: False, 89: False, 90: False, 92: False, 93: False, 95: False,
                96: False, 98: False, 99: False, 106: False, 113: False, 117: False, 128: False,
                145: False, 162: False}  
        if n in memo: return False
        num2 = 0
        while n>1:
            if n in memo: return False
            else: memo[n]=None
            while n>0:
                num2 += (n % 10)**2
                n = n//10
            n, num2 = num2, 0
        return True

如果用字典是比較容易去偷機，如果不偷機，用集合會比較好增加資料(可以少打幾個字)。

class Solution:
    def isHappy(self, n: int) -> bool:           
        memo = {*''}      
        num2 = 0
        while n>1:
            if n in memo: return False
            else: memo.add(n)
            while n>0:
                num2 += (n % 10)**2
                n = n//10
            n, num2 = num2, 0
        return True

直方圖中最大的長方形面積

這題感到棘手，寫好的暴力破解法會超時，只能不斷看題目去領悟點甚麼。

找出最大面積不是件難事，要怎麼才能加速呢？

看了搜尋的兩前項，別人寫著遞增數列，找局部峰值，為什麼？到底有甚麼關係？

我簡單一句講明目的：「把這張直方圖分切出各個好處理的部分。」

在這個遞迴II章節，有一個部分是在說到把問題切碎，處理後再重組，得到答案。這就是需要這樣做的例子。

直方圖分解示意圖

把局部峰值也就是左大右小之處，切下去，左邊的值會遞減。得到一個遞增數列再往右搜尋。

碰到下一個峰值，往左遇到實際較高的直方，因為它已經被切進上一個遞增數列，所以可以忽視掉突出部分，維持一樣的值繼續遞減。

一旦變成遞增數列就可以很快速地找到最大面積。

把直方圖的每直方看成座標，遞增數列的右下角為原點，找出端點x和y絕對值相乘最大的就是該部分最大面積。

得到各部分的最大面積，再相互比較，就能得到直方圖中最大的長方形面積。

class Solution:
    """遞增數列"""
    def largestRectangleArea(self, heights) -> int:        
        if not heights: return 0    
        peaks = []
        p = None
        for idx, each in enumerate(heights):
            if p and each < p:
                peaks.append(idx-1)
            p = each
        peaks.append(n-1)

        maxAreas = []
        while peaks:
            # 從右而左搜尋
            endpoint = peaks.pop()      
            height = heights[endpoint]
            maxArea = 0
            for i in range(endpoint,-1,-1):
                width = endpoint+1-i
                height = min(height, heights[i])  
                maxArea = max(maxArea, width*height)
            maxAreas.append(maxArea)
        return max(maxAreas)

先找峰值，紀錄峰值出現在哪，最後一個也是峰值，最後從記錄找起一次把各種切出遞增數列找出最大長方形面積，再得到當中的最大值。

接下來就是優化了，對於一個 N 個數列，首先先減少遍例次數，求各遞增數列的最大面積可以放在找峰值的時候進行。

而且如果左右兩個點一樣高，可以忽略右邊的不計，減少要找的端點。在遍歷各端點時，如果剩下的最大可能面積沒辦法比較大，就可以跳出迴圈。

經過一番優化之後，就變成這樣。

這讓我深刻體會到，unfold 的好處在哪裡。如果沒有標上註解，可讀性遠遠不如上一個。

class Solution:
    """遞增數列"""
    def largestRectangleArea(self, heights) -> int:                
        if not heights: return 0
        def getMaxArea():
            area = 0            
            endpoint, height = hArray.pop()
            for i in range(len(hArray)-1,-1,-1):
                idx, h2 = hArray[i]                
                width = endpoint+1-idx
                height = min(height, h2)  
                area = max(area, width*height)
                if (endpoint+1)*height <= area:break                    
            return area


        n = len(heights) 
        hArray= []
        maxAreas = []

        for idx, h in enumerate(heights):
            if idx:                 
                if h < preH: #出現峰值，即刻求該遞增數列的最大面積
                    # 添加EndPoint
                    hArray.append((idx-1, preH))
                    # 搜尋當前面積
                    maxAreas.append(getMaxArea())
                    # 砍掉前面鋒值凸出的部分，最後要添加端點紀錄修改
                    stack = [idx, h]
                    while hArray and hArray[-1][1] > h:
                        stack[0] = hArray[-1][0] 
                        del hArray[-1]                    
                    hArray.append(stack)                    
                elif h > preH: #紀錄遞增變化
                    hArray.append((idx, h))
            else:
                hArray.append((idx, h))
            preH = h
        # 最後一搜,其中一個為最後一直方的左上端點 另一個是右上
        hArray.extend([(idx, h), (idx, h)])
        maxAreas.append(getMaxArea())        
        return max(maxAreas)

「Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.」

給一個數字 n ，要產生有 n 個左右成對「 ( ) 」的所有組合 。

說實在並不難，如果有想到左右成對的規則下，任何位置的左邊的 ( 數量一定得大於等於 )，不然會無法成對。

利用這特性，很快就可以寫出一個遞迴函數。

class Solution:
    def generateParenthesis(self, n):
        result = []
        def nextIdx(ln, rn, text):
            if ln == 0 and rn == 0:
                result.append(text)
            if ln - 1 >= 0:
                nextIdx(ln-1, rn, text+"(")
            if rn - 1 >= ln:
                nextIdx(ln, rn-1, text+")")
        nextIdx(n, n, "")
        return result

這是最直觀的寫法，速度也不錯。

換另外一種寫法 BackTracking。

class Solution:
    def generateParenthesis(self, n):
        """BackTracking"""
        result = []
        path = []
        def nextIdx(ln, rn):
            if ln == 0 and rn == 0:
                result.append("".join(path))
            if ln - 1 >= 0:
                path.append("(")
                nextIdx(ln-1, rn)
                del path[-1]
            if rn - 1 >= ln:
                path.append(")")
                nextIdx(ln, rn-1)
                del path[-1]

        nextIdx(n, n)
        return result

這種寫法就慢了一點，畢竟不會碰到下一步不合規則的判斷，如果真的盲選 ( 或 )寫入再判斷，應該只會更慢。

這題在子章節「unfold」，意思是不要寫得太精簡難懂。順著前進時，已經很習慣並不會覺得異樣，如果要倒退著，跟往前相比，就會覺得有點費力。

在前幾題有個求 1, 2, 3, …, N個數有 K 種組合情形。那題使用尾呼叫會比較快速，這題也來嘗試使用那種模式回答。

class Solution:
    def generateParenthesis(self, n):
        """尾呼叫"""
        def nextIdx(ln, rn, text):
            res = []
            if ln == 0 and rn == 0:
                res.append(text)
                return res
            if ln - 1 >= 0:
                res.extend(nextIdx(ln-1, rn, text+"("))
            if rn - 1 >= ln:
                res.extend(nextIdx(ln, rn-1, text+")"))
            return res        
        return nextIdx(n, n, "")

解數獨，非常地生活化。

這跟上一個 N-Queens 不同，你要直接修改數獨表，最後要是已經完成的狀態，這次要把答案紀錄好就不再刪除了。

而且一排排往下的概念並不好用，因為有些已經填滿了。

先把主架構寫出來，寫出一個回溯法函數(Backtracking)，把排換個概念換成層，而每一層就是單一個還沒下過的位置，靠著遍歷數獨表就可以知道有哪些位置。

接者就可以 Backtrack 一路往下搜尋。

當順利解出來時，就不會再有下一層，這時會出現報錯，出現別的情況，只要當這個情況出現時，回傳一個值，就可以用回傳值判斷要不要刪掉最後下過的位置，這樣就能阻止刪掉解法的最後一步。

class Solution:
    def solveSudoku(self, board) -> None:
        """
        Do not return anything, modify board in-place instead.
        """     
        def getCandidate(y, x):            
            Candidates = {}.fromkeys([str(i) for i in range(1,10)])            
            for x2 in range(9):                
                if board[y][x2] in Candidates: del Candidates[board[y][x2]]
            for y2 in range(9):                
                if board[y2][x] in Candidates: del Candidates[board[y2][x]]     
            for y2 in range(y//3*3, y//3*3+3):
                for x2 in range(x//3*3, x//3*3+3):
                    if board[y2][x2] in Candidates: del Candidates[board[y2][x2]]
            return Candidates.keys()             

        def nextStep(level):
            try:
                row, col, _ = stepPos[level]
                for num in getCandidate(row, col):
                    board[row][col] = num                  
                    if nextStep(level+1): 
                        return True
                    else:
                        board[row][col] = "." 
            except:
                return True

        stepPos = []  
        for y in range(9):
            for x in range(9): 
                if board[y][x] == ".":
                    stepPos.append((y, x, len(getCandidate(y, x))))

        stepPos.sort(key=lambda x: x[2])
        nextStep(0)

當中多了一作法，在找出所有可下位置時算出可能的數字數，接著再用可能數字數從小到大排序，就會從最少可能組合開始下起，這就像我們玩數獨一般，會從最少可能性的地方找起。

一看可以優化，用memo紀錄各col各row各area的所有數字，這樣用 in 找值的時候，能夠最快效率。

沒有排序問題，也沒有設值需求，然後需要求出兩數組差(123456789 與 各col各row各area)，所以使用集合 set ，這樣就能方便計算。

剛好可以安插在找所有可下位置的時候，將各col各row各area的所有數字都添加進去。

class Solution:
    def solveSudoku(self, board) -> None:
        """
        Do not return anything, modify board in-place instead.
        """     
        Candidates = {*'123456789'}
        memoCol = {}
        memoRow = {}
        memoArea = {}
        for i in range(9):
            memoCol[i] = set()
            memoRow[i] = set()
            memoArea[i] = set()

        def getCandidate(y, x):            
            return Candidates - memoArea[x//3+y//3*3] - memoCol[x] - memoRow[y]          

        def nextStep(level):
            try:
                row, col = stepPos[level]
                for num in getCandidate(row, col):
                    memoCol[col].add(num)   
                    memoRow[row].add(num)    
                    memoArea[col//3+row//3*3].add(num)   
                    board[row][col] = num                
                    if nextStep(level+1): 
                        return True
                    else:
                        board[row][col] = "."                   
                        memoCol[col].discard(num)
                        memoRow[row].discard(num)
                        memoArea[col//3+row//3*3].discard(num)
            except:
                return True

                
        stepPos = []  
        for y in range(9):
            for x in range(9): 
                v = board[y][x]
                if v == ".":
                    stepPos.append((y,x))
                else:   
                    memoCol[x].add(v)       
                    memoRow[y].add(v)   
                    memoArea[x//3+y//3*3].add(v)   

        nextStep(0)

給一串非空整數字串列，每個元素會重複兩次，只有一個只出現一次，找出來。

這題非常簡單，一開始就有各種解法。不過我當作可能重複不只兩次，用這樣的前提寫出：

class Solution:    
    def singleNumber(self, nums: List[int]) -> int:
        memo = {}
        memo2 = {}
        for num in nums:
            if num in memo2:
                continue                    
            else:
                if num in memo:
                    del memo[num]
                    memo2[num] = 0
                    continue
                memo[num] = num   
        
        for key in memo: return memo[key]

我在想，有沒有甚麼只循環過一遍就能得到解法？不要有跑完N兩次或以上。看了前段班解法，回頭看題目才知道頂多重複兩次。(又再一次沒有看清楚題目

我的解法也只會跑過一次N。

偷看大神的解答，覺得這個相當精巧。

class Solution:       
    def singleNumber(self, nums: List[int]) -> int:        
        count = 0
        for num in nums:
            count ^= num            
        return count

運用「 ^= 」，重複的數字會重複兩次，於是會抵消掉，最後的值會等於只出現一次的數字。這方法不需要排序，也不用比較，也只需要遍歷串列過一次。

求出在 N * N的棋盤放上 N 個彼此無法互吃的解法數量。

最直觀的就是暴力解法，若 N = 4，就會有 16 格，於是第一步的可能下法就會有16種。

取出前面的結果，找出第二步下法的地方，得到第二步符合規則的所有下法，依序往下傳。

傳到第 N 步下完後，剩下多少種不相同的可行下法就是解答。(這樣會找到重複解。

這種暴力解法多計算了不需要的「流程」，每一步先後順序都沒有差。

換一種想法，有沒有更快速的下法？

每排上面一定有一個皇后，於是可以逐排安排皇后。

在逐排之下，要是該欄可以放皇后，就往下排從頭搜尋，到底則次數+1，不行則取走上排的皇后，退回上排再往下一欄搜尋。

回去偷看一下範例，才想到這樣的解法。(誰叫我當初選擇跳過不看呢，呵呵。

class Solution:
    def totalNQueens(self, n: int) -> int:
        def is_not_under_attack(Queens, y, x):
            for queen in Queens:
                qy, qx = queen
                if qy == y: return False
                if qx == x: return False
                if abs(qx-x) == abs(qy-y): return False
            return True

        Queens = [] 
        row, col = 0, 0 
        count = 0
        while col <= n:
            #print(row,col)
            if col == n:
                # remove queen
                if Queens:
                    row, col = Queens.pop()
                    col = col+1             
                else: break                    
            elif row == n: 
                count += 1
                row, col = Queens.pop()
                col = col+1      
            elif is_not_under_attack(Queens, row, col):
                # place queen
                Queens.append((row,col))
                row, col = row + 1, 0              
            else:
                col += 1

        return count

當走到最後一排，順利放完就會觸發超出排數，這代表順利找到一個解法，成功將 N 個皇后放在棋盤上。取走上一個的皇后，然後繼續搜尋。

當走到最後一欄，超出欄數，就代表該排無法放置皇后，取走上一個皇后。如果在第 0 排，沒有皇后可取，就跳出迴圈，回傳計數。

有了這種思路，解答速度就會有所保證，接下來就是優化，讓速度更快速。

class Solution:
    def totalNQueens(self, n: int) -> int:
        result = []
        queens, xy_sum, xy_dif = {}, {}, {}
        def searchNext(row):
            if row == n:
                result.append("")
            else:
                for col in range(n):     
                    xyS = row + col
                    xyD = row - col
                    if not col in queens and not xyS in xy_sum and not xyD in xy_dif:
                        queens[col] = xy_sum[xyS] = xy_dif[xyD] = None
                        searchNext(row+1)
                        del queens[col], xy_sum[xyS], xy_dif[xyD]                                               
        searchNext(0)     
        return len(result)

用了一個串列 result 接收結果，要解法可以添加 queens 當下所有鍵，只要解法數目最後用 len() 就能得到所有解的數目，要添加甚麼到result就隨便喜好。

這不得不說是參考前段班大神的解法，用xy相加與相減就能快速找到是否在斜線上，由於是一排排的下，所以也不會有同排(同y)的狀況要排除。

考慮到「查值是否存在」的速度差異，使用字典比起串列還快不少，所以都換成字典，畢竟只會使用 in 去查鍵是否存在，該鍵的值是甚麼就不重要。

在串列使用 append() 添加比 + 還快，用 + 會回傳一個新串列，如果沒有需要新生成或是有別的辦法替代，先用 append() 再傳會比較快。

這優化解法一開始就會直接到深處開始，不像前面的解法是一排排往下找，相快速度跟代碼長度就會快很多跟少很多。找完就刪掉最後一項(最後下的Queen)然後往右下一欄，走完所有欄，就會回上層繼續。

今天碰到這一題，卡關很久，來記錄一下。

二元樹算是目前遇到稍微棘手級別，棘手級別目前只有莫隊算法，還沒有花時間去弄通它。

這一題屬於「遞迴」的範圍之內，給一個數字，要你回傳有相同節點數的所有可能。

一開始直覺，就是把數列排序，取一個數字，由於是二元樹，左邊皆小於該節值，右邊則大於，所以左邊樹結就是該數字左邊的所有項目組合，右邊等同處理。

接下來，要設一個節點，該節點左邊的等於左邊的遞迴結果，右邊等同處理。

就在這裡卡了一整個下午，之前相關的遞迴幾乎是把 node 往下傳，然後回傳也是 node。如果node 傳下來，左右邊的有數種組合，但是根節點只有一個，左邊要哪一個組合？右邊要哪一個組合？還是一開始就傳許多根節？直接以根結點指定左右是不可行的。

由上而下的想法是行不通的，這題需要的是由下而上。但一開始的想法碰壁之後就一直在思考由上而下的想法，直到最後才又回歸一開始的寫法改進。

既然有各種組合，就不能回傳節點，要能涵蓋各種組合，首選是用串列。

將回傳改成串列，左右邊會各有一個串列包含數種組合，最後再左右合併，往頭傳遞。這點順利改好後，一切就順多了。

用兩個迴圈跑完所有的左右組合，這時才把該子二元樹根節實例化，就不會有共同祖先的問題，也能產出對應數量且沒有重疊的子二元樹根節。

如果左或右沒有組合，就需要換成一個 [None] 來代替，沒有組合的那邊就只會是 None 也算一種組合。

寫完整理後就如下：

class Solution:
    def generateTrees(self, n: int):
        def nextNode(ns):
            NTS = []
            for i in range(len(ns)):          
                lntree = nextNode(ns[:i])               
                rntree = nextNode(ns[i+1:])
                if not lntree: lntree = [None]
                if not rntree: rntree = [None]
                for l in lntree:
                    for r in rntree:
                        root = TreeNode(ns[i])
                        root.left, root.right = l, r
                        NTS.append(root)
            return NTS
        return nextNode(list(range(1,n+1)))

相當地直觀，但是效率並不到前中段班的。

前段班在代碼中加上 memo，將組合儲存起來，如果有就優先返回該值，沒有才遞迴並建立。

在一個區間的組合是固定的，就像1234組合起來，只會有同一種各組合可能。根如果為5、6、7…，1234就會被重複計算到，有memo就不用再算一次。

索引就以左界右界，建立二維串列儲存。

class Solution:
    def generateTrees(self, n: int):
        memo = [[None]*n for _ in range(n)]
        
        def nextNode(l, r):
            if l > r: return [None]
            elif memo[l][r]: return memo[l][r]

            NTS = []
            for i in range(l,r+1, 1):    
                print(l,  i, i+1, r,range(l,r+1, 1))
                lntree = nextNode(l, i-1)               
                rntree = nextNode(i+1, r)                 
                for lt in lntree:
                    for rt in rntree:
                        root = TreeNode(i+1)
                        root.left, root.right = lt, rt
                        NTS.append(root)
            memo[l][r] = NTS
            return NTS
        
        if n == 0: return []
        return nextNode(0, n-1)