单词搜索
class Solution: def exist(self, board: List[List[str]], word: str) -> bool: self.m = len(board) self.n = len(board[0]) for i in range(self.m): for j in range(self.n): if board[i][j] == word[0]: if self.check(board,i,j,word, 0): return True return False def check(self, board, i, j, word, index): if i < 0 or i >= self.m or j < 0 or j >= self.n or board[i][j] != word[index]: return False if index == len(word) - 1: return True # 把当前坐标的值保存下来，为了在最后复原,回溯 t = board[i][j] # 然后修改当前坐标的值，避免之前找到过的元素又被找到一次 board[i][j] = '.' res = self.check(board,i,j-1,word,index + 1) or self.check(board,i,j+1,word,index + 1) or self.check(board,i-1,j,word,index + 1) or self.check(board,i+1,j,word,index + 1) board[i][j] = t return res
N皇后问题
class Solution: def solveNQueens(self, n: int) -> List[List[str]]: def isValid(row, col): for i in range(row): for j in range(n): # 注：左斜对角线上，同一条斜线上的每个位置满足行下标与列下标之差相等 # 注：右斜对角线上，同一条斜线上的每个位置满足行下标与列下标之和相等 if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col): return False return True def backtrack(board, row): if row >= n: cur_res = [''.join(row) for row in board] res.append(cur_res) return for i in range(n): if isValid(row, i, board): board[row][i] = 'Q' backtrack(board, row+1) board[row][i] = '.' res = [] board = [['.'] * n for _ in range(n)] backtrack(board,0) return res # 优化，通过集合记录之前放置过元素的正向对角线，负向对角线，及列，判断当前点是否在集合中，在的话说明不满足要求 def solveNQueens(self, n: int) -> List[List[str]]: def isValid(row, col): # 注：左斜对角线上，同一条斜线上的每个位置满足行下标与列下标之差相等 # 注：右斜对角线上，同一条斜线上的每个位置满足行下标与列下标之和相等 if col in col_hash or (row + col) in pie_hash or (row-col) in na_hash: return False return True def backtrack(board, row): if row >= n: cur_res = [''.join(row) for row in board] res.append(cur_res) return for col in range(n): if isValid(row, col, board): board[row][col] = 'Q' pie_hash.add(row + col) na_hash.add(row - col) col_hash.add(col) backtrack(board, row+1) board[row][col] = '.' pie_hash.remove(row + col) na_hash.remove(row-col) col_hash.remove(col) res = [] board = [['.'] * n for _ in range(n)] pie_hash = set() na_hash = set() col_hash = set() backtrack(board,0) return res
判断有效数独
class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: row_set = [set() for _ in range(9)] col_set = [set() for _ in range(9)] square_set = [[set() for _ in range(3)] for _ in range(3)] #3*3 for i in range(9): for j in range(9): if board[i][j] in row_set[i] or board[i][j] in col_set[j] or board[i][j] in square_set[i//3][j//3]: return False if board[i][j] != '.': row_set[i].add(board[i][j]) col_set[j].add(board[i][j]) square_set[i//3][j//3].add(board[i][j]) return True
解数独
解法一
class Solution: def solveSudoku(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ nums = {"1", "2", "3", "4", "5", "6", "7", "8", "9"} row = [set() for _ in range(9)] col = [set() for _ in range(9)] palace = [[set() for _ in range(3)] for _ in range(3)] # 3*3 blank = [] # 初始化，按照行、列、宫 分别存入哈希表 for i in range(9): for j in range(9): ch = board[i][j] if ch == ".": blank.append((i, j)) else: row[i].add(ch) col[j].add(ch) palace[i//3][j//3].add(ch) def dfs(n): if n == len(blank): return True i, j = blank[n] rst = nums - row[i] - col[j] - palace[i//3][j//3] # 剩余的数字 ### rst = nums - (row[i] | col[j] | palace[i//3][j//3]) if not rst: return False for num in rst: board[i][j] = num row[i].add(num) col[j].add(num) palace[i//3][j//3].add(num) if dfs(n+1): return True row[i].remove(num) col[j].remove(num) palace[i//3][j//3].remove(num) dfs(0)
解法二
class Solution: def solveSudoku(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ self.board = board self.solve() def findUnassigned(self): for row in range(9): for col in range(9): if self.board[row][col] == ".": return row, col return -1, -1 def solve(self): row, col = self.findUnassigned() #no unassigned position is found, puzzle solved if row == -1 and col == -1: return True for num in ["1","2","3","4","5","6","7","8","9"]: if self.isSafe(row, col, num): self.board[row][col] = num if self.solve(): return True self.board[row][col] = "." return False def isSafe(self, row, col, ch): boxrow = row - row%3 boxcol = col - col%3 if self.checkrow(row,ch) and self.checkcol(col,ch) and self.checksquare(boxrow, boxcol, ch): return True return False def checkrow(self, row, ch): for col in range(9): if self.board[row][col] == ch: return False return True def checkcol(self, col, ch): for row in range(9): if self.board[row][col] == ch: return False return True def checksquare(self, row, col, ch): for r in range(row, row+3): for c in range(col, col+3): if self.board[r][c] == ch: return False return True
