做网站编辑的时候没保存怎么,在线无限观看次数破解版,国内建网站软件,专业的龙岗网站建设1全排列 II
给定一个可包含重复数字的序列 nums #xff0c;按任意顺序 返回所有不重复的全排列。 示例 1#xff1a;
输入#xff1a;nums [1,1,2]
输出#xff1a;
[[1,1,2],[1,2,1],[2,1,1]]示例 2#xff1a;
输入#xff1a;nums [1,2,3]
输出#xff1a;[[1,…1全排列 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]]提示
1 nums.length 8-10 nums[i] 10
思路 这道题目和46.全排列 的区别在与给定一个可包含重复数字的序列要返回所有不重复的全排列。
这里又涉及到去重了。
1. 递归函数的返回值以及参数
返回值和参数
void backtracking(vectorint nums, vectorbool used) 返回值为 void因为每次调用只需要修改全局变量 path 和 result不需要从函数中返回特定值。参数 nums 是输入的原始数组used 是一个标记数组用于记录每个位置的元素是否已经被使用过。
2. 回溯函数的终止条件
终止条件
if (path.size() nums.size()) 当 path 的长度等于 nums 的长度时表示已经形成了一个完整的排列将 path 加入到 result 中并返回。
3. 单层搜索的过程
解题思路
选择路径 每次递归调用时在未使用过的元素中选择一个加入到 path 中。判断条件 使用 used 数组来判断当前元素是否已经被使用过以及是否需要去重。标记和递归 将当前未使用的元素加入 path 中并标记为已使用。递归调用 backtracking继续向下一层搜索。在递归返回后执行回溯操作撤销选择恢复标记状态以便进行下一次选择。
去重部分
去重条件
if (i 0 nums[i - 1] nums[i] used[i - 1] true) 当前元素与上一个元素相同并且上一个元素已经被使用过时跳过当前元素避免重复选择相同的元素。
代码
#include vector
#include algorithm // 包含排序函数 sort
using namespace std;class Solution {
private:vectorint path; // 存储当前路径的一维向量vectorvectorint result; // 存储最终结果的二维向量// 回溯函数参数为原始数组nums和标记数组usedvoid backtracking(vectorint nums, vectorbool used) {// 当路径长度等于数组长度时将当前路径加入结果集合if (path.size() nums.size()) {result.push_back(path);return;}// 遍历数组numsfor (int i 0; i nums.size(); i) {// 如果元素已经被使用过则跳过if (i 0 nums[i - 1] nums[i] used[i - 1] true) {continue; // 去重部分跳过重复的元素}if (used[i] true) {continue; // 如果元素已经被使用过则跳过}// 标记当前元素为已使用used[i] true;// 将当前元素加入路径中path.push_back(nums[i]);// 递归进入下一层决策树backtracking(nums, used);// 回溯操作撤销选择used[i] false;path.pop_back();}}public:// 主函数生成所有排列的入口函数vectorvectorint permuteUnique(vectorint nums) {result.clear(); // 清空结果集合path.clear(); // 清空当前路径sort(nums.begin(), nums.end()); // 排序输入数组确保重复元素相邻vectorbool used(nums.size(), false); // 标记数组记录每个位置的元素是否被使用过// 调用回溯函数从第一个位置开始生成排列backtracking(nums, used);// 返回最终的结果集合return result;}
};
2 N 皇后
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。 示例 1 输入n 4
输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]
解释如上图所示4 皇后问题存在两个不同的解法。示例 2
输入n 1
输出[[Q]]提示
1 n 9
思路
1. 递归函数的返回值以及参数
递归函数 backtracking 的目的是在棋盘上逐行放置皇后并检查每一步是否符合规则。其参数包括 int n棋盘大小int row当前处理的行数vectorstring chessboard当前棋盘状态。它没有显式的返回值而是通过修改全局变量 result 来存储所有合法的解。
2. 回溯函数终止条件
在 backtracking 函数中终止条件是当 row 等于 n 时即所有行都处理完毕此时找到了一个合法的皇后布局将其加入 result 数组中。
if (row n) {result.push_back(chessboard); // 找到一种解法存入结果return;
}3. 单层搜索的过程
在每一层递归中通过循环尝试将皇后放置在当前行的每一个列上然后递归处理下一行。在尝试放置之前通过 isValid 函数检查当前位置是否合法避免皇后之间的冲突。
for (int col 0; col n; col) {if (isValid(row, col, chessboard, n)) {chessboard[row][col] Q; // 放置皇后backtracking(n, row 1, chessboard); // 递归处理下一行chessboard[row][col] .; // 回溯撤销皇后}
}这种方法通过逐行放置皇后并通过回溯撤销不符合条件的放置最终找到所有合法的N皇后布局。
代码
class Solution {
private:vectorvectorstring result; // 存放最终的结果// 回溯算法核心函数// n 是棋盘大小row 是当前递归到的行数chessboard 是当前的棋盘状态void backtracking(int n, int row, vectorstring chessboard) {// 如果已经递归到最后一行说明找到了一种解法将其存入结果集合中if (row n) {result.push_back(chessboard);return;}// 遍历当前行的每一列尝试放置皇后for (int col 0; col n; col) {// 检查当前位置是否可以放置皇后if (isValid(row, col, chessboard, n)) { // 验证合法就可以放chessboard[row][col] Q; // 放置皇后backtracking(n, row 1, chessboard); // 递归处理下一行chessboard[row][col] .; // 回溯撤销皇后}}}// 检查当前位置是否可以放置皇后bool isValid(int row, int col, vectorstring chessboard, 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--) {if (chessboard[i][j] Q) {return false;}}// 检查右上方是否有皇后冲突for(int i row - 1, j col 1; i 0 j n; i--, j) {if (chessboard[i][j] Q) {return false;}}return true;}public:vectorvectorstring solveNQueens(int n) {result.clear(); // 清空结果集vectorstring chessboard(n, string(n, .)); // 初始化棋盘全部用.表示空backtracking(n, 0, chessboard); // 从第一行开始递归求解return result; // 返回所有解法}
};
3. 解数独
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 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]]
解释输入的数独如上图所示唯一有效的解决方案如下所示 提示
board.length 9board[i].length 9board[i][j] 是一位数字或者 .题目数据 保证 输入数独仅有一个解
思路
1. 递归函数的返回值与参数
递归函数 backtracking 的目标是填充数独中的空白格子用’.表示使得每个数字都符合数独的规则每行、每列、每个3x3子数独内都不能有重复的数字。具体来说
参数 函数接受一个二维字符数组 board即数独的当前状态。返回值 返回一个布尔值表示是否找到了符合规则的解找到解返回 true否则返回 false。
2. 回溯函数的终止条件
在 backtracking 函数中回溯的终止条件包括
当找到一个空白格子‘.’时尝试填入数字’1’到’9’。对于每个尝试的数字使用 isValid 函数检查其在当前位置是否符合数独规则。如果找到一个有效的数字则将其放入当前格子中并递归地调用 backtracking 继续填充下一个空白格子。如果当前尝试的数字不能使得数独的解合法则撤销当前的选择回溯尝试下一个数字。
3. 单层搜索的过程解题思路
在单层搜索的过程中
遍历数独的每个格子对于每个空白格子尝试填入数字’1’到’9’。使用 isValid 函数来检查填入的数字是否在当前行、当前列和当前3x3子数独内都没有重复出现。如果找到一个合法的填入方式则继续递归填充下一个空白格子如果找不到合法的填入方式则进行回溯。当所有空白格子都被填满且符合数独规则时数独问题得到解决。
判断一个数独棋盘是否合法主要依据以下三个维度进行检查 同行是否重复 对于每一行检查其中的每个数字是否唯一。遍历每一行使用一个集合或者数组来记录已经出现过的数字若再次出现相同数字则表示该行不合法。 同列是否重复 对于每一列检查其中的每个数字是否唯一。遍历每一列同样使用集合或数组记录已经出现过的数字如果重复出现则该列不合法。 9宫格是否重复 数独棋盘被分为9个3x3的子宫格。对于每个子宫格检查其中的数字是否唯一。通过计算当前位置所在的子宫格的起始行和起始列使用 (row / 3) * 3 和 (col / 3) * 3 计算遍历该子宫格内的所有数字同样使用集合或数组来记录已经出现过的数字若有重复则该子宫格不合法。
代码
class Solution {
private:// 回溯函数尝试解决数独问题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] .) {// 尝试填充数字1到9for(char k 1; k 9; k) {// 如果当前数字k在位置(i, j)合法if(isValid(i, j, k, board)) {board[i][j] k; // 放置数字k// 递归调用backtracking尝试填充下一个空白格if(backtracking(board)) return true;board[i][j] .; // 回溯撤销当前位置的填充}}return false; // 1-9都尝试过无解}}}return true; // 数独已解}// 检查在位置(row, col)填充字符val是否合法bool isValid(int row, int col, char val, vectorvectorchar 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;}}// 检查同一个3x3子数独内是否有重复int startRow (row / 3) * 3;int startCol (col / 3) * 3;for(int i startRow; i startRow 3; i) {for(int j startCol; j startCol 3; j) {if(board[i][j] val) {return false;}}}return true; // 合法}public:// 解决数独问题的入口函数void solveSudoku(vectorvectorchar board) {backtracking(board); // 调用回溯函数解决数独}
};
