网站源码文件,discuz主题,wordpress相关知识,design工业设计本文将通过几个经典的回溯问题#xff0c;展示回溯算法的应用及其在解决问题时的核心思想和技巧。这些问题包括全排列、全排列II、N皇后以及数独问题#xff0c;本文将分别介绍每个问题的思路与实现。
46. 全排列
给定一个不含重复数字的数组 nums #xff0c;返回其 所有…本文将通过几个经典的回溯问题展示回溯算法的应用及其在解决问题时的核心思想和技巧。这些问题包括全排列、全排列II、N皇后以及数独问题本文将分别介绍每个问题的思路与实现。
46. 全排列
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2
输入nums [0,1]
输出[[0,1],[1,0]]示例 3
输入nums [1]
输出[[1]]思路 对于给定的数组我们通过回溯法逐一选择数组中的元素并将其加入当前的排列中。 需要一个 visited 数组来记录每个元素是否已经被使用过避免重复排列。 每当排列的长度等于原数组长度时表示当前排列已完成加入结果集。
核心技巧 在递归过程中使用 visited 数组来确保每个元素只被使用一次。 递归的终止条件是当当前排列的长度等于数组长度时说明已经形成一个完整的排列。
class Solution {
public:vectorvectorint res;vectorint path;unordered_setint node;void backfind(vectorint nums){if(path.size()nums.size()){res.push_back(path);return;}for(int i0; inums.size(); i){if(node.find(nums[i])!node.end()){continue;}node.insert(nums[i]);path.push_back(nums[i]);backfind(nums);node.erase(nums[i]);path.pop_back();}}vectorvectorint permute(vectorint nums) {backfind(nums);return res;}
};47. 全排列 II
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。
示例 1
输入nums [1,1,2]
输出
[[1,1,2],[1,2,1],[2,1,1]]示例 2
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]思路先对数组进行排序使得相同的元素相邻。使用 visited 数组来标记每个元素是否已经被访问过同时利用排序后的数组来跳过已经处理过的重复元素。在每次递归时检查当前元素与前一个元素是否相同如果相同且前一个元素未被访问则跳过当前元素。
核心技巧排序保证了相同元素相邻从而避免了重复排列。通过回溯的剪枝技巧避免在同一层的递归中重复访问相同的元素。 class Solution {
public:vectorvectorint res;vectorint path;void backfind(vectorint nums, vectorbool visited){if(path.size()nums.size()){res.push_back(path);return; }for(int i0; inums.size(); i){if(i0nums[i]nums[i-1]visited[i-1]false){continue;}//同层树重复的跳过同层的上一个visited是没访问过的(回溯)//visited[i-1]true也是可以滴if(visited[i]){continue;}visited[i]true;path.push_back(nums[i]);backfind(nums,visited);visited[i]false;path.pop_back();}}vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end());vectorbool visited(nums.size(), false);backfind(nums,visited);return res;}
};51. N 皇后
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。
示例 1 输入n 4
输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]
解释如上图所示4 皇后问题存在两个不同的解法。思路使用回溯法逐行放置皇后每放置一个皇后就递归处理下一行。 在每次尝试放置皇后时检查该位置是否会与已放置的皇后发生冲突即检查同列、左斜线和右斜线是否已有皇后。
核心技巧使用三种标记列标记、左斜线标记、右斜线标记来有效判断是否可以放置皇后。 通过递归实现行的逐步尝试并在放置皇后后继续处理下一行。 class Solution {
public:vectorvectorstring res;void find(int n, int row, vectorstring rowChess){if(rown){res.push_back(rowChess);return;}for(int col0; coln; col){if(isQ(rowChess,row,col,n)){rowChess[row][col]Q;find(n, row1, rowChess);rowChess[row][col].;}}}bool isQ(vectorstring rowChess, int row, int col, int n){//先遍历列for(int i0; irow; i){if(rowChess[i][col]Q){return false;}}//再检查45°线for(int irow-1, jcol-1; i0j0; i--,j--){if(rowChess[i][j]Q){return false;}}//再检查135°线for(int irow-1, jcol1; i0jn; i--,j){if(rowChess[i][j]Q){return false;}}return true;}vectorvectorstring solveNQueens(int n) {vectorstring rowChess(n, string(n,.));find(n, 0, rowChess);return res;}
};37. 解数独
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图
数独部分空格内已填入了数字空白格用 . 表示。
思路使用回溯法逐步填充数独中的空格。每次选择一个空格尝试填入数字 1-9并检查填入的数字是否合法。如果合法递归处理下一个空格如果不合法回溯并尝试其他数字。
核心技巧使用一个 isOK 函数来检查当前填入的数字是否符合数独的规则。 回溯的终止条件是所有空格都被填充且合法时返回解。
class Solution {
public:bool backsolve(vectorvectorchar board){for(int i0; iboard.size(); i){for(int j0; jboard[0].size(); j){if(board[i][j].){for(char c1; c9; c){if(isOK(board,i,j,c)){board[i][j]c;if(backsolve(board)) return true;board[i][j].;}}return false;}}}return true;}bool isOK(vectorvectorchar board, int row, int col, char val){//行里面寻找有没有重复的for(int i0; i9; i){if(board[i][col]val){return false;}}//列里面寻找有没有重复的for(int j0; j9; j){if(board[row][j]val){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]val){return false;}}}return true;}void solveSudoku(vectorvectorchar board) {backsolve(board);}
};
