Backtrack

51. & 52. N Queens

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

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 = []
Gary Lai

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 位數的情況,大約是幾十兆的數字中,
Gary Lai

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,
Gary Lai

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
Gary Lai