网站链接数怎么做,网站推广需要多少钱易下拉系统,南通网站优化推广,网站建设首选建站系统详细布置
今天这三道题都非常难#xff0c;那么这么难的题#xff0c;为啥一天做三道#xff1f; 因为 一刷 也不求大家能把这么难的问题解决#xff0c;所以 大家一刷的时候#xff0c;就了解一下题目的要求#xff0c;了解一下解题思路#xff0c;不求能直接写出代码…详细布置
今天这三道题都非常难那么这么难的题为啥一天做三道 因为 一刷 也不求大家能把这么难的问题解决所以 大家一刷的时候就了解一下题目的要求了解一下解题思路不求能直接写出代码先大概熟悉一下这些题二刷的时候随着对回溯算法的深入理解再去解决如下三题。 大家今天的任务其实是 对回溯算法章节做一个总结就行。 重点是看 回溯算法总结篇 代码随想录 332.重新安排行程可跳过 代码随想录 Python使用used数组lc1/81会超时: class Solution:def __init__(self):self.result []self.path [JFK]def backtracking(self, tickets, cur, used):if len(self.path)len(tickets)1:self.result self.path[:]return Truefor i, ticket in enumerate(tickets):if ticket[0] cur and used[i] False:used[i] True self.path.append(ticket[1])state self.backtracking(tickets, ticket[1], used)if state: return Trueused[i] Falseself.path.pop() def findItinerary(self, tickets: List[List[str]]) - List[str]:tickets.sort()used [False] * len(tickets)self.backtracking(tickets, JFK, used)return self.result python版本只有优化到 使用字典 并逆序查找才可以通过所有的测试用例。 from collections import defaultdictclass Solution:def findItinerary(self, tickets):targets defaultdict(list) # 创建默认字典用于存储机场映射关系for ticket in tickets:targets[ticket[0]].append(ticket[1]) # 将机票输入到字典中for key in targets:targets[key].sort(reverseTrue) # 对到达机场列表进行字母逆序排序result []self.backtracking(JFK, targets, result) # 调用回溯函数开始搜索路径return result[::-1] # 返回逆序的行程路径def backtracking(self, airport, targets, result):while targets[airport]: # 当机场还有可到达的机场时next_airport targets[airport].pop() # 弹出下一个机场self.backtracking(next_airport, targets, result) # 递归调用回溯函数进行深度优先搜索result.append(airport) # 将当前机场添加到行程路径中 C: class Solution {
private:
unordered_mapstring, mapstring, int targets;
bool backtracking(int ticketNum, vectorstring result) {if (result.size()ticketNum1) return true;for (pairconst string, int target: targets[result[result.size()-1]]) {if (target.second 0) {result.push_back(target.first);target.second--;if (backtracking(ticketNum, result)) return true;result.pop_back();target.second;}}return false;
} public: vectorstring findItinerary(vectorvectorstring tickets) {vectorstring result;result.push_back(JFK);for (const vectorstring vec: tickets) {targets[vec[0]][vec[1]];}backtracking(tickets.size(), result);return result;}
}; 51. N皇后可跳过 代码随想录 视频讲解这就是传说中的N皇后 回溯算法安排| LeetCode51.N皇后_哔哩哔哩_bilibili Python: class Solution:def __init__(self):self.result []def isValid(self, row, col, chessboard):# 检查列for i in range(row):if chessboard[i][col] Q:return False# 检查45度i, j row-1, col-1while i0 and j0:if chessboard[i][j] Q:return Falsei - 1j- 1# 检查135度i, j row-1, col1while i0 and jlen(chessboard):if chessboard[i][j] Q:return Falsei - 1j 1return Truedef backtracking(self, n, row, chessboard):if rown:self.result.append(chessboard[:])returnfor col in range(n):if self.isValid(row, col, chessboard):chessboard[row] chessboard[row][:col] Q chessboard[row][col1:]self.backtracking(n, row1, chessboard)chessboard[row] chessboard[row][:col] . chessboard[row][col1:] returndef solveNQueens(self, n: int) - List[List[str]]:if n1: return [[Q]] chessboard [.*n for _ in range(n)]self.backtracking(n, 0, chessboard)return self.result C: class Solution {
public:vectorvectorstring result;void backtracking(int n, int row, vectorstring chessboard) {if (rown) {result.push_back(chessboard);return;}for (int col0; coln; col) {if (isValid(row, col, chessboard)) {chessboard[row][col] Q;backtracking(n, row1, chessboard);chessboard[row][col] .;}}}bool isValid(int row, int col, vectorstring chessboard) {// 检查列for (int i0; irow; i) {if (chessboard[i][col]Q) return false;}// 检查45度for (int irow-1, j col-1; i0 j0; i--, j--) {if (chessboard[i][j]Q) return false;}// 检查135度for (int irow-1, jcol1; i0 jchessboard.size(); i--, j) {if (chessboard[i][j]Q) return false;}return true;}vectorvectorstring solveNQueens(int n) {result.clear();std:: vectorstd::string chessboard(n, std::string(n, .));backtracking(n, 0, chessboard);return result;}
}; 37. 解数独可跳过 代码随想录 视频讲解回溯算法二维递归解数独不过如此| LeetCode37. 解数独_哔哩哔哩_bilibili Python: class Solution:def isValid(self, row, col, ele, board):# 行for i in range(9):if board[row][i] ele: return False# 列for j in range(9):if board[j][col] ele: return False# 九宫格start_row (row//3) * 3start_col (col//3) * 3for i in range(start_row, start_row3):for j in range(start_col, start_col3):if board[i][j] ele: return Falsereturn Truedef backtracking(self, row, board):for row in range(9):for col in range(9):if board[row][col] ! .: continuefor ele in range(1, 10):if self.isValid(row, col, str(ele), board): board[row][col] str(ele)if self.backtracking(row1, board): return Trueboard[row][col] .return Falsereturn Truedef solveSudoku(self, board: List[List[str]]) - None:Do not return anything, modify board in-place instead.self.backtracking(0, board) C: class Solution {
public:bool isValid(int row, int col, char ele, vectorvectorchar board) {// 行for (int i0; i9; i) {if (board[row][i]ele) return false;}// 列for (int j0; j9; j) {if (board[j][col]ele) return false;} // 九宫格int startRow (row/3) * 3;int startCol (col/3) * 3;for (int istartRow; istartRow3; i) {for (int jstartCol; jstartCol3; j) {if (board[i][j]ele) return false;}}return true;}bool backtracking(vectorvectorchar board) {for (int row0; row9; row) {for (int col0; col9; col) {if (board[row][col].) {for (char ele1; ele9; ele) {if (isValid(row, col, ele, board)) {board[row][col] ele;if (backtracking(board)) return true;board[row][col] .;} }return false;}}}return true;}void solveSudoku(vectorvectorchar board) {backtracking(board);}
}; 总结 代码随想录
