聚牛网站建设公司,开网站挣不挣钱,网站数据统计,wordpress 定时 检查46.全排列
题目链接#xff1a;. - 力扣#xff08;LeetCode#xff09;
讲解视频#xff1a;
组合与排列的区别#xff0c;回溯算法求解的时候#xff0c;有何不同#xff1f;
题目描述#xff1a;
给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能…46.全排列
题目链接. - 力扣LeetCode
讲解视频
组合与排列的区别回溯算法求解的时候有何不同
题目描述
给定一个不含重复数字的数组 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]]解题思路 与前边的组合分割问题不同在于全排列问题每次递归至下一层后都要从头开始遍历。使用一个used数组进行去重判断当前元素是否已经被使用 代码
class Solution {
public:vectorvectorint result;vectorint path;void backTracking(vectorint nums, vectorint used){if(path.size() nums.size()) {result.push_back(path);return;}for(int i 0; i nums.size(); i){if(used[i] 0){used[i] 1;path.push_back(nums[i]);backTracking(nums,used);path.pop_back();used[i] 0;}}}vectorvectorint permute(vectorint nums) {result.clear();path.clear();vectorint used(nums.size(), 0);backTracking(nums,used);return result;}
};
47.全排列 II
题目链接. - 力扣LeetCode
讲解视频
回溯算法求解全排列如何去重| LeetCode47.全排列 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]]解题思路 先对nums数组排序去重逻辑 横向去重使用used数组对同层元素进行判断若前后元素相同且前一个元素used值为0表明当前遍历是同层遍历就说明该元素已经被使用跳过这个元素纵向去重每次递归至下一层后都要从头开始遍历。使用同一个used数组进行去重判断当前元素是否已经被使用 代码
class Solution {
public:vectorvectorint result;vectorint path;void backTracking(vectorint nums,vectorint used){if(path.size() nums.size()) {result.push_back(path);return;}for(int i 0; i nums.size(); i){if(i 0 nums[i] nums[i-1] used[i-1] 0) continue;if(used[i] 0){path.push_back(nums[i]);used[i] 1;backTracking(nums,used);used[i] 0;path.pop_back();}}}vectorvectorint permuteUnique(vectorint nums) {result.clear();path.clear();sort(nums.begin(),nums.end());vectorint used(nums.size(),0);backTracking(nums,used);return result;}
};
51. N皇后
题目链接. - 力扣LeetCode
讲解视频
这就是传说中的N皇后 回溯算法安排| LeetCode51.N皇后
题目描述
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。
示例 1
输入n 4
输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]
解释如上图所示4 皇后问题存在两个不同的解法。
解题思路 N皇后问题步骤 按行遍历对每一行中每一个位置做判断看当前棋盘布局是否符合条件判断标准同一行同一列对角线45°135°均不能存在2个及以上的Q若所有行均遍历完成就把结果保存至result中并返回。 代码
class Solution {
public:vectorvectorstring result;bool isValid(vectorstring chessboard, int row, int col, int n){for(int i 0; i row; i) // 判断列if(chessboard[i][col] Q) return false;for(int i row - 1, j col - 1; i 0 j 0; i--,j--) //对角45°if(chessboard[i][j] Q) return false;for(int i row - 1, j col 1; i 0 j n; i--,j) //对角135°if(chessboard[i][j] Q) return false;return true;}void backTracking(vectorstring chessboard, int row, int n){if(row n){result.push_back(chessboard);return;}for(int col 0; col n; col){if(isValid(chessboard,row,col,n)){chessboard[row][col] Q;backTracking(chessboard,row1,n);chessboard[row][col] .;}}}vectorvectorstring solveNQueens(int n) {vectorstring chessboard(n,string(n,.));backTracking(chessboard,0,n);return result;}
};
37. 解数独
题目链接. - 力扣LeetCode
讲解视频
回溯算法二维递归解数独不过如此| LeetCode37. 解数独
题目描述
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图
数独部分空格内已填入了数字空白格用 . 表示。题目数据 保证 输入数独仅有一个解
示例 1 输入board [[5,3,.,.,7,.,.,.,.],[6,.,.,1,9,5,.,.,.],[.,9,8,.,.,.,.,6,.],[8,.,.,.,6,.,.,.,3],[4,.,.,8,.,3,.,.,1],[7,.,.,.,2,.,.,.,6],[.,6,.,.,.,.,2,8,.],[.,.,.,4,1,9,.,.,5],[.,.,.,.,8,.,.,7,9]]
输出[[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]
解释输入的数独如上图所示唯一有效的解决方案如下所示解题思路 该题目与N皇后问题的区别在于 解数独问题中只要找到一个解即可回溯函数类型为bool。N皇后问题找到所有解回溯函数类型为void解数独问题使用二维数组遍历。N皇后问题使用一维数组遍历。解数独问题中每一个格中从1~9中判断。N皇后问题每一个格只从Q判断解数独问题判断条件同行同列不能有重复元素3x3宫内不能有重复元素 代码
class Solution {
public:bool isValid(int row, int col, int k, vectorvectorchar board){for(int i 0; i board[0].size(); i) //判断行if(i ! col board[row][i] k) return false; for(int i 0; i board.size(); i) //判断列if(i ! row board[i][col] k) return false; for(int i row - row % 3; i row - row % 3 3; i)for(int j col - col % 3; j col - col%3 3; j)if(i ! row j ! col board[i][j] k) return false;return true;}bool backTracking(vectorvectorchar 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){if(isValid(i,j,k,board)){board[i][j] k;if(backTracking(board)) return true;board[i][j] .;}}return false;}}}return true;}void solveSudoku(vectorvectorchar board) {backTracking(board);}
};
