前言

• 回溯回溯回溯！早上整理檔案竟然用了桶排序，不愧是算法狂魔們

79. 單詞搜索 - 力扣（LeetCode）

• DFS

  • class Solution:def exist(self, board: List[List[str]], word: str) -> bool:m, n = len(board), len(board[0])# used = [[0] * n for _ in range(m)]word_len = len(word)self.flag = Falsedef dfs(x, y, index):if index == word_len:self.flag = Truereturnfor x0, y0 in ((x-1, y), (x, y-1), (x+1, y), (x,y+1)):# if 0 <= x0 < m and 0 <= y0 < n and board[x0][y0] == word[index] and used[x0][y0] == 0:if 0 <= x0 < m and 0 <= y0 < n and board[x0][y0] == word[index]:# used[x0][y0] = 1board[x0][y0] = ''           # 置為空字符避免重復dfs(x0, y0, index+1)board[x0][y0] = word[index]  # 回溯# used[x0][y0] = 0for i in range(len(board)):for j in range(len(board[0])):if board[i][j] == word[0]:# used[i][j] = 1board[i][j] = ''        # 置為空字符避免重復dfs(i, j, 1)board[i][j] = word[0]   # 回溯# used[i][j] = 0if self.flag: return self.flag  # 剪枝，找到一條就可以退出了return self.flag

?131. 分割回文串 - 力扣（LeetCode）

• 回溯（分割）

  • 
  • 動規判斷回文串的方法看【代碼隨想錄】刷題筆記Day54-CSDN博客

  • class Solution:def partition(self, s: str) -> List[List[str]]:# # 雙指針判斷是否回文串# def isPalindrome(s, left, right):#     while s[left] == s[right]:#         left += 1#         right -= 1#         if left >= right: return True#     return False  # # 優化：動規法判斷回文串# def computePalindrome(s, isPalindrome):#     for i in range(len(s) - 1, -1, -1):  # 需要倒序計算，保證在i行時，i+1行已經計算好了#         for j in range(i, len(s)):#             if j == i:#                 isPalindrome[i][j] = True#             elif j - i == 1:#                 isPalindrome[i][j] = (s[i] == s[j])#             else:#                 isPalindrome[i][j] = (s[i] == s[j] and isPalindrome[i+1][j-1]) # isPalindrome = [[False] * len(s) for _ in range(len(s))]  # 初始化isPalindrome矩陣# computePalindrome(s, isPalindrome)  # 到時候直接查，isPalindrome[i][j]代表s[i:j]閉區間是否是回文字串path = []res = []n = len(s)def backtrack(start = 0):if start == n:res.append(path[:])for i in range(start, n):# if isPalindrome(s, start, i):  # 利用雙指針判斷回文if s[start:i+1] == s[start:i+1][::-1]:  # 利用python特性直接判斷回文# if isPalindrome[start][i]:   # 利用動規預先存好的dp數組判斷回文path.append(s[start:i+1])backtrack(i+1)path.pop()backtrack()return res

分割補充

?93. 復原 IP 地址 - 力扣（LeetCode）

• 

• class Solution:def restoreIpAddresses(self, s: str) -> List[str]:# 送進來的是1~3位字符串def isValid(s):if s[0] != '0' and 1 <= int(s) <= 255:return Trueelif len(s) == 1 and int(s) == 0:return Trueelse:return Falsepath = []res = []n = len(s)def backtrack(start = 0):if start == n and len(path) == 4:res.append(".".join(path))for i in range(start, start + 3):  # 只要往后3位if i < n:  # 不要越界# 剪枝：剩余字符數 > 3*割完后剩下要割的數量if n - i - 1 > 3 * (3 - len(path)):continuetmp = s[start:i+1]if isValid(tmp):path.append(tmp)backtrack(i+1)path.pop()backtrack()return res

?51. N 皇后 - 力扣（LeetCode）

• 回溯（占坑）

  • 自己寫出來的，成就感max，雖然蠢但是還想記錄下來

  • class Solution:def solveNQueens(self, n: int) -> List[List[str]]:used = [[0] * n for _ in range(n)]  # 0代表可放，大于1表示不可放path = []res = []def backtrack(row = 0):if row == n:res.append(path[:])returnfor col in range(n):if used[row][col] == 0:tmp = col*'.' + 'Q' + (n-col-1)*'.'path.append(tmp) # 往下占坑l_col = r_col = colfor row_now in range(row+1, n):l_col -= 1  r_col += 1  used[row_now][col] += 1  # 正下方if l_col >= 0: used[row_now][l_col] += 1  # 左斜向下if r_col <= n-1: used[row_now][r_col] += 1  # 右斜向下# 進入下一行backtrack(row+1)# 回溯退坑l_col = r_col = colfor row_now in range(row+1, n):l_col -= 1r_col += 1used[row_now][col] -= 1  # 正下方if l_col >= 0: used[row_now][l_col] -= 1  # 左斜向下if r_col <= n-1: used[row_now][r_col] -= 1  # 右斜向下path.pop()backtrack()return res

• ?回溯（合法）

  • class Solution:def solveNQueens(self, n: int) -> List[List[str]]:# 從上往下放棋子# 按照row從小到大放置皇后board = [['.'] * n for _ in range(n)]res = []# 表示board中小于row的那些行（row上面的那些行）已經放置皇后了# 這一步開始往第row行放皇后def backtrack(row):n = len(board)# 如果到最后一行了，則將結果添加到res里if row == n:tmp = [''.join(i) for i in board]res.append(tmp)returnfor col in range(n):if not self.isValid(board, row, col):continueboard[row][col] = 'Q'backtrack(row + 1)board[row][col] = '.'backtrack(0)return res # 查看是否可以在board[row][col]的位置放置皇后def isValid(self, board, row, col):n = len(board)# 查看上方是否有Qfor i in range(row):if board[i][col] == 'Q':return False# 查看右上方是否有Qfor i, j in zip(range(row - 1, -1, -1), range(col + 1, n, 1)):if board[i][j] == 'Q':return False# 查看左上方是否有Qfor i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):if board[i][j] == 'Q':return Falsereturn True 

棋盤補充?

37. 解數獨 - 力扣（LeetCode）

• 回溯（雙重遞歸 + 合法判斷）

  • class Solution:def solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""self.backtracking(board)def backtracking(self, board: List[List[str]]) -> bool:# 若有解，返回True；若無解，返回Falsefor i in range(len(board)): # 遍歷行for j in range(len(board[0])):  # 遍歷列# 若空格內已有數字，跳過if board[i][j] != '.': continuefor k in range(1, 10):if self.is_valid(i, j, k, board):board[i][j] = str(k)if self.backtracking(board): return Trueboard[i][j] = '.'# 若數字1-9都不能成功填入空格，返回False無解return Falsereturn True # 有解def is_valid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool:# 判斷同一行是否沖突for i in range(9):if board[row][i] == str(val):return False# 判斷同一列是否沖突for j in range(9):if board[j][col] == str(val):return False# 判斷同一九宮格是否有沖突start_row = (row // 3) * 3start_col = (col // 3) * 3for i in range(start_row, start_row + 3):for j in range(start_col, start_col + 3):if board[i][j] == str(val):return Falsereturn True

• 回溯（剩余數字set取交集）?

  • class Solution:def solveSudoku(self, board: List[List[str]]) -> None:row = [set(range(1, 10)) for _ in range(9)]  # 行剩余可用數字col = [set(range(1, 10)) for _ in range(9)]  # 列剩余可用數字block = [set(range(1, 10)) for _ in range(9)]  # 塊剩余可用數字empty = []  # 收集需填數位置for i in range(9):for j in range(9):if board[i][j] != '.':  # 更新可用數字val = int(board[i][j])row[i].remove(val)col[j].remove(val)block[(i // 3)*3 + j // 3].remove(val)else:empty.append((i, j))def backtrack(iter=0):if iter == len(empty):  # 處理完empty代表找到了答案return Truei, j = empty[iter]b = (i // 3)*3 + j // 3for val in row[i] & col[j] & block[b]:  # set取交集row[i].remove(val)col[j].remove(val)block[b].remove(val)board[i][j] = str(val)if backtrack(iter+1):return Truerow[i].add(val)  # 回溯col[j].add(val)block[b].add(val)return Falsebacktrack()

后言

• 回溯搞定！！感覺模板已經有印在腦子里了，希望下次遇到還能寫。另外，自己寫出N皇后和看最后很優雅的數獨set的方法真的顱內高潮了，這就是刷題的正反饋吧！?