*332.重新安排行程

https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html

• 考点
  • 图论里的深度优先搜索（本题使用回溯来解决）
  • 这是一道hard题，一刷先放过去，二刷有精力再做
• 我的思路
  • 无思路
• 视频讲解关键点总结
  • 见链接
• 我的思路的问题
  • 无思路
• 代码书写问题
  • 无
• 可执行代码

# 这种方法会超时
class Solution:def backtracking(self, tickets, start, used, result):if len(result) == len(tickets) + 1:return Truefor i, ticket in enumerate(tickets):if ticket[0] == start and used[i] == 0:used[i] = 1result.append(ticket[1])res = self.backtracking(tickets, ticket[1], used, result)if res is True:return Trueresult.pop()used[i] = 0def findItinerary(self, tickets: List[List[str]]) -> List[str]:tickets.sort()result = ['JFK']used = [0] * len(tickets)self.backtracking(tickets, 'JFK', used, result)return result

*51. N皇后

https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html
视频讲解：https://www.bilibili.com/video/BV1Rd4y1c7Bq

• 考点
  • 回溯+棋盘问题
• 我的思路
  • 无思路
• 视频讲解关键点总结
  • 棋盘问题的关键就是怎么回溯：for循环的范围是棋盘的宽，递归的深度是棋盘的高
• 我的思路的问题
  • 无
• 代码书写问题
  • 初始化二维列表可以使用['.' * n for _ in range(n)]
• 可执行代码

class Solution:def backtracking(self, n, solution, loc, x, result):if len(solution) == n:result.append(solution[:])returnfor i in range(n):if solution and not self.is_right(loc, x, i):continueloc.append((x, i))base = ['.'] * nbase[i] = 'Q'solution.append(''.join(base))self.backtracking(n, solution, loc, x + 1, result)solution.pop()loc.pop()def is_right(self, loc, x_loc, i):for x, y in loc:if y == i or abs(x - x_loc) == abs(y - i):return Falsereturn Truedef solveNQueens(self, n):result = []self.backtracking(n, [], [], 0, result)return result

*37. 解数独

• 考点
  • 回溯+棋盘
• 我的思路
  • 无思路
• 视频讲解关键点总结
  • 把回溯里的循环变成双层，之后再用一个循环遍历不同的数字
  • 具体思路见视频
  • 
• 我的思路的问题
  • 无思路
• 代码书写问题
  • 无
• 可执行代码

class Solution:def backtracking(self, board):for i in range(len(board)):for j in range(len(board[0])):if board[i][j] == '.':for num in range(1, 10):if self.is_valid(board, num, i, j):board[i][j] = str(num)result = self.backtracking(board)if result:return Trueboard[i][j] = '.'return Falsereturn Truedef is_valid(self, board, num, i, j):for y in range(len(board[0])):if board[i][y] == str(num):return Falsefor x in range(len(board)):if board[x][j] == str(num):return Falsestart_x = (i // 3) * 3start_y = (j // 3) * 3for x in range(start_x, start_x + 3):for y in range(start_y, start_y + 3):if board[x][y] == str(num):return Falsereturn Truedef solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""self.backtracking(board)

总结

• 见我的另一篇文章