泰安中呼网站建设有限公司 概况,wordpress注册未发送邮件,北京ui培训机构排行,局域网算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习三 01.字母大小写全排列02.优美的排列03.N 皇后04.有效的数独 01.字母大小写全排列
题目链接#xff1a;https://leetcode.cn/problems/letter-case-permutation/
给定一个字符串 s #xff0c;通过将字符串 s 中的每个字… 算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习三 01.字母大小写全排列02.优美的排列03.N 皇后04.有效的数独 01.字母大小写全排列
题目链接https://leetcode.cn/problems/letter-case-permutation/
给定一个字符串 s 通过将字符串 s 中的每个字母转变大小写我们可以获得一个新的字符串。
返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
示例 1
输入s a1b2
输出[a1b2, a1B2, A1b2, A1B2]示例 2:
输入: s 3z4
输出: [3z4,3Z4]提示:
1 s.length 12s 由小写英文字母、大写英文字母和数字组成
思路
在处理英文字母时每个元素存在三种情况
不进行处理如果当前字母是英文字母并且是大写将其修改为小写如果当前字母是英文字母并且是小写将其修改为大写。
代码
class Solution {string path;vectorstring ret;
public:vectorstring letterCasePermutation(string s) {dfs(s,0);return ret;}void dfs(string s,int pos){if(poss.size()){ret.push_back(path);return;}int chs[pos];path.push_back(ch);dfs(s,pos1);path.pop_back();if(ch0||ch9){int tmpchange(ch);path.push_back(tmp);dfs(s,pos1);path.pop_back();}}char change(char ch){if(chachz) ch-32;else ch32;return ch;}
};02.优美的排列
题目链接https://leetcode.cn/problems/beautiful-arrangement/
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm下标从 1 开始只要满足下述条件 之一 该数组就是一个 优美的排列
perm[i] 能够被 i 整除i 能够被 perm[i] 整除
给你一个整数 n 返回可以构造的 优美排列 的 数量 。
示例 1
输入n 2
输出2
解释
第 1 个优美的排列是 [1,2]- perm[1] 1 能被 i 1 整除- perm[2] 2 能被 i 2 整除
第 2 个优美的排列是 [2,1]:- perm[1] 2 能被 i 1 整除- i 2 能被 perm[2] 1 整除示例 2
输入n 1
输出1提示
1 n 15
思路 在这个问题中我们需要在每一个位置上考虑所有的可能情况并确保不出现重复。通过深度优先搜索的方式不断地枚举每个数在当前位置的可能性并回溯到上一个状态直到枚举完所有可能性得到正确的结果。为了实现这一目标可以采用以下步骤
定义一个变量用来记录所有可能的排列数量使用一个一维数组 visited 标记元素的使用情况从第一个位置开始进行递归枚举每个数的可能性。
通过这样的深度优先搜索过程可以得到所有符合条件的排列。
代码
class Solution {bool check[16];int ret0,n;
public:int countArrangement(int _n) {n_n;dfs(1);return ret;}void dfs(int pos){if(posn1){ret;return;}for(int i1;in;i){if(!check[i](pos%i0||i%pos0)){check[i]true;dfs(pos1);check[i]false;}}}
};03.N 皇后
题目链接https://leetcode.cn/problems/n-queens/
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
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
思路
首先在每一行放置第一个皇后然后遍历棋盘的第二行在可行的位置放置第二个皇后再遍历第三行以此类推直到放置了n个皇后为止。
为了记录每一行放置的皇后的列数使用一个数组来记录。在每一行中尝试放置一个皇后并检查是否与前面已经放置的皇后冲突。如果没有冲突继续递归地放置下一行的皇后直到所有皇后都放置完毕然后记录这个方案。
在检查皇后是否冲突时可以使用一个数组来记录每一列是否已经放置了皇后并检查当前要放置的皇后是否会和已经放置的皇后冲突。对于对角线可以使用两个数组来记录从左上角到右下角的每一条对角线上是否已经放置了皇后以及从右上角到左下角的每一条对角线上是否已经放置了皇后。
对于对角线是否冲突的判断可以通过以下流程解决
从左上到右下相同对角线的行列之差相同从右上到左下相同对角线的行列之和相同。
因此需要创建用于存储解决方案的二维字符串数组 ret用于存储每个皇后的位置的一维整数数组 path以及用于记录每一列和对角线上是否已经有皇后的布尔型数组 checkCol、checkDig1 和 checkDig2。
代码
class Solution {bool checkCol[10],checkDig1[20],checkDig2[20];vectorvectorstring ret;vectorstring path;int n;
public:vectorvectorstring solveNQueens(int _n) {n_n;path.resize(n,string(n,.));dfs(0);return ret;}void dfs(int row){if(rown){ret.push_back(path);return;}for(int col0;coln;col){if(!checkCol[col]!checkDig1[row-coln]!checkDig2[rowcol]){path[row][col]Q;checkCol[col]checkDig1[row-coln]checkDig2[rowcol]true;dfs(row1);path[row][col].;checkCol[col]checkDig1[row-coln]checkDig2[rowcol]false;}}}
};04.有效的数独
题目链接https://leetcode.cn/problems/valid-sudoku/
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 验证已经填入的数字是否有效即可。
数字 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]]
输出true示例 2
输入board
[[8,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]]
输出false
解释除了第一行的第一个数字从 5 改为 8 以外空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。思路
创建三个数组标记行、列以及 3*3 小方格中是否出现 1~9 之间的数字即可。
代码
class Solution {int row[9][10];int col[9][10];int grid[3][3][10];
public:bool isValidSudoku(vectorvectorchar board) {for(int i0;i9;i){for(int j0;j9;j){if(board[i][j]!.){int numboard[i][j]-0;if(!row[i][num]!col[j][num]!grid[i/3][j/3][num]){row[i][num]col[j][num]grid[i/3][j/3][num]1;}else return false;}}}return true;}
};
