跟着Carl学算法--回溯【2】

IP复原（难）

力扣链接：IP复原

题目：有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

思路：
$$回溯三问\{\begin{array}{l}\text{当前操作?枚举分隔符‘.’的位置（有三种情况，长度1，2，3）}\\ \text{子问题?从下标}\ge j\text{的后缀中继续修复IP}\\ \text{下一个子问题?从下标}\ge j+1\text{的后缀中继续修复IP}\end{array}$$
判断IP合法，即所枚举分割的字符串（从i开始，长度枚举）

1. 开头不为0（注意，这里是当长度大于1才有的约束，单单一个0完全可以，01就不行）
2. 转换成的数字小于等于255

边界情况

最后可能剩余长度不到3了

比如长度为4 ，i为3，j只能为1，即i+j>n会越界

注意这里：substr(i,j)，这里从下标为i的开始，长度为j，i为3说明前面有三个元素，所以i+j>n时才越界，而不是i+j≥n就越界

这里使用了vector<string>来定义路径，而不是string，优点有两个

• 可以在最后统一处理“.”，而不是每次加入path时就+”.“,不需要在最后一步额外再处理”.“
• 回溯方便，pop（）即可，不需要使用earse函数

stoi()，C++内置字符串转整型

class Solution {
public:vector<string> restoreIpAddresses(string s) {int n = s.size();vector<string> result;vector<string> path;if (n < 4 || n > 12)return {};auto dfs = [&](this auto&& dfs, int i) {if (i == n && path.size() == 4) {result.emplace_back(path[0] + '.' + path[1] + '.' + path[2] +'.' + path[3]);return;}// 剪枝函数，如果剩余字符数小于剩余段数，或者剩余字符数大于剩余段数乘以3，则不可能构成有效的IP地址if (n - i < 4 - path.size() || n - i > 3 * (4 - path.size()))return;for (int j = 1; j <= 3; j++) {if (i + j >n)break;string sub = s.substr(i, j);if (sub[0] == '0' && j > 1) //continue;if (std::stoi(sub) > 255)continue;path.emplace_back(sub);dfs(i + j);path.pop_back();}};dfs(0);return result;}
};

全排列

for (int i:unused) { //for增强循环path.push_back(i);unused.erase(i);//修改集合dfs();unused.insert(i);//修改集合
}

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<int> path;vector<vector<int>> result;bool used[6] = {false};int n = nums.size();auto dfs = [&](this auto&& dfs, int i) {if (i == n) {result.push_back(path);return;}for (int j = 0; j < n; j++) {if (used[j]) //使用过的元素不在使用continue;path.push_back(nums[j]);used[j] = true;dfs(i + 1);//回溯时记得连同使用过的元素一起回溯path.pop_back();used[j] = false;}};dfs(0);return result;}
};

全排列II

力扣链接：全排列II

题目：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

相较于全排列nums中有重复元素了
$$回溯三问\{\begin{array}{l}\text{当前操作?枚举nums中未使用过，且本层未使用过的元素}\\ \text{子问题?构造path的≥i+1的部分，剩余元素为{nums}-{x1}}\\ \text{下一个子问题?继续构造path的≥i+1的部分，剩余元素为{nums}-{x2}}\end{array}$$
思路：

思考：上一道题与非递减子序列的结合

只需要在上一道题的基础上加个本层去重即可，

应该​排序​+​相同​元素​跳过​或者​每​层​s​et​集合去重均可🤔

这里使用set集合去重

即bool数组用于避免同一个元素使用两次，set集合用于避免出现同一种排列（本层同一种（不是同一个元素选两次）

class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> result;vector<int> path;bool used[8] = {false}; // 此元素使用过int n = nums.size();auto dfs = [&](this auto&& dfs, int i) {if (i == n) {result.push_back(path);return;}unordered_set<int> curUsed; // 相等元素本层使用过for (int j = 0; j < n; j++) {if (used[j] || curUsed.find(nums[j]) != curUsed.end())continue;path.push_back(nums[j]);used[j] = true;curUsed.insert(nums[j]);dfs(i + 1);//回溯，因为set记录的是本层的重复元素，所以不需要回溯path.pop_back();used[j] = false;}};dfs(0);return result;}
};

N皇后

力扣链接：N皇后

题目：按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

思路：

与全排列类似，是枚举列号的全排列，举例，即[1，2，3，4]的全排列，数组的下标代表行号，内容代表列号，

在此基础上加了两个难点

1. 最终结果的输出[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
   • 遍历保存了每一行queen位置的queens数组，queen在第几列，就构造一个n个"."的字符串，同时构造一个n-1-queen（加起来一共是n个字符）位置个“.”字符串，两者通过一个Q进行拼接，即为答案
2. 每一组全排列要额外满足不在对角线上
   • 很巧妙很巧妙，复制的灵神的
   • 首先对角线分为两类，主对角线和副对角线，需要构造两个数组分别存储
   • 其次，对于同一条对角线，
     • 副对角线（左下到右上）：行数 +列数（r+c）相等，想象一下，r每-1,c就+1。
       范围【0，n*2-2】,因为r【0，n-1】，c【0，n-1】，两者相加的范围就是【0，2*n-2】
     • 主对角线（左上到右下）：行数 - 列数（r-c）相等，因为，同一条对角线上 r每+1，c就+1。
       范围【-(n-1)，n-1】,因为r【0，n-1】，-c【-(n-1)，0】，两者相加的范围就是【-(n-1)，n-1】
   • 基于以上思考，可以两者均定义为n*2-1的数组，副对角线计算时直接r+c即可，主对角线计算时为避免负索引，需要r-c+n-1

处理完这两个难点，这道题就和全排列的解决步骤相同了

class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<vector<string>> ans;vector<int> queens(n); // queens 数组用于存储皇后的位置，queens[r] 表示第 r 行的皇后放在了第 queens[r] 列//这里标记位置的col，diag本来bool类型即可，但是灵神说int效率更高vector<int> col(n);// col 数组用于标记每一列是否已经被占用vector<int> diag1(n * 2 - 1); // diag1 数组用于标记副对角线（左下到右上）是否已经被占用// r + c 的值在同一条副对角线上是相同的vector<int> diag2(n * 2 - 1); // diag2 数组用于标记主对角线（左上到右下）是否已经被占用// r - c + n - 1 的值在同一条主对角线上是相同的auto dfs = [&](this auto&& dfs, int r) {//结束if (r == n) {//将queens数组生成字符串，并整合为答案vector<string> board(n);for (int i = 0; i < n; i++) {// 使用字符串构造函数生成一行，先生成 queens[i] 个 '.'，然后是 'Q'，最后是 n - 1 - queens[i] 个 '.board[i] = string(queens[i], '.') + 'Q' + string(n - 1 - queens[i], '.');}ans.push_back(board);return;}// 在第 r 行的每一列尝试放置皇后for (int c = 0; c < n; c++) {// 计算当前位置所在的副对角线的索引int rc = r - c + n - 1;// 如果当前列和两条对角线都没有被占用，说明可以在当前位置放置皇后if (!col[c] && !diag1[r + c] && !diag2[rc]) { //!col[c]即为与全排列的元素不能重复的逻辑实现queens[r] = c;// 标记当前列和两条对角线已经被占用col[c] = diag1[r + c] = diag2[rc] = true;// 递归调用 dfs，尝试在下一行放置皇后dfs(r + 1);// 恢复现场，回溯到上一步，尝试在其他位置放置皇后col[c] = diag1[r + c] = diag2[rc] = false;}}};dfs(0);return ans;}
};

解数独

力扣链接：解数独

题目：编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

思路：

难点：

1. 当前位置枚举数字的合法性检测
2. 二维递归

合法性检测：3X3范围内只出现一次？

可以先将范围定位到就九个中棋盘，即row/3定位到纵向三个位置中的一个，同理col也是，0，即代表前面有0个粗化的行（即3个细行），其他同理
定位到中位置后，再进一步将大体位置细化到具体的起始行和列，将原来的大体位置*3即可，因为一个行号或者列号对应三个细化的行和列，

以行为例，【0，1，2】分别即对应【0，3，6】

然后知道起始行也知道长度，遍历九宫格即可

for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val) {return false;}}}

二维递归

要始终明白，下一个子问题是从填充后面所有位置，而不是填充从下一行开始到结束的所有位置

名称一样二维递归

auto dfs = [&](this auto&& dfs, int row) -> bool {for(int i = row; i < 9; i++)  //（上一层填充了一个位置）从当前行开始重新遍历，更好的做法是直接定位到某行某列，//但是不易于实现和理解for (int j = 0; j < 9; j++) {if (board[i][j] == '.') {for (char num = '1'; num <= '9'; num++) {if (isValid(i, j, num, board)) {board[i][j] = num;if (dfs(i))  //深入判断，只有此处一直为真才会返回真，//当路径偏差时（即上一层为真，但是导致下一层所有数字都不可填入时），会返回假return true;board[i][j] = '.';}}//无论前面是否填充，进行到这一步就返回false，//当前面九个数字都不满足时返回 false//一旦有数字满足就会深入分支，进行进一步深入判断，return false;}}//遍历结束，直接返回真即可，只要遍历到最后，说明前面都符合，//中途一个位置出现了所有数字都不能填充当前位置时（即填充行为无法进行时），就会return falsereturn true;};