图论【52-55】
200.岛屿数量
深度优先搜索
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
visited = [[False] * n for _ in range(m)]
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)] # 四个方向,左,右,下,上
result = 0
def dfs(x, y):
for d in dirs:
nextx = x + d[0]
nexty = y + d[1]
if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n: # 越界了,直接跳过
continue
if not visited[nextx][nexty] and grid[nextx][nexty] == '1': # 没有访问过的同时是陆地的
visited[nextx][nexty] = True
dfs(nextx, nexty)
for i in range(m):
for j in range(n):
if not visited[i][j] and grid[i][j] == '1': #没有参观过& 陆地
visited[i][j] = True
result += 1 # 遇到没访问过的陆地,+1
dfs(i, j) # 将与其链接的陆地都标记上 true
return result
994.腐烂的句子
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
row, col, time = len(grid), len(grid[0]), 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
queue = []
#把腐烂的橘子加到队列
for i in range(row):
for j in range(col):
if grid[i][j] == 2:
queue.append((i, j, time))
# 广度搜索
while queue:
i, j, time = queue.pop(0)
for di, dj in directions:
if 0 <= i + di < row and 0 <= j + dj < col and grid[i + di][j + dj] == 1:
grid[i + di][j + dj] = 2
queue.append((i + di, j + dj, time + 1))
# 如果仍然有新鲜橘子,返回-1
for row in grid:
if 1 in row:
return -1
return time
207.课程表
from collections import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
indegrees = [0 for _ in range(numCourses)]
adjacency = [[] for _ in range(numCourses)]
queue = deque()
# 得到每个节点的入度表,
for cur, pre in prerequisites:
indegrees[cur] += 1
adjacency[pre].append(cur)
# 得到所有入度为0的节点【没有结点能得到入度为0的节点】
for i in range(len(indegrees)):
if not indegrees[i]:
queue.append(i)
# BFS
while queue:
pre = queue.popleft()
numCourses -= 1
for cur in adjacency[pre]:
indegrees[cur] -= 1
if not indegrees[cur]:
queue.append(cur)
return not numCourses
208.实现True(前缀树)
isWord 表示从根节点到当前节点为止,该路径是否形成了一个有效的字符串。
children 是该节点的所有子节点。
class Node(object):
def __init__(self):
self.children = collections.defaultdict(Node)
self.isword = False
class Trie(object):
def __init__(self):
self.root = Node()
def insert(self, word):
current = self.root
for w in word:
current = current.children[w]
current.isword = True
def search(self, word):
current = self.root
for w in word:
current = current.children.get(w)
if current == None: #路径断了
return False
return current.isword
def startsWith(self, prefix):
current = self.root
for w in prefix:
current = current.children.get(w)
if current == None:
return False
return True
回溯【56-63】
46.全排列
class Solution:
def permute(self, nums):
result = []
self.backtracking(nums, [], [False] * len(nums), result)
return result
def backtracking(self, nums, path, used, result):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
self.backtracking(nums, path, used, result)
path.pop()
used[i] = False
78.子集
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
self.backtracking(nums, 0, [], res)
return res
def backtracking(self, nums, startindex, path, res):
res.append(path[:])
for i in range(startindex, len(nums)):
path.append(nums[i])
self.backtracking(nums, i+1, path, res)
path.pop()
17.电话号码的字母组合
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
self.mapping = {2:'abc', 3:'def', 4:'ghi',
5:'jkl',6:'mno',7:'pqrs',8:'tuv',9:'wxyz'}
res = []
if len(digits)==0:
return res
self.backtracking(digits, 0, [],res)
return res
def backtracking(self, digits, startindex, path, res):
if len(path) == len(digits):
res.append(''.join(path)) #将结果转换成str
return
#树宽是mapping[index],树高是len(digits)
ss = self.mapping[int(digits[startindex])]
for i in ss:
path.append(i)
self.backtracking(digits,startindex+1,path,res)
path.pop()
39.组合总和
candidate元素不重复,一个元素可以重复选取
'''控制重复选取'''
self.backtracking(candidates, i, path, res, target)
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
self.backtracking(candidates, 0, [],res,target)
return res
def backtracking(self, candidates, startindex, path, res, target):
if target == 0:
res.append(path[:])
return
if target < 0:
return
for i in range(startindex, len(candidates)):
path.append(candidates[i])
target -= candidates[i]
self.backtracking(candidates, i, path, res, target)
path.pop()
target += candidates[i]
22.括号生成
什么时候可以向下搜索:
- 插入数量 < n
- 左括号插入数量 > 右括号数量
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
self.backtracking(n, 0, 0, '', res)
return res
def backtracking(self, n, left, right, path, res):
if left == n and right == n:
res.append(path)
return
if left<n:
self.backtracking(n, left+1, right, path+'(', res )
if left > right :
self.backtracking(n, left, right+1, path+')', res)
79.单词搜索
递归参数
当前元素在矩阵 board 中的行列索引 i 和 j ,当前目标字符在 word 中的索引 k 。
:
终止条件
- 返回 false : (1) 行或列索引越界 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过
- 返回 true : k = len(word) - 1 ,即字符串 word 已全部匹配。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i, j, k):
if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]:
return False
if k == len(word) - 1:
return True
board[i][j] = '' #代表当前元素已经访问过,防止反复访问
res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
board[i][j] = word[k]
return res
#遍历i,j,找到word[0]
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i, j, 0): #当前在board[i][j],单词在word[k]
return True
return False
131.分割回文串
class Solution:
def partition(self, s: str) -> List[List[str]]:
res =[]
self.backtracking(s, 0, [], res)
return res
def backtracking(self, s, startindex, path, res):
if startindex == len(s):
res.append(path[:])
return
for i in range(startindex, len(s)):
ss = s[startindex:i+1]
if ss == ss[::-1]: #是回文, 再递归
path.append(ss)
self.backtracking(s, i+1, path, res )
path.pop()
51. N 皇后
棋盘的宽度就是for循环的长度,递归的深度就是棋盘的高度,这样就可以套进回溯法的模板里了。
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
result = [] # 存储最终结果的二维字符串数组
chessboard = ['.' * n for _ in range(n)] # 初始化棋盘
self.backtracking(n, 0, chessboard, result) # 回溯求解
return [[''.join(row) for row in solution] for solution in result] # 返回结果集
def backtracking(self, n: int, row: int, chessboard: List[str], result: List[List[str]]) -> None:
if row == n:
result.append(chessboard[:]) # 棋盘填满,将当前解加入结果集
return
for col in range(n):
if self.isValid(row, col, chessboard):
chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:] # 放置皇后
self.backtracking(n, row + 1, chessboard, result) # 递归到下一行
chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:] # 回溯,撤销当前位置的皇后
def isValid(self, row: int, col: int, chessboard: List[str]) -> bool:
# 检查列
for i in range(row):
if chessboard[i][col] == 'Q':
return False # 当前列已经存在皇后,不合法
# 检查 45 度角是否有皇后
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if chessboard[i][j] == 'Q':
return False # 左上方向已经存在皇后,不合法
i -= 1
j -= 1
# 检查 135 度角是否有皇后
i, j = row - 1, col + 1
while i >= 0 and j < len(chessboard):
if chessboard[i][j] == 'Q':
return False # 右上方向已经存在皇后,不合法
i -= 1
j += 1
return True # 当前位置合法