代码随想录算法训练营 Day 22
Published:
Q1. LeetCode 491
去重逻辑与LeetCode 90的区别：不能对原数组排序，因此记录已遇见的元素
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
res = []
def backtracking(start, arr):
if len(arr) > 1:
res.append(arr[:])
# 因为题目限制，也可用数组替代
used = set()
for i in range(start, len(nums)):
if (arr and nums[i] < arr[-1]) or nums[i] in used:
continue
used.add(nums[i])
arr.append(nums[i])
backtracking(i + 1, arr)
arr.pop()
backtracking(0, [])
return res
复杂度分析
时间复杂度：O($n \times 2^n$) 空间复杂度：O($n$)
Q2. LeetCode 46
题目要求返回的是所有排列，而排列是有序的 (e.g. $[1,2]$和$[2,1]$两者不同)，因此每次都需要从头遍历
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
# used数组表示对应位置的元素是否已被使用
def backtracking(used, arr):
if sum(used) == len(nums):
res.append(arr[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = 1
arr.append(nums[i])
backtracking(used, arr)
arr.pop()
used[i] = 0
backtracking([0] * len(nums), [])
return res
复杂度分析
时间复杂度：O($n!$) 空间复杂度：O($n$)
Q3. LeetCode 47
注意两种去重的逻辑，理解为什么第二种更高效。参考代码随想录
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
# used数组表示对应位置的元素是否已被使用
def backtracking(used, arr):
if sum(used) == len(nums):
res.append(arr[:])
return
for i in range(len(nums)):
if (i > 0 and nums[i] == nums[i - 1] and used[i - 1]) or used[i]:
continue
used[i] = 1
arr.append(nums[i])
backtracking(used, arr)
arr.pop()
used[i] = 0
backtracking([0] * len(nums), [])
return res
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
# used数组表示对应位置的元素是否已被使用
def backtracking(used, arr):
if sum(used) == len(nums):
res.append(arr[:])
return
for i in range(len(nums)):
if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]:
continue
used[i] = 1
arr.append(nums[i])
backtracking(used, arr)
arr.pop()
used[i] = 0
backtracking([0] * len(nums), [])
return res
复杂度分析
时间复杂度：O($n! \times n$) 空间复杂度：O($n$)
Q4. LeetCode 332
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
t = defaultdict(list)
for source, dest in tickets:
t[source].append(dest)
for city in t:
t[city].sort()
res = []
def backtracking(city):
while t[city]:
next_city = t[city].pop(0)
backtracking(next_city)
# 当没有下一个城市时，将当前城市放进结果集中
res.append(city)
backtracking('JFK')
return res[::-1]
Q5. LeetCode 51
经典的N皇后问题：1. 皇后不能同行；2. 皇后不能同列；3. 皇后不能在一条斜线
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
def is_vaid(row, col, board):
# 判断是否有同一列的皇后
for i in range(row):
if board[i][col] == 'Q':
return False
# 判断45度角是否有皇后
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 判断135度角是否有皇后
i, j = row - 1, col + 1
while i >= 0 and j < len(board):
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtracking(r, board):
if r == n:
res.append(board[:])
return
# 每次都往一行加入一个皇后，保证了皇后不同行
for c in range(n):
if is_vaid(r, c, board):
board[r] = board[r][:c] + 'Q' + board[r][c + 1:]
backtracking(r + 1, board)
board[r] = board[r][:c] + '.' + board[r][c + 1:]
init_board = ['.' * n for _ in range(n)]
backtracking(0, init_board)
return res
复杂度分析
时间复杂度：O($n!$) 空间复杂度：O($n$)
Q6. LeetCode 37
二维递归：与N皇后不同，判断条件需要遍历所有行和所有列
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def is_valid(r, c, num, b):
# 判断同一行
for j in range(9):
if b[r][j] == str(num):
return False
# 判断同一列
for i in range(9):
if b[i][c] == str(num):
return False
# 判断所处九方格
start_r = (r // 3) * 3
start_c = (c // 3) * 3
for i in range(3):
for j in range(3):
if b[start_r + i][start_c + j] == str(num):
return False
return True
def backtracking(b):
for i in range(len(b)):
for j in range(len(b[0])):
if b[i][j] != '.':
continue
for n in range(1, 10):
if is_valid(i, j, n, b):
b[i][j] = str(n)
if backtracking(b):
return True
b[i][j] = '.'
return False
return True
backtracking(board)
TODO
Q4 - Q6巩固