字母大小写全排列

题目：字母大小写全排列

思路

对每个位置的字符有两种情况

• 不修改：数字字符，直接递归下一层；
• 修改：字母字符，大写改小写、小写改大写后，递归下一层；

C++代码

class Solution 
{string path;vector<string> ret;
public:vector<string> letterCasePermutation(string s) {dfs(s, 0);return ret;}void dfs(string& s, int pos){if(pos == s.size()){ret.push_back(path);return;}int ch = s[pos];// 不改变path.push_back(ch);dfs(s, pos + 1);path.pop_back();// 改变if(ch < '0' || ch > '9'){char t = change(ch);path.push_back(t);dfs(s, pos + 1);path.pop_back();}}char change(char ch){if(ch >= 'a' && ch <= 'z') ch -= 32;else ch += 32;return ch;}
};

优美的排列

题目：优美的排列

思路

我们可以使用回溯法解决本题，从左向右依次向目标排列中放入数即可

• 使用 check数组来跟踪哪些数字已经被使用过。
• 在每次递归中，检查当前排列是否符合优美排列的条件。
• 基于回溯生成所有排列： 在排列中逐步填充数字，并检查每一步是否满足条件。
• 统计符合条件的排列数量。

C++代码

class Solution 
{bool check[16];int ret;
public:int countArrangement(int n) {// 从下表为 1 开始枚举dfs(1, n);return ret;}void dfs(int pos, int n){if(pos == n + 1){ret++;return;}for(int i = 1; i <= n; i++){if(!check[i] && (pos % i == 0 || i % pos == 0)){check[i] = true;dfs(pos + 1, n);check[i] = false;}}}
};

N 皇后

题目：N 皇后

思路

在第一行放置第一个皇后，然后遍历棋盘的第二行，在合法的位置放置第二个皇后，再遍历第三行，以此类推，直到放置了n个皇后为止

• 从第一行开始，尝试在每一列放置皇后
• 对于每个放置位置，检查该位置的列和两个对角线是否已经被占用
• 如果该位置未被占用，则放置皇后，并标记相应的列和对角线为已占用
• 递归地尝试在下一行放置皇后
• 如果在当前行无法放置皇后（即所有列和对角线都被占用），则回溯，撤销上一行的皇后放置，并尝试在当前行的下一个位置放置皇后
• 当所有行都成功放置了皇后时，保存当前排列

C++代码

class Solution 
{bool checkCol[10], checkDig1[20], checkDig2[20];vector<vector<string>> ret;vector<string> path;int n;
public:vector<vector<string>> solveNQueens(int _n) {n = _n;path.resize(n, string(n, '.'));dfs(0);return ret;}void dfs(int row){if(row == n){ret.push_back(path);return;}for(int col = 0;col < n; col++){if(!checkCol[col] && !checkDig1[row-col+n] && !checkDig2[row+col]){path[row][col] = 'Q';checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;dfs(row + 1);path[row][col] = '.';checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;}}}
};

有效的数独

题目：有效的数独

思路

• 遍历棋盘的每一个格子
• 如果当前格子不是空字符.，则提取该字符代表的数字board[i][j] - '0'
• 检查这个数字在当前行、当前列和当前3x3子网格中是否已经出现过（通过查看row[i][num]、col[j][num]和grid[i/3][j/3][num]是否为0）
• 如果这个数字在任何一处已经出现过，则返回false，表示数独无效
• 如果这个数字在所有检查的地方都未出现过，则将其在row、col和grid中标记为已出现过（即将相应的位置设为1）
• 如果遍历完所有格子都没有发现重复数字，则返回true，表示数独有效

C++代码

class Solution 
{int row[9][10];int col[9][10];int grid[3][3][10];
public:bool isValidSudoku(vector<vector<char>>& board) {for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] != '.'){int num = board[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;}
};