YOLOのBLOG
回溯算法问题
felicx 化神
  2023 年 04 月 02 日 12:22 2023-04-02 12:22   2023 年 04 月 02 日 12:40      2.9k 字  13 分钟  

一、全排列（中）

题目

给定一个不含重复数字的数组 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]]$

提示：
$1 <= nums.length <= 6$
$-10 <= nums[i] <= 10$
nums 中的所有整数 互不相同

题解1

这道题可以用『回溯算法』来解决。
看下面这张图，应该就好理解了
image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 private:
  vector<vector<int>> result;  // 存储结果
  vector<int> track;           // 存储当前路径

 public:
  vector<vector<int>> permute(vector<int>& nums) {
    backtrack(nums, 0);  // 回溯函数
    return result;
  }

  // 路径：记录在 track 中
  // 选择列表：nums 中不存在于 track 中的元素
  // 结束条件：遍历完所有行, 即 index = nums.size()
  void backtrack(vector<int>& nums, int index) {
    // index为当前枚举的位置
    if (index == nums.size()) {
      // 遍历完数组中最后一个数字,把当前组合加入结果
      result.push_back(track);
      return;
    }

    for (int i = 0; i < nums.size(); i++) {
      if (find(track.begin(), track.end(), nums[i]) != track.end()) {
        // 排除不合法的选择
        continue;
      }
      track.push_back(nums[i]);  // 做选择,将当前元素添加到路径中
      backtrack(nums, index + 1);  // 进⼊下⼀层决策树
      track.pop_back();  // 撤销选择,将当前元素从路径中弹出
    }
  }
};

题解2

上面的解法中，排除不合法的选择是通过查找track中元素来排除的，速度有点慢。
简单的方法就是维护一个数组，用来记录每个数字的使用情况，遍历nums时直接判断数字使用情况来排除不合法的选择。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  vector<vector<int>> result; // 存储结果
  vector<int> track;  // 存储当前路径
  vector<bool> used;    // 数字是否使用

 public:
  vector<vector<int>> permute(vector<int>& nums) {
    used = vector<bool>(nums.size());
    backtrack(nums, 0);
    return result;
  }

  void backtrack(vector<int>& nums, int index) {
    // index为当前枚举的位置
    if (index == nums.size()) {
      // 遍历完数组中最后一个数字,把当前组合加入结果
      result.push_back(track);
      return;
    }
    for (int i = 0; i < nums.size(); i++) {
      if (used[i]) {
        continue;
      }
      // 当前数字没有使用,加入组合
      track.push_back(nums[i]);
      // 更新使用状态
      used[i] = true;
      // 继续搜索下一个位置
      backtrack(nums, index + 1);
      // 回退使用状态
      used[i] = false;
      // 把数字从当前组合中删除
      track.pop_back();
    }
  }
};

二、全排列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$

题解

这道题和『全排列』区别就在于数字是与重复的，那我们就需要在做回溯前先把已经枚举过的数字去重。

有两种情况，
1、数字已使用过；
2、前后数字重复且前面数字已经使用过（这个我们就需要先对数组排序，让相同的数字都在一块）。
其余的照搬『全排列』的回溯就ok了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
  vector<vector<int>> result; // 存储结果
  vector<int> track;  // 存储当前路径
  vector<bool> used;    // 数字是否使用

 public:
  vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());  // 先排个序,让重复的数字都在一块
    used = vector<bool>(nums.size());
    backtrack(nums, 0);
    return result;
  }

  void backtrack(vector<int>& nums, int index) {
    // idx为当前枚举的位置
    if (index == nums.size()) {
      // 遍历完数组中最后一个数字,把当前组合加入结果
      result.push_back(track);
      return;
    }
    unordered_set<int> s;
    for (int i = 0; i < nums.size(); i++) {
      if (used[i] || (i > 0 && nums[i] == nums[i - 1] && used[i - 1])) {
        // 1、数字已使用过; 2、前后数字重复且前面数字已经使用过
        continue;
      }
      // 当前数字没有使用,加入组合
      track.push_back(nums[i]);
      // 更新使用状态
      used[i] = true;
      // 继续搜索下一个位置
      backtrack(nums, index + 1);
      // 回退使用状态
      used[i] = false;
      // 把数字从当前组合中删除
      track.pop_back();
    }
  }
};

三、N皇后（困）

题目

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例 1：
image
输入：$n = 4$
输出：$[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]$
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：
输入：$n = 1$
输出：$[[“Q”]]$

提示：
$1 <= n <= 9$

题解

下面我用一个 3 * 3 的棋盘，将搜索过程抽象为一棵树，如图：
image
根据回溯模板，
1、定义全局变量二维数组board来记录最终结果。
参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了。

1
vector<string> board(n, string(n, '.'));

2、根据上图可以看出，当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了。

1
2
3
4
if (row == board.size()) {
  res.push_back(board);
  return;
}

3、递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。
每次都是要从新的一列的起始位置开始搜，所以都是从0开始。

1
2
3
4
5
6
7
8
9
10
11
12
for (int col = 0; col < n; col++) {
  // 排除不合法选择
  if (!isValid(board, row, col)) {
    continue;
  }
  // 做选择
  board[row][col] = 'Q';
  // 进⼊下⼀行决策
  backtrack(board, row + 1);
  // 撤销选择
  board[row][col] = '.';
}

4、看一下皇后们的约束条件：不能同行、不能同列、不能同斜线。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isValid(vector<string>& board, int row, int col) {
  int n = board.size();
  // 检查列是否有皇后互相冲突
  for (int i = 0; i < n; i++) {
    if (board[i][col] == 'Q')
      return false;
  }
  // 检查右上方是否有皇后互相冲突
  for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
    if (board[i][j] == 'Q')
      return false;
  }
  // 检查左上方是否有皇后互相冲突
  for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
    if (board[i][j] == 'Q')
      return false;
  }
  return true;
}

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
  vector<vector<string>> res;

 public:
  /* 输⼊棋盘边⻓ n，返回所有合法的放置 */
  vector<vector<string>> solveNQueens(int n) {
    // n x n的棋盘，n行，每行1个元素，大小为n的string
    // '.' 表⽰空，'Q' 表⽰皇后，初始化空棋盘。
    vector<string> board(n, string(n, '.'));
    backtrack(board, 0);
    return res;
  }
  // 路径：board 中小于 row 的那些行都已经成功放置了皇后
  // 选择列表：第 row 行的所有列都是放置皇后的选择
  // 结束条件：row 超过 board 的最后⼀行
  void backtrack(vector<string>& board, int row) {
    // 触发结束条件
    if (row == board.size()) {
      res.push_back(board);
      return;
    }
    int n = board[row].size();
    for (int col = 0; col < n; col++) {
      // 排除不合法选择
      if (!isValid(board, row, col)) {
        continue;
      }
      // 做选择
      board[row][col] = 'Q';
      // 进⼊下⼀行决策
      backtrack(board, row + 1);
      // 撤销选择
      board[row][col] = '.';
    }
  }

  /* 是否可以在 board[row][col] 放置皇后？ */
  bool isValid(vector<string>& board, int row, int col) {
    int n = board.size();
    // 检查列是否有皇后互相冲突
    for (int i = 0; i < n; i++) {
      if (board[i][col] == 'Q')
        return false;
    }
    // 检查右上方是否有皇后互相冲突
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] == 'Q')
        return false;
    }
    // 检查左上方是否有皇后互相冲突
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] == 'Q')
        return false;
    }
    return true;
  }
};

四、复原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 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：
输入：s = “25525511135”
输出：[“255.255.11.135”,”255.255.111.35”]

示例 2：
输入：s = “0000”
输出：[“0.0.0.0”]

示例 3：
输入：s = “101023”
输出：[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]

提示：
1 <= s.length <= 20
s 仅由数字组成

题解

用回溯的话，把递归树画出来就清晰了。
image

  • 从字符串的开头开始，每次尝试截取1到3个字符，判断是否是合法的片段；
    • 一个片段的长度是 1~3
    • 片段的值范围是 0~255
    • 不能是 “0x”、”0xx” 形式
  • 如果是，就加入到当前的IP地址中，并继续向后搜索，直到找到四个整数或者字符串结束。
  • 如果找到了四个整数且字符串刚好结束，就说明找到了一个有效的IP地址，可以加入到结果集中。
  • 如果没有找到四个整数或者字符串还有剩余，就说明这条搜索路径不可行，需要回溯到上一步，尝试其他的截取方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
 private:
  vector<string> result;  // 存储结果

 public:
  vector<string> restoreIpAddresses(string s) {
    // 剪枝操作
    if (s.size() < 4 || s.size() > 12)
      return result;
    backtrack(s, 0, 0);
    return result;
  }

  // 回溯函数
  void backtrack(string& s, int startIndex, int pointNum) {
    // 如果已经找到了 3 个点，且剩余的字符串也是合法的，则将结果加入到 result 中
    if (pointNum == 3) {
      if (isValid(s, startIndex, s.size() - 1)) {
        result.emplace_back(s);
      }
      return;
    }
    // 枚举下一个点的位置
    for (int i = startIndex; i < s.size(); ++i) {
      // 如果当前位置是合法的，则在当前位置加入一个点
      if (isValid(s, startIndex, i)) {
        s.insert(s.begin() + i + 1, '.');
        ++pointNum;
        // 继续递归查找下一个点
        backtrack(s, i + 2, pointNum);
        --pointNum;
        // 将加入的点移除
        s.erase(s.begin() + i + 1);
      } else {
        // 如果当前位置不合法，则直接退出循环
        break;
      }
    }
  }

  // 判断字符串 s 中从 start 到 end 位置的子串是否合法
  bool isValid(string s, int start, int end) {
    if (start > end)
      return false;
    if (s[start] == '0' && start != end)
      return false;
    // 判断字符串中的数字是否合法
    int num = 0;
    for (int i = start; i <= end; ++i) {
      if (s[i] > '9' || s[i] < '0') {
        return false;
      }
      // 计算字符串对应的数字
      num = num * 10 + (s[i] - '0');
      if (num > 255)
        return false;
    }
    return true;
  }
};
回溯算法问题
2199921100.html
作者
felicx
发布于
2023-04-02 12:22
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 一、全排列（中）
    1. 题目
    2. 题解1
    3. 题解2
  2. 二、全排列II（中）
    1. 题目
    2. 题解
  3. 三、N皇后（困）
    1. 题目
    2. 题解
  4. 四、复原IP地址（中）
    1. 题目
    2. 题解
© 2018 - 2024    felicx
由 Hexo 驱动 & 主题 Keep
访客数 访问量
  1. 一、全排列（中）
    1. 题目
    2. 题解1
    3. 题解2
  2. 二、全排列II（中）
    1. 题目
    2. 题解
  3. 三、N皇后（困）
    1. 题目
    2. 题解
  4. 四、复原IP地址（中）
    1. 题目
    2. 题解