Backtrack

51. & 52. N Queens

51. N-Queens & 52. N-Queens 這個題目也是透過棋類遊戲的規則所設計出的一個回溯法的問題，如同前言所示，棋類遊戲需要快速的找出幾個可行解，接著在心中的棋盤放下那個旗子，並繼續往下推演，如果推演下去發現並不好或是無法滿足遊戲規則，就換下一個可行解來找。皇后問題的困難點在於，題目有兩個大方向去思考，第一個是回溯法的邏輯要怎麼處理，第二個是要怎麼處理該棋盤位置皇后是否可以放上去，而這兩個處理的方法又有部份交疊，所以讓這個題目的細節不怎麼好處理。首先先看一眼皇后在棋盤上的的規則 1. 同一行不能有皇后，在程式裡面很好透過行的遍歷來處理 2. 同一列不能有皇后，在程式裡面很好透過列的遍歷來處理 3. 主對角線上不能有皇后，這沒有這個好處理，晚點再來討論 4. 反對角線上不能有皇后，這沒有這個好處理，晚點再來討論了解以上的規則後，就可以開始想我們會怎麼樣的放置皇后，這裡請先忽略第三第四個條件，假設我們在一個位置上放置了皇后，只考慮該行和該列就再也不能放置，我們就可以用以下的方式來走訪。下面的走訪方式是一列一列的方式往下找下一個可以放的位置，走到該

31. Next Permutation

31. Next Permutation 題目是給定一個數字，要使用這個數字有使用到的數字，並透過排列組合，找到下一個排列組合比現在這個數字還大，可是卻是所有可行的排列組合中最小的，如果說現在的這個數字已經是排列組合中最大的數字，那我們就回傳排列組合中最小的數字。這個排列也可以稱做一種字典排列。我的第一個直覺想法是，既然是排列組合題目，那我就把所有的排列組合窮舉出來，並且由小到大的排序，找出哪個數字和目前的數字相同，下一個數字就會是字典數了，當然如果是最大的數字，那就返回最小的數，題目還有要求要只在記憶體修改，那是這個並不是太困難的事情。回溯法 class Solution: def nextPermutation(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ sortedNums = sorted(nums) res = []

247. Strobogrammatic Number II

247. Strobogrammatic Number II 根據 Leetcode 的資料，這一題是 Google 常見的考題，這一題程式是很好寫，可是最困難的是這個問題的邏輯並不好想。題目給的 n 的長度最大是到 14 ，看起來很小，不過這個數字真正代表的是最大的搜索區間是落在是 \([10^{13}, 10^{14}]\) 的，這個 n 是一個非常非常大的數字！如果已經做過題目 246. Strobogrammatic Number ，的確可以想到用暴力解找到。演算法的題目寫多了就會可以快速觀察到，如果今天我們要找的一個數字，是非常稀缺的話，暴力法一定不是一個好解法，像是 204. Count Primes 這題，質數是一個很難找的數字，尤其數字越大會越難找到，這一題最大的 n 可以是 14，不過在 14 位數的情況，大約是幾十兆的數字中，

1219. Path with Maximum Gold

1219. Path with Maximum Gold class Solution: def getMaximumGold(self, grid: List[List[int]]) -> int: rows = len(grid) cols = len(grid[0]) ans = float('-inf') directions = [(1,0),(-1,0),(0,1),(0,-1)] def backtrack(curr, row, col): nonlocal ans if grid[row][col] == 0: return current_gold

425. Word Squares

425. Word Squares class Solution: def wordSquares(self, words: List[str]) -> List[List[str]]: square_width = len(words[0]) trie = {} res = [] for index, word in enumerate(words): node = trie for char in word: if char in node: node = node[char] else: node[char] = { '#': [] } node = node[char]

212. Word Search II

212. Word Search II 這一題是 79. Word Search 的進階版，原先我們要找的是給定一個字串，看這個一個字串是否存在，這題是給定很多字串，要看哪些字串存在？第一個直覺的想法是，那就把第一題的解法把字串一個一個檢查就好，但是這樣的方法很明顯會超時。 class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: rows = len(board) cols = len(board[0]) directions = [(1,0),(-1,0),(0,1),(0,-1)] def backtrack(r,

79. Word Search

79. Word Search 這一題用的是回溯算法，接著從矩陣的每個字元開始出發，首先會先判斷兩件事情： 1. 是否超過邊界？ 2. 該座標的是不是目標字串的第一個字？如果是的話才會開始向下搜尋，向下搜尋的時候要注意兩件事情 1. 要記得將目前的座標標記成為已造訪 2. 向下傳遞時，是傳遞目標字串的 word[1:] 終止條件是字串搜尋完畢 class Solution: def exist(self, board: List[List[str]], word: str) -> bool: rows = len(board) cols = len(board[0]) directions = [(1,0),(-1,0),(0,1),(0,-1)] def