牛客 0026 括号生成 (中等, 2022-02)牛客 0027 集合的所有子集(一) (中等, 2022-02)牛客 0042 有重复项数字的全排列 (中等, 2022-03)牛客 0043 没有重复项数字的全排列 (中等, 2022-03)牛客 0046 加起来和为目标值的组合(二) (中等, 2022-03)牛客 0047 数独 (较难, 2022-03)
给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
例如，给出n=3，解集为：
"((()))", "(()())", "(())()", "()()()", "()(())"- 关键是中止条件的判断，详见代码；
Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return string字符串一维数组
#
class Solution:
def generateParenthesis(self , n: int) -> List[str]:
# write code here
ret = []
tmp = []
def dfs(i, j):
if i > n or j > n or i < j:
return
if i == j == n:
ret.append(''.join(tmp))
return
tmp.append('(')
dfs(i + 1, j)
tmp.pop()
tmp.append(')')
dfs(i, j + 1)
tmp.pop()
dfs(0, 0)
return ret
现在有一个没有重复元素的整数集合S，求S的所有子集
注意：
你给出的子集中的元素必须按升序排列
给出的解集中不能出现重复的元素Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param S int整型一维数组
# @return int整型二维数组
#
class Solution:
def subsets(self , S: List[int]) -> List[List[int]]:
# write code here
N = len(S)
ret = []
tmp = []
def dfs(i):
if i == N:
ret.append(tmp[:])
return
# 不要当前元素
dfs(i + 1)
# 要当前元素
tmp.append(S[i])
dfs(i + 1)
tmp.pop()
dfs(0)
return ret
给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。- 难点是重复数字的剪枝；
- 定义
book[i] = 1表示num[i]已经使用过；
Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param num int整型一维数组
# @return int整型二维数组
#
class Solution:
def permuteUnique(self , num: List[int]) -> List[List[int]]:
ret = []
tmp = []
N = len(num)
num.sort() # 排序
book = [0] * N
def dfs(deep):
if deep == N:
ret.append(tmp[:])
return
for i in range(N):
if book[i]:
continue
# 树层剪枝
if not book[i - 1] and i > 0 and num[i] == num[i - 1]:
continue
# 为什么是 not book[i - 1]？
# 当遍历完一条路径回到本层的时候，book[i - 1] 会回溯为 0，
# 此时如果还有 num[i] == num[i - 1]，说明当前路径重复，直接跳过
book[i] = 1
tmp.append(num[i])
dfs(deep + 1)
tmp.pop()
book[i] = 0
dfs(0)
return ret
给出一组数字，返回该组数字的所有排列
例如：
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param num int整型一维数组
# @return int整型二维数组
#
class Solution:
def permute(self , num: List[int]) -> List[List[int]]:
ret = []
tmp = []
N = len(num)
book = [0] * N
def dfs(deep):
if deep == N:
ret.append(tmp[:])
for i in range(N):
if book[i]:
continue
book[i] = 1
tmp.append(num[i])
dfs(deep + 1)
tmp.pop()
book[i] = 0
dfs(0)
return ret
给出一组候选数 c 和一个目标数 t ，找出候选数中起来和等于 t 的所有组合。
c 中的每个数字在一个组合中只能使用一次。
注意：
1. 题目中所有的数字（包括目标数 t ）都是正整数
2. 组合中的数字要按非递减排序
3. 结果中不能包含重复的组合
4. 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。- 定义
dfs(start, rest)表示从start开始遍历剩下的元素，剩余目标和rest； - 剪枝要点（详见代码）；
- 先对
arr排序； - 当前层跳过重复值，即
arr[i] == arr[i-1]时continue； - 遍历当前层元素时，若
rest < arr[i]直接break；
- 先对
Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param num int整型一维数组
# @param target int整型
# @return int整型二维数组
#
class Solution:
def combinationSum2(self , arr: List[int], target: int) -> List[List[int]]:
N = len(arr)
arr.sort()
ret = []
tmp = []
def dfs(start, rest):
if rest == 0:
ret.append(tmp[:])
return
for i in range(start, N):
if i > start and arr[i] == arr[i - 1]:
continue
# 因为排过序了，所以当前值不够的话，后面的肯定都不够了，直接全部剪掉
if rest < arr[i]:
break
tmp.append(arr[i])
# 注意这里不是 start + 1，而是 i + 1，表示下一层应该从 i + 1 开始尝试
# dfs(start + 1, rest - arr[i]) # err
dfs(i + 1, rest - arr[i])
tmp.pop()
dfs(0, target)
return ret
请编写一个程序，给数独中的剩余的空格填写上数字
空格用字符'.'表示
假设给定的数独只有唯一的解法- 使用三个矩阵记录每行、每列、每块出现过的数字；开始时，需要对已经出现过的数字初始化；
- 难点1：
- 对
board[i][j]很容易确定他所在的行和列，但是确定所在块需要对坐标做一个转换； - 具体来说，假设块的标号从左往右，从上往下依次为
0~8，则对(i,j)，其所在块的 id 为k = 3*(i/3) + j/3； - 简单验证几个位置，
(0,0)在第 0 块，(8,8)在第 8 块；(4,5)在第 4 块；
- 对
- 难点2：
- 确定下一个遍历位置，最直观的顺序是从左往右，从上往下；
- 假设当前位置为
(i, j)表示第i行，第j列；则下一个位置(nxt_i, nxt_j)为：nxt_i = i if j != 8 else i + 1；nxt_j = j + 1 if j != 8 else 0；
- 详见代码；
Python
class Solution:
def solveSudoku(self , board):
if not board: return []
n = len(board) # 9
row = [[0] * (n + 1) for _ in range(n)]
col = [[0] * (n + 1) for _ in range(n)]
blk = [[0] * (n + 1) for _ in range(n)]
def init():
"""初始化 row, clo, blk 记录出现过的数字"""
for i in range(n):
for j in range(n):
# 确定块 id
k = 3 * (i // 3) + j // 3
if (x := board[i][j]) != '.':
x = int(x)
row[i][x] = col[j][x] = blk[k][x] = 1
def dfs(i, j):
# 顺利达到最后一行，说明每个位置都满足要求
if i == n: return True
# 确定下一个遍历位置
nxt_i = i if j != (n - 1) else i + 1
nxt_j = j + 1 if j != (n - 1) else 0
# 如果当前位置不需要填，直接到下一个位置
if board[i][j] != '.':
return dfs(nxt_i, nxt_j)
# 对当前位置遍历每个可用数字
k = 3 * (i // 3) + j // 3 # 块 id
for x in range(1, 10):
# 不可用，跳过
if row[i][x] or col[j][x] or blk[k][x]:
continue
# 可用，DFS回溯
row[i][x] = col[j][x] = blk[k][x] = 1
board[i][j] = str(x)
if dfs(nxt_i, nxt_j):
return True
board[i][j] = '.'
row[i][x] = col[j][x] = blk[k][x] = 0
return False
init()
dfs(0, 0)
return board