练习
37. 解数独
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
rows = [[False] * 9 for _ in range(9)]
cols = [[False] * 9 for _ in range(9)]
cell = [[False] * 9 for _ in range(9)]
cell_i = lambda i, j: (i // 3) * 3 + (j // 3)
for i in range(9):
for j in range(9):
if board[i][j] == '.': continue
n = int(board[i][j]) - 1
rows[i][n] = cols[j][n] = cell[cell_i(i, j)][n] = True
def dfs(x, y):
if x == 9: return True
if y == 9: return dfs(x + 1, 0)
if board[x][y] != '.': return dfs(x, y + 1)
for i in range(9):
if not rows[x][i] and not cols[y][i] and not cell[cell_i(x, y)][i]:
rows[x][i] = cols[y][i] = cell[cell_i(x, y)][i] = True
board[x][y] = str(i + 1)
if dfs(x, y + 1): return True
rows[x][i] = cols[y][i] = cell[cell_i(x, y)][i] = False
board[x][y] = '.'
return False
dfs(0, 0) 39. 组合总和
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
def dfs(cur, t):
if t < 0: return
if t == 0: ans.append(cur); return
for x in candidates:
if (len(cur) > 0 and cur[-1] or 0) <= x <= t: dfs(cur + [x], t - x)
dfs([], target)
return ans 题目说如果两个结果中每个所选数字的数量都相同，那么这两个结果等价。也就是说不要求顺序，每一个结果都是 set 而非 list，只不过用 list 存放；是组合而非排列。
中间的条件 (len(cur) > 0 and cur[-1] or 0) <= x <= t 保证产生的序列是递增的，这样选择的是唯一的。
40. 组合总和 II
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans = set()
n = len(candidates)
candidates.sort()
def dfs(cur, idx, t):
if t == 0: ans.add(tuple(cur)); return
if t < 0 or idx >= n: return
for i in range(idx, n):
x = candidates[i]
if x <= t: dfs(cur + [x], i + 1, t - x)
dfs([], 0, target)
return [list(x) for x in ans]上面的写法对于这个用例会 TLE：[1] * x, 30。需要先想清楚这个 dfs 执行过程中产生的树是什么样子的，然后剪枝。
感谢 liweiwei1419 大佬提供的剪枝思路。简单来说就是同层的相同的都给剪掉，不同层的相同的当然不用管，可以详细看评论区。
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans = set()
n = len(candidates)
candidates.sort()
def dfs(cur, idx, t):
if t == 0: ans.add(tuple(cur)); return
if t < 0 or idx >= n: return
for i in range(idx, n):
if i > idx and candidates[i] == candidates[i - 1]: continue
x = candidates[i]
if x <= t: dfs(cur + [x], i + 1, t - x)
dfs([], 0, target)
return [list(x) for x in ans]282. 给表达式添加运算符
需要注意的细节：
- 以 0 开头的只有 ‘0’ 才行，其他都不行。
- 只是二元运算，第一个数字前面没有符号或操作。
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
n = len(num)
ans = []
def dfs(pre, cur, idx, res):
# 上一个数，当前算数结果，下一个的下标，当前字符串结果
if idx == n:
if cur == target: ans.append(res)
return
for slen in range(1, n - idx + 1):
cur_s = num[idx: idx + slen]
cur_num = int(cur_s)
if cur_s[0] == '0' and len(cur_s) != 1: return
if idx == 0:
dfs(cur_num, cur + cur_num, idx + slen, res + cur_s)
else:
dfs(cur_num, cur + cur_num, idx + slen, res + "+" + cur_s)
dfs(-cur_num, cur - cur_num, idx + slen, res + "-" + cur_s)
dfs(pre * cur_num, cur - pre + pre * cur_num, idx + slen, res + "*" + cur_s)
dfs(0, 0, 0, "")
return ans