前言
本篇共4题，附有解题思路和AC代码。
边听歌边刷起来吧~
47. 全排列 II
链接：47. 全排列 II
解题思路
- 在 travalBack 函数中，首先判断当前排列的长度是否等于原始数组的长度，如果是，则将该排列加入到结果集中，并返回。
- 如果当前排列长度不满足条件，就遍历原始数组 nums 中的元素，并进行处理。
- 在遍历过程中，如果当前元素与前一个元素相等，并且前一个元素没有被使用过，则跳过该元素，以避免产生重复的排列。
- 如果当前元素没有被使用过，则将其加入到当前排列 path 中，并将该元素标记为已使用。
- 然后递归调用 travalBack 函数，继续生成下一个位置上的元素。
- 在递归调用返回后，需要将当前元素标记为未使用，并将其从当前排列中移除，以便生成其他可能的排列。
- 在 permuteUnique 函数中，首先对原始数组进行排序，以确保重复元素紧邻。
- 然后创建一个布尔型数组 used，并将其传递给 travalBack 函数进行全排列的生成。
- 最后返回结果集 res。
AC代码
class Solution { public: vector<vector<int>> res; vector<int> path; void travalBack(vector<int>& nums ,vector<bool>& used) { if(path.size()==nums.size()) { res.push_back(path); return; } for(int i=0;i<nums.size();++i) { if(i>0&&nums[i-1]==nums[i]&&used[i-1]==false)continue; else if(used[i]==false){ path.push_back(nums[i]); used[i]=true; travalBack(nums,used); used[i]=false; path.pop_back(); } } } vector<vector<int>> permuteUnique(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<bool> used(nums.size()); travalBack(nums,used); return res; } };
332. 重新安排行程
链接：332. 重新安排行程
解题思路
这一题和之前的回溯一样的模板，它的关键点在于要看到怎么处理航班之间的关系，但是其实来说就是要判断行程是否合理，如果之前已经飞过，就不能再飞，还有就是整躺下来如果不能用到所有的机票也是不对的路径，还要注意的是要求字典序最小的路径
所以可以得出：
- 终止条件：result的大小需要等于机票的数量加1
- for循环内：需要判断是否有当前的机票，有则进入”可回溯“的区域
- ”可回溯“区域：注意票数的更新，如果满足条件就可以返回true，已经找到
- 在一开始的时候就要建立机场之间的映射关系
AC代码
class Solution { public: //unordered_map<出发机场, map<到达机场, 航班班次>> targets; unordered_map<string, map<string,int>> targets; bool backtraval(int ticketNum,vector<string>&result){ if(result.size() == ticketNum + 1){ return true; } for(pair<const string,int>&target : targets[result[result.size()-1]]){ if(target.second > 0){ result.push_back(target.first); target.second--; if(backtraval(ticketNum,result))return true; result.pop_back(); target.second++; } } return false; } vector<string> findItinerary(vector<vector<string>>& tickets) { targets.clear(); vector<string> result; for(const vector<string>&vec : tickets){ targets[vec[0]][vec[1]]++; } result.push_back("JFK"); backtraval(tickets.size(),result); return result; } };
51. N 皇后
链接：51. N 皇后
解题思路
AC代码
class Solution { public: vector<vector<string>> res; void travalBack(int row,int n,vector<string>& board){ if(row == n){ res.push_back(board); return; } for(int col=0;col<n;++col){ if(isvalid(row,col,n,board)){ board[row][col]='Q'; travalBack(row+1,n,board); board[row][col]='.'; } } } bool isvalid(int row,int col,int n,vector<string>& board) { for(int i=0;i<row;++i){ if(board[i][col]=='Q')return false; } for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){ if(board[i][j]=='Q')return false; } for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){ if(board[i][j]=='Q')return false; } return true; } vector<vector<string>> solveNQueens(int n) { std::vector<std::string> board(n, std::string(n, '.')); travalBack(0,n,board); return res; } };
37. 解数独
链接：37. 解数独
解题思路
AC代码
class Solution { private: bool backtracking(vector<vector<char>>& board) { for (int i = 0; i < board.size(); i++) { // 遍历行 for (int j = 0; j < board[0].size(); j++) { // 遍历列 if (board[i][j] == '.') { for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适 if (isValid(i, j, k, board)) { board[i][j] = k; // 放置k if (backtracking(board)) return true; // 如果找到合适一组立刻返回 board[i][j] = '.'; // 回溯，撤销k } } return false; // 9个数都试完了，都不行，那么就返回false } } } return true; // 遍历完没有返回false，说明找到了合适棋盘位置了 } bool isValid(int row, int col, char val, vector<vector<char>>& board) { for (int i = 0; i < 9; i++) { // 判断行里是否重复 if (board[row][i] == val) { return false; } } for (int j = 0; j < 9; j++) { // 判断列里是否重复 if (board[j][col] == val) { return false; } } int startRow = (row / 3) * 3; int startCol = (col / 3) * 3; for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复 for (int j = startCol; j < startCol + 3; j++) { if (board[i][j] == val ) { return false; } } } return true; } public: void solveSudoku(vector<vector<char>>& board) { backtracking(board); } };
