Leetcode刷题记录——回溯排列篇
Leetcode46 全排列
排列问题是每个元素都要用，所以就不需要startIndex了
对于重复问题，依然是设置一个used数组
Pyhton代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def __init__(self):
self.res = []
self.path = []
def permute(self, nums: List[int]) -> List[List[int]]:
used = [0] * len(nums)
self.backtracking(nums, used)
return self.res
def backtracking(self, nums, used):
if len(self.path) == len(nums):
self.res.append(self.path[:])
return
for i in range(len(nums)):
if used[i] == 1:
continue
self.path.append(nums[i])
used[i] = 1
self.backtracking(nums, used)
self.path.pop()
used[i] = 0
|
Leetcode47 全排列Ⅱ
这道题依然是考去重
由于排列问题的for循环每次都是从头开始的，因此，在判断是否重复时，还需要添加used[i] == 1,表示遍历到的当前元素是否已经被用
并且用这种if (i > 0 and nums[i] == nums[i-1] and used[i-1] == 0) or used[i] == 1:方式判断是否去重的题
由于是往后依次判断是否出现重复元素，所以nums要事先排序
Python代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution:
def __init__(self):
self.res = []
self.path = []
def backtracking(self, nums, used):
if len(self.path) == len(nums):
self.res.append(self.path[:])
return
for i in range(len(nums)):
if (i > 0 and nums[i] == nums[i-1] and used[i-1] == 0) or used[i] == 1:
continue
self.path.append(nums[i])
used[i] = 1
self.backtracking(nums, used)
self.path.pop()
used[i] = 0
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
used = [0] * len(nums)
self.backtracking(nums, used)
return self.res
|
Leetcode51 N皇后
for循环是遍历棋盘的列(也就是树的宽度)，递归是遍历行(也就是树的深度)
检查的时候, 因为是按行一行一行放的棋子, 所以其实每次只要检查列、左上、右上即可
Python代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution:
def __init__(self):
self.res = []
self.final_res = []
def backtracking(self, chessboard, n, row):
if row == n:
self.res.append(chessboard[:])
return
for i in range(n):
if self.isValid(chessboard, row, i):
chessboard[row] = chessboard[row][:i] + 'Q' + chessboard[row][i+1:]
self.backtracking(chessboard, n, row+1)
chessboard[row] = chessboard[row][:i] + '.' + chessboard[row][i+1:]
def isValid(self, chessboard, row, col):
for i in range(row):
if chessboard[i][col] == 'Q':
return False
for i in range(col):
if chessboard[row][i] == 'Q':
return False
i = row - 1
j = col + 1
while i >= 0 and j < len(chessboard):
if chessboard[i][j] == 'Q':
return False
i -= 1
j += 1
i = row - 1
j = col - 1
while i >= 0 and j >= 0 :
if chessboard[i][j] == 'Q':
return False
i -= 1
j -= 1
return True
def solveNQueens(self, n: int) -> List[List[str]]:
chessboard = ['.' * n for _ in range(n)]
self.backtracking(chessboard, n, 0)
return self.res
|
Leetcode37 解数独
如果在回溯中只需要返回一个结果，那么可行的结果是在叶子节点，可以把backtracking的返回值设置成bool，遇到一个成立的就返回
如果是收集所有的结果，那么backtracking是不需要返回值的
Python代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution:
def backtracking(self, chessboard):
for i in range(len(chessboard)):
for j in range(len(chessboard[0])):
if chessboard[i][j] == '.':
for k in range(1, 10):
if self.isValid(i, j, k, chessboard):
chessboard[i][j] = str(k)
if self.backtracking(chessboard):
return True
chessboard[i][j] = '.'
return False
return True
def isValid(self, row, col, k, chessboard):
for i in range(9):
if chessboard[row][i] == str(k):
return False
for i in range(9):
if chessboard[i][col] == str(k):
return False
start_row = (row // 3) * 3
start_col = (col // 3) * 3
for i in range(start_row, start_row+3):
for j in range(start_col, start_col+3):
if chessboard[i][j] == str(k):
return False
return True
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
self.backtracking(board)
|