排列与棋盘问题

Channing Hsu
  2024-07-09 15:14:37 2024-07-09 15:14:37 创建   2024-12-03 01:50:49 2024-12-03 01:50:49 更新      9.1k 字  36 分钟  

46.全排列

力扣题目链接

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

  • 输入: [1,2,3]
  • 输出:
    [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
    ]

回溯三部曲

  • 递归函数参数

首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。

但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:

46.全排列

代码如下：

1
2
3
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used)
  • 递归终止条件

46.全排列

可以看出叶子节点，就是收割结果的地方。

那么什么时候，算是到达叶子节点呢？

当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

代码如下：

1
2
3
4
5
// 此时说明找到了一组
if (path.size() == nums.size()) {
    result.push_back(path);
    return;
}
  • 单层搜索的逻辑

这里和77.组合问题、131.切割问题和78.子集问题最大的不同就是for循环里不用startIndex了。

因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。

而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。

代码如下：

1
2
3
4
5
6
7
8
for (int i = 0; i < nums.size(); i++) {
    if (used[i] == true) continue; // path里已经收录的元素，直接跳过
    used[i] = true;
    path.push_back(nums[i]);
    backtracking(nums, used);
    path.pop_back();
    used[i] = false;
}

整体C++代码如下：

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
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == true) continue; // path里已经收录的元素，直接跳过
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};
  • 时间复杂度: O(n!)
  • 空间复杂度: O(n)

总结

大家此时可以感受出排列问题的不同：

  • 每层都是从0开始搜索而不是startIndex
  • 需要used数组记录path里都放了哪些元素了

47.全排列 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.全排列的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。

这里又涉及到去重了。

在40.组合总和II 、90.子集II我们分别详细讲解了组合问题和子集问题如何去重。

那么排列问题其实也是一样的套路。

还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

我以示例中的 [1,1,2]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程如图：

47.全排列II1

图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。

一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

在46.全排列中已经详细讲解了排列问题的写法，在40.组合总和II 、90.子集II中详细讲解了去重的写法，所以这次我就不用回溯三部曲分析了，直接给出代码，如下：

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 {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            if (used[i] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

// 时间复杂度: 最差情况所有元素都是唯一的。复杂度和全排列1都是 O(n! * n) 对于 n 个元素一共有 n! 中排列方案。而对于每一个答案，我们需要 O(n) 去复制最终放到 result 数组
// 空间复杂度: O(n) 回溯树的深度取决于我们有多少个元素
  • 时间复杂度: O(n! * n)
  • 空间复杂度: O(n)

拓展

大家发现，去重最为关键的代码为：

1
2
3
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}

**如果改成 used[i - 1] == true， 也是正确的!**去重代码如下：

1
2
3
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
    continue;
}

这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。

对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！

这么说是不是有点抽象？

来来来，我就用输入: [1,1,1] 来举一个例子。

树层上去重(used[i - 1] == false)，的树形结构如下：

47.全排列II2

树枝上去重（used[i - 1] == true）的树型结构如下：

47.全排列II3

大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

总结

这道题其实还是用了我们之前讲过的去重思路，但有意思的是，去重的代码中，这么写：

1
2
3
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}

和这么写：

1
2
3
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
    continue;
}

都是可以的，这也是很多同学做这道题目困惑的地方，知道used[i - 1] == false也行而used[i - 1] == true也行，但是就想不明白为啥。

所以我通过举[1,1,1]的例子，把这两个去重的逻辑分别抽象成树形结构，大家可以一目了然：为什么两种写法都可以以及哪一种效率更高！

这里可能大家又有疑惑，既然 used[i - 1] == false也行而used[i - 1] == true也行，那为什么还要写这个条件呢？

直接这样写 不就完事了？

1
2
3
if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

其实并不行，一定要加上 used[i - 1] == false或者used[i - 1] == true，因为 used[i - 1] 要一直是 true 或者一直是false 才可以，而不是 一会是true 一会又是false。 所以这个条件要写上。

是不是豁然开朗了！！

332.重新安排行程

力扣题目链接

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

提示：

  • 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
  • 所有的机场都用三个大写字母表示（机场代码）。
  • 假定所有机票至少存在一种合理的行程。
  • 所有的机票必须都用一次 且 只能用一次。

示例 1：

  • 输入：[[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]
  • 输出：[“JFK”, “MUC”, “LHR”, “SFO”, “SJC”]

示例 2：

  • 输入：[[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]
  • 输出：[“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”]
  • 解释：另一种有效的行程是 [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”]。但是它自然排序更大更靠后。

思路一

直觉上来看 这道题和回溯法没有什么关系，更像是图论中的深度优先搜索。

实际上确实是深搜，但这是深搜中使用了回溯的例子，在查找路径的时候，如果不回溯，怎么能查到目标路径呢。

所以我倾向于说本题应该使用回溯法，那么我也用回溯法的思路来讲解本题，其实深搜一般都使用了回溯法的思路，在图论系列中我会再详细讲解深搜。

这里就是先给大家拓展一下，原来回溯法还可以这么玩！

这道题目有几个难点：

  1. 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
  2. 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
  3. 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
  4. 搜索的过程中，如何遍历一个机场所对应的所有机场。

针对以上问题我来逐一解答！

如何理解死循环

对于死循环，我来举一个有重复机场的例子：

332.重新安排行程

为什么要举这个例子呢，就是告诉大家，出发机场和到达机场也会重复的，如果在解题的过程中没有对集合元素处理好，就会死循环。

该记录映射关系

有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？

一个机场映射多个机场，机场之间要靠字母序排列，一个机场映射多个机场，可以使用std::unordered_map，如果让多个机场之间再有顺序的话，就是用std::map 或者std::multimap 或者 std::multiset。

如果对map 和 set 的实现机制不太了解，也不清楚为什么 map、multimap就是有序的同学，可以看这篇文章关于哈希表，你该了解这些！。

这样存放映射关系可以定义为 unordered_map<string, multiset<string>> targets 或者 unordered_map<string, map<string, int>> targets。

含义如下：

unordered_map<string, multiset<string>> targets：unordered_map<出发机场, 到达机场的集合> targets

unordered_map<string, map<string, int>> targets：unordered_map<出发机场, map<到达机场, 航班次数>> targets

这两个结构，我选择了后者，因为如果使用unordered_map<string, multiset<string>> targets 遍历multiset的时候，不能删除元素，一旦删除元素，迭代器就失效了。

再说一下为什么一定要增删元素呢，正如开篇我给出的图中所示，出发机场和到达机场是会重复的，搜索的过程没及时删除目的机场就会死循环。

所以搜索的过程中就是要不断的删multiset里的元素，那么推荐使用unordered_map<string, map<string, int>> targets。

在遍历 unordered_map<出发机场, map<到达机场, 航班次数>> targets的过程中，可以使用"航班次数"这个字段的数字做相应的增减，来标记到达机场是否使用过了。

如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。

相当于说我不删，我就做一个标记！

回溯法

这道题目我使用回溯法，那么下面按照我总结的回溯模板来：

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

本题以输入：[[“JFK”, “KUL”], [“JFK”, “NRT”], [“NRT”, “JFK”]为例，抽象为树形结构如下：

332.重新安排行程1

开始回溯三部曲讲解：

  • 递归函数参数

在讲解映射关系的时候，已经讲过了，使用unordered_map<string, map<string, int>> targets; 来记录航班的映射关系，我定义为全局变量。

当然把参数放进函数里传进去也是可以的，我是尽量控制函数里参数的长度。

参数里还需要ticketNum，表示有多少个航班（终止条件会用上）。

代码如下：

1
2
3
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {

注意函数返回值我用的是bool！

我们之前讲解回溯算法的时候，一般函数返回值都是void，这次为什么是bool呢？

因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线，如图：

332.重新安排行程1

所以找到了这个叶子节点了直接返回，这个递归函数的返回值问题我们在讲解二叉树的系列的时候，在这篇二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？详细介绍过。

当然本题的targets和result都需要初始化，代码如下：

1
2
3
4
for (const vector<string>& vec : tickets) {
    targets[vec[0]][vec[1]]++; // 记录映射关系
}
result.push_back("JFK"); // 起始机场
  • 递归终止条件

拿题目中的示例为例，输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] ，这是有4个航班，那么只要找出一种行程，行程里的机场个数是5就可以了。

所以终止条件是：我们回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程，把所有航班串在一起了。

代码如下：

1
2
3
if (result.size() == ticketNum + 1) {
    return true;
}

已经看习惯回溯法代码的同学，到叶子节点了习惯性的想要收集结果，但发现并不需要，本题的result相当于 回溯算法：求组合总和！中的path，也就是本题的result就是记录路径的（就一条），在如下单层搜索的逻辑中result就添加元素了。

  • 单层搜索的逻辑

回溯的过程中，如何遍历一个机场所对应的所有机场呢？

这里刚刚说过，在选择映射函数的时候，不能选择unordered_map<string, multiset<string>> targets， 因为一旦有元素增删multiset的迭代器就会失效，当然可能有牛逼的容器删除元素迭代器不会失效，这里就不在讨论了。

可以说本题既要找到一个对数据进行排序的容器，而且还要容易增删元素，迭代器还不能失效。

所以我选择了unordered_map<string, map<string, int>> targets 来做机场之间的映射。

遍历过程如下：

1
2
3
4
5
6
7
8
9
for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
    if (target.second > 0 ) { // 记录到达机场是否飞过了
        result.push_back(target.first);
        target.second--;
        if (backtracking(ticketNum, result)) return true;
        result.pop_back();
        target.second++;
    }
}

可以看出 通过unordered_map<string, map<string, int>> targets里的int字段来判断 这个集合里的机场是否使用过，这样避免了直接去删元素。

分析完毕，此时完整C++代码如下：

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
class Solution {
private:
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {
    if (result.size() == ticketNum + 1) {
        return true;
    }
    for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
        if (target.second > 0 ) { // 记录到达机场是否飞过了
            result.push_back(target.first);
            target.second--;
            if (backtracking(ticketNum, result)) return true;
            result.pop_back();
            target.second++;
        }
    }
    return false;
}
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targets.clear();
        vector<string> result;
        for (const vector<string>& vec : tickets) {
            targets[vec[0]][vec[1]]++; // 记录映射关系
        }
        result.push_back("JFK"); // 起始机场
        backtracking(tickets.size(), result);
        return result;
    }
};

一波分析之后，可以看出我就是按照回溯算法的模板来的。

代码中

1
for (pair<const string, int>& target : targets[result[result.size() - 1]])

一定要加上引用即 & target，因为后面有对 target.second 做减减操作，如果没有引用，单纯复制，这个结果就没记录下来，那最后的结果就不对了。

加上引用之后，就必须在 string 前面加上 const，因为map中的key 是不可修改了，这就是语法规定了。

总结

如果单纯的回溯搜索（深搜）并不难，难还难在容器的选择和使用上。

本题其实是一道深度优先搜索的题目，但是我完全使用回溯法的思路来讲解这道题题目，算是给大家拓展一下思维方式，其实深搜和回溯也是分不开的，毕竟最终都是用递归。

如果最终代码，发现照着回溯法模板画的话好像也能画出来，但难就难如何知道可以使用回溯，以及如果套进去，所以我再写了这么长的一篇来详细讲解。

思路二

当解决题目涉及到重新安排航线的问题时，我们可以将其抽象为图论中的欧拉路径问题。欧拉路径问题（Eulerian Path Problem）是图论中一个经典的问题，主要研究的是在一个图中找到一条路径，该路径经过图中的每条边恰好一次。

这种问题的特点是，我们需要从一个起始点出发，沿着边依次访问所有的边且每条边仅访问一次，最终回到起始点。

分析

  1. 建立图的表示：
    • 给定的航线列表 tickets 可以看作是一个有向图，其中每个机场表示图中的节点，每张机票表示图中的一条有向边。
    • 邻接表（Adjacency List）是一种用于表示图的数据结构。它通过将图中的每个顶点（节点）和与之直接相连的边存储起来，来描述图的结构。邻接表通常用于表示稀疏图（Sparse Graph），其中顶点的数量相对较少，但是顶点之间的边比较多的情况。
    • 我们使用一个哈希表 unordered_map<string, priority_queue<string, vector<string>, greater<string>>>> graph 来构建邻接表表示图。这里使用 priority_queue 是为了保证从每个机场出发的目的地按照字典序排列。
  2. 深度优先搜索（DFS）：
    • 从起始点 JFK 开始进行深度优先搜索。每次访问一个节点时，按照字典序依次选择下一个未访问的目的地进行递归访问。
    • 如果当前节点没有可访问的目的地，将当前节点加入到结果路径中。这样递归下去，直到找到一条完整的路径或者无法继续为止。
  3. 路径的处理：
    • 由于DFS的性质，最终得到的路径是从最后一个节点到第一个节点的反向路径。因此，我们在返回结果之前，需要将路径反转，得到从起始点 JFK 开始的正向路径。

代码实现解释

下面是详细的代码实现，帮助理解如何通过深度优先搜索来解决题目要求的航线重排问题：

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
class Solution {
private:
    unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph;
    vector<string> result;
    
    void dfs(const string& from) {
        auto& dests = graph[from];
        while (!dests.empty()) {
            string to = dests.top();  // 按字典序选择最小的目的地
            dests.pop();
            dfs(to);  // 继续从目的地出发进行DFS
        }
        result.push_back(from);  // 将当前节点加入结果路径中
    }
    
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        // 构建图的邻接表，用优先队列保证目的地字典序最小
        for (const auto& ticket : tickets) {
            graph[ticket[0]].push(ticket[1]);
        }
        
        // 从 JFK 开始进行 DFS 遍历
        dfs("JFK");
        
        // 结果是反向存储的，需要翻转一下得到正向路径
        reverse(result.begin(), result.end());
        return result;
    }
};

关键点解释

  • 图的构建： 使用 unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph，其中 string 表示机场名称，priority_queue 用于存储从每个机场出发的目的地列表，保证了目的地按照字典序排列。

  • DFS 函数： dfs 函数从给定的起始点开始递归遍历，每次选择当前节点的字典序最小的目的地进行下一步递归。当当前节点没有可选目的地时，将当前节点加入结果路径中。

  • 结果处理： 因为DFS的性质是反向存储路径，所以需要在返回结果之前将路径反转，得到正确的从 JFK 开始的路径序列。

总结

通过深度优先搜索和图的邻接表表示，我们可以有效地解决航线重新规划的问题。这种方法不仅能够保证找到一条有效路径，还能够保证路径的字典序最小，符合题目的要求。

解释邻接图

unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph 是一个复杂的数据结构，用于在C++中表示有向图的邻接表。

  1. unordered_map<string, ...>
  • unordered_map 是 C++ 标准库中的一种哈希表实现，用于存储键-值对。
  • 在这里，unordered_map<string, ...> 的键（key）是机场的名称（字符串类型），值（value）是一个 priority_queue<string, vector<string>, greater<string>>。
  1. priority_queue<string, vector<string>, greater<string>>
  • priority_queue 是 C++ 标准库中的优先队列容器，它会根据指定的比较函数来自动排序元素。
  • 在这里，priority_queue<string, vector<string>, greater<string>> 的含义是：
    • 存储的元素类型是 string。
    • 内部使用 vector<string> 作为基础容器。
    • 使用 greater<string> 作为比较函数，这意味着队列会按照字典序的反序（即逆序）排列元素，即较小的元素在队头，较大的元素在队尾。
  1. 组合在一起的意义

将 unordered_map<string, priority_queue<string, vector<string>, greater<string>>> 结合起来，可以实现以下功能：

  1. 图的表示： unordered_map 用于存储从每个机场出发的航班信息。
  2. 邻接表的使用： 对于每个机场名称作为键，其对应的值是一个 priority_queue，存储了以该机场为起点的所有航班的目的地列表。
  3. 自动排序： 每个机场的目的地列表会按照字典序逆序存储，使得在需要访问机场的目的地时，能够优先选择字典序较小的目的地。

示例

假设有以下航线信息：

1
2
3
4
5
6
7
vector<vector<string>> tickets = {
    {"JFK", "SFO"},
    {"JFK", "ATL"},
    {"SFO", "ATL"},
    {"ATL", "JFK"},
    {"ATL", "SFO"}
};

我们可以通过 unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph 构建如下邻接表：

  • 对于机场 “JFK”：

    • graph["JFK"] 包含 priority_queue，其中包含 "ATL", "SFO"，这些目的地按照字典序逆序排列。

  • 对于机场 “SFO”：

    • graph["SFO"] 包含 priority_queue，其中包含 "ATL"，这个目的地按照字典序逆序排列。

  • 对于机场 “ATL”：

    • graph["ATL"] 包含 priority_queue，其中包含 "JFK", "SFO"，这些目的地按照字典序逆序排列。

使用场景

这种数据结构特别适合需要按照特定顺序访问节点的图算法，比如深度优先搜索（DFS）或广度优先搜索（BFS）。在航线规划问题中，我们可以利用这种结构保证每次选择下一个目的地时都是按照字典序最小的，从而实现题目要求的最小行程规划。

通过深入理解 unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph 的结构和使用方法，可以更好地应对类似的图论问题。

51. N皇后

力扣题目链接

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

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

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

示例 1：

img

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

示例 2：

  • 输入：n = 1
  • 输出：[[“Q”]]

思路

都知道n皇后问题是回溯算法解决的经典问题，但是用回溯解决多了组合、切割、子集、排列问题之后，遇到这种二维矩阵还会有点不知所措。

首先来看一下皇后们的约束条件：

  1. 不能同行
  2. 不能同列
  3. 不能同斜线

确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。

下面我用一个 3 * 3 的棋盘，将搜索过程抽象为一棵树，如图：

51.N皇后

从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。

那么我们用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。

回溯三部曲

按照我总结的如下回溯模板，我们来依次分析：

1
2
3
4
5
6
7
8
9
10
11
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
  • 递归函数参数

我依然是定义全局变量二维数组result来记录最终结果。

参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了。

代码如下：

1
2
vector<vector<string>> result;
void backtracking(int n, int row, vector<string>& chessboard) {
  • 递归终止条件

在如下树形结构中：
51.N皇后

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

代码如下：

1
2
3
4
if (row == n) {
    result.push_back(chessboard);
    return;
}
  • 单层搜索的逻辑

递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。

每次都是要从新的一行的起始位置开始搜，所以都是从0开始。

代码如下：

1
2
3
4
5
6
7
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] = '.'; // 回溯，撤销皇后
    }
}
  • 验证棋盘是否合法

按照如下标准去重：

  1. 不能同行
  2. 不能同列
  3. 不能同斜线 （45度和135度角）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isValid(int row, int col, vector<string>& chessboard, int n) {
    // 检查列
    for (int i = 0; i < row; i++) { // 这是一个剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 检查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

在这份代码中，细心的同学可以发现为什么没有在同行进行检查呢？

因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重了。

那么按照这个模板不难写出如下C++代码：

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
class Solution {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋盘的第几行了
void backtracking(int n, int row, vector<string>& 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, vector<string>& chessboard, int n) {
    // 检查列
    for (int i = 0; i < row; i++) { // 这是一个剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 检查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return result;
    }
};
  • 时间复杂度: O(n!)
  • 空间复杂度: O(n)

可以看出，除了验证棋盘合法性的代码，省下来部分就是按照回溯法模板来的。

总结

本题是我们解决棋盘问题的第一道题目。

如果从来没有接触过N皇后问题的同学看着这样的题会感觉无从下手，可能知道要用回溯法，但也不知道该怎么去搜。

这里我明确给出了棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了。

大家可以在仔细体会体会！

37. 解数独

力扣题目链接(opens new window)

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

一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 ‘.’ 表示。

解数独

一个数独。

解数独

答案被标成红色。

提示：

  • 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

思路

棋盘搜索问题可以使用回溯法暴力搜索，只不过这次我们要做的是二维递归。

怎么做二维递归呢？

大家已经跟着代码随想录刷过了如下回溯法题目，例如：77.组合（组合问题），131.分割回文串（分割问题），78.子集（子集问题），46.全排列（排列问题），以及51.N皇后（N皇后问题），其实这些题目都是一维递归。

如果以上这几道题目没有做过的话，不建议上来就做这道题哈！

N皇后问题是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置。

本题就不一样了，本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。

因为这个树形结构太大了，我抽取一部分，如图所示：

37.解数独

回溯三部曲

  • 递归函数以及参数

递归函数的返回值需要是bool类型，为什么呢？

因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值。

代码如下：

1
bool backtracking(vector<vector<char>>& board)
  • 递归终止条件

本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。

不用终止条件会不会死循环？

递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件！

那么有没有永远填不满的情况呢？

这个问题我在递归单层搜索逻辑里再来讲！

  • 递归单层搜索逻辑

37.解数独

在树形图中可以看出我们需要的是一个二维的递归 （一行一列）

一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！

代码如下：（详细看注释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool backtracking(vector<vector<char>>& board) {
    for (int i = 0; i < board.size(); i++) {        // 遍历行
        for (int j = 0; j < board[0].size(); j++) { // 遍历列
            if (board[i][j] != '.') continue;
            for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适
                if (isValid(i, j, k, board)) {
                    board[i][j] = k;                // 放置k
                    if (backtracking(board)) return true; // 如果找到合适一组立刻返回
                    board[i][j] = '.';              // 回溯，撤销k
                }
            }
            return false;                           // 9个数都试完了，都不行，那么就返回false
        }
    }
    return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}

注意这里return false的地方，这里放return false 是有讲究的。

因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！

那么会直接返回， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！

判断棋盘是否合法

判断棋盘是否合法有如下三个维度：

  • 同行是否重复
  • 同列是否重复
  • 9宫格里是否重复

代码如下：

1
2
3
4
5
6
7
8
9
10
11
bool isValid(vector<vector<char>> &board, int row, int col, char c) {
    // 检查行、列、九宫格是否有重复
    for (int i = 0; i < 9; i++) {
        // 检查行和列
        if (board[i][col] == c) return false;
        if (board[row][i] == c) return false;
        // 检查九宫格
        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
    }
    return true;
}

最后整体C++代码如下：

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
class Solution {
private:
bool backtracking(vector<vector<char>>& board) {
    for (int i = 0; i < board.size(); i++) {        // 遍历行
        for (int j = 0; j < board[0].size(); j++) { // 遍历列
            if (board[i][j] == '.') {
                for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适
                    if (isValid(board，i, j, k)) {
                        board[i][j] = k;                // 放置k
                        if (backtracking(board)) return true; // 如果找到合适一组立刻返回
                        board[i][j] = '.';              // 回溯，撤销k
                    }
                }
                return false;  // 9个数都试完了，都不行，那么就返回false
            }
        }
    }
    return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}
bool isValid(vector<vector<char>> &board, int row, int col, char c) {
    // 检查行、列、九宫格是否有重复
    for (int i = 0; i < 9; i++) {
        // 检查行和列
        if (board[i][col] == c) return false;
        if (board[row][i] == c) return false;
        // 检查九宫格
        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
    }
    return true;
  
}
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

总结

解数独可以说是非常难的题目了，如果还一直停留在单层递归的逻辑中，这道题目可以让大家瞬间崩溃。

所以我在开篇就提到了二维递归，这也是我自创词汇，希望可以帮助大家理解解数独的搜索过程。

一波分析之后，再看代码会发现其实也不难，唯一难点就是理解二维递归的思维逻辑。

评论
目录
排列与棋盘问题
  1. 46.全排列
    1. 回溯三部曲
    2. 总结
  2. 47.全排列 II
    1. 思路
    2. 拓展
    3. 总结
  3. 332.重新安排行程
    1. 思路一
    2. 思路二
    3. 解释邻接图
  4. 51. N皇后
    1. 思路
    2. 回溯三部曲
    3. 总结
  5. 37. 解数独
    1. 思路
    2. 回溯三部曲
    3. 判断棋盘是否合法