解數獨，非常地生活化。

這跟上一個 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)