07-递归和回溯法
# 树形问题（电话号码的字母组合）
上一章中，我们介绍了二叉树相关问题，通常需要使用递归算法，这一章我们来看一下更多递归的应用，以及使用递归算法时一个非常经典的思想——回溯法，这个思想通常都应用在一类问题上，我们称作树形问题。这类问题本身没有定义在二叉树机构中，但是当我们具体分析后，会发现解决这个问题的思路本质是一棵树的形状。
这一节我们先从一个比较简单的问题入手。
# 问题分析
17. 电话号码的字母组合 (opens new window)中等
给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]1
2
如下图所示，我们以 digits = "23" 为例，先来看 2 可以代表 (a, b , c) 三个字母，所以我们就需要基于 (a, b , c) 这三种可能来考虑下一个数字 3 能代表哪些字母，3 能代表 (d, e, f) 三个字母，所以我们就得到了 3 * 3 = 9 种字母组合 ["ad","ae","af","bd","be","bf","cd","ce","cf"]。
经过分析，我们看到形成了一棵树，这类问题的思路是隐藏在一颗树种的，所以我们把这类问题称为树形问题。因为是树形结构，所以我们很容易想到使用递归的方式来解决，这个问题的递归结构在哪里呢？
我们从 2 开始看可以表示哪些字母，我们只需要求出 3 能代表哪些字母，然后在前面加上 2 所能代表的这些字母，一起就构成了结果。
/**
* 时间复杂度: O(3^m * 4^n)，m 为可以代表 3 个字母的数字个数，n 为可以代表 4 个字母的数字个数
* 空间复杂度: O(m + n)，m+n 为输入数字的总个数
*/
class Solution {
// 每个数字对应的字母，0 和 1 在本题中不用
private String[] letterMap = {
" ", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
// 存放结果
private List<String> res;
public List<String> letterCombinations(String digits) {
res = new ArrayList<>();
if (digits.equals(""))
return res;
findCombination(digits, 0, "");
return res;
}
/**
* 翻译 digits 字符串 index 索引下的字符，拼接到字符串 s 上，然后添加到结果 res 中
*
* @param digits 数字字符串
* @param index 将要翻译的索引
* @param str 到目前位置翻译的结果，当翻译到 digits 最后一位时将其添加到 res 中
*/
private void findCombination(String digits, int index, String str) {
if (index == digits.length()) {
res.add(str);
return;
}
String letters = letterMap[digits.charAt(index) - '0'];
for (int i = 0; i < letters.length(); i++)
findCombination(digits, index + 1, str + letters.charAt(i));
}
}
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
# 什么是回溯
# 回溯法介绍
下面我们结合图示来解释上一节题目对应程序的运行过程。
2 可以表示 (a, b, c) 三个字母，我们先尝试 2=a 的时候来到 3 节点，对于 3 可以表示 (d, e, f)，当 3 表示 d 我们就得到了 ad， 然后回到 3 节点，它还可以表示 e 我们就得到了 ae，再回到 3 节点还可以表示 f 我们就得到了 af，此时 3 的所以可能已经尝试完了，我们再回到 2 节点，2 还可以表示 b……
通过上面的过程我们得到递归调用一个非常重要的性质——要返回。即递归调用结束之后我们总是要返回到上一层继续调用，每一层的递归调用都是如此，我们要逐步返回，直到在根节点的那次递归调用的所有可能性都尝试完成，我们整个的递归函数才结束。也正是如此我们这种递归尝试寻找答案的规程也被称之为 回溯。
也就是说我们沿着一条路径寻找答案，一旦找到答案或者没找到答案就回去继续找，以此类推，这个过程就是回溯。用这个概念看的话我们在上一章学习的跟树相关的算法，本质也是回溯，因为我们使用了递归，递归的话就需要返回。只不过 回溯法 这个词通常被用于问题是查找一个解。
上一节算法的时间复杂度大致是 3^n = O(2^n)，是一个指数级的算法，所以其效率是非常低的。我们来结合这棵树看，第一层有 3 种情况，第二层有 9 种情况，一直下去，是以指数级上升的。
回溯法是暴力解法的一个主要实现手段。 我们遇到是很多问题要枚举其所有可能，如果不能使用简单的循环遍历的话，就需要使用这种回溯法。
大家可以思考下对于这个问题的特点是什么，特点是对于 n 是一个变量。如果它的长度是固定的，比如 8，那我们就可以使用 8 重循环来枚举所有的可能性。但是现在长度是动态的，我们就可以使用这种回溯法来枚举所有的可能性。我们后面会看到动态规划也是在回溯法的基础上构建的。
有些问题我们只能使用回溯法这种暴力解法来解决，但是在回溯的过程中我们可以通过 剪枝 不用到达所有的的叶子节点，从而提高算法效率，后面我们将接触到。
# 相关问题
93. 复原 IP 地址 (opens new window)中等
给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从
s获得的 有效 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 地址。
/**
* 回溯
* 时间复杂度: 复杂，不会算
* 空间复杂度: O(4)，表示需要 4 个网段，递归深度是 4
*/
class Solution {
private List<String> res; // 存放所有可能的 ip 地址
private List<String> segments; // 存放已经拼入的网段
public List<String> restoreIpAddresses(String s) {
res = new ArrayList<>();
segments = new ArrayList<>();
dfs(s, 0);
return res;
}
/**
* 从 s 的 start 位置开始找出一个网段加入 segments 中，
* 直到 segments 中够 4 个，并且 s 恰好用完就加入结果集 res 中
*
* @param s 原始字符串
* @param start 新网段开始位置
*/
private void dfs(String s, int start) {
// 只要 segments 满 4 个了就要结束递归
if (segments.size() == 4) {
// 如果 s 正好用完，表示成功解析 ip，加入结果集
if (start == s.length())
res.add(String.join(".", segments));
return;
}
int unallocated = s.length() - start; // 剩余未分配的字符个数
int need = 4 - segments.size(); // 还需要几个网段
// 不够分配或者分配不下了，结束递归（剪枝）
if (unallocated < need || unallocated > need * 3) return;
// 继续拼入网段，长度 length 可取 1 到 Math.min(3, unallocated)
for (int length = 1; length <= Math.min(3, unallocated); length++) {
String segment = s.substring(start, start + length); // 新网段
// 判断 segment 是否为有效网段：不能有先导零且数值不大于 255
if (!(length > 1 && segment.startsWith("0")) && Integer.parseInt(segment) <= 255) {
segments.add(segment); // 拼入网段
dfs(s, start + length); // 继续递归
segments.remove(segments.size() - 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
131. 分割回文串 (opens new window)中等
给你一个字符串
s，请你将s分割成一些子串，使每个子串都是 回文串 。返回s所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。
回溯 + 记忆化搜索
/** * 回溯 + 记忆化搜索 * 时间复杂度: O(n * 2^n) * 空间复杂度: O(n^2) */ class Solution { // memo[l][r] 表示 s[l...r] 是否回文串，0:未计算，1:是，-1:不是 private int[][] memo; // 存放结果 private List<List<String>> res; public List<List<String>> partition(String s) { res = new ArrayList<>(); memo = new int[s.length()][s.length()]; dfs(s, 0, new LinkedList<>()); return res; } /** * 尝试将从 s 的 start 位置开始拼入一个回文串，加入 list */ private void dfs(String s, int start, LinkedList<String> list) { // s 遍历完了，存入结果返回 if (start == s.length()) { res.add(new LinkedList<>(list)); return; } // 尝试继续加入一个回文串 for (int end = start; end < s.length(); end++) { if (isPalindrome(s, start, end) == 1) { // 如果是回文串 list.addLast(s.substring(start, end + 1)); // 拼入 dfs(s, end + 1, list); // 递归继续拼入 list.removeLast(); // 回溯，尝试下一个长度子串 } } } /** * 验证 s[l...r] 是不是回文串 */ private int isPalindrome(String s, int l, int r) { if (memo[l][r] != 0) return memo[l][r]; if (l >= r) { memo[l][r] = 1; } else { if (s.charAt(l) == s.charAt(r)) { memo[l][r] = isPalindrome(s, l + 1, r - 1); } else { memo[l][r] = -1; } } return memo[l][r]; } }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回溯 + 动态规划
// todo1
# 排列问题（全排列）
之前通过一个问题详细介绍了回溯算法，下面几个小节来看看回溯算法的应用，看看它能处理哪些问题。首先回溯算法能处理一类非常重要的问题—— 排列问题。
# 问题分析
给定一个不含重复数字的数组
nums，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
解题分析可参考：回溯算法入门级详解 + 练习 (opens new window)
排列问题的递归回溯结构如下图所示。
用表达式可以表示为：
Perms(nums) = {取出一个数字} + Perms(nums - 这个数字)
大家要注意这个问题和之前的 17. 电话号码的字母组合 (opens new window) 问题稍有不同，前一个问题每一个数字代表一个字母，数字和数字之间是不冲突的。对本题来说，每次取出一个数字，都影响下一递归调用的要处理的数据范围，为了解决这个问题，我们在编程的时候还需要借助一些辅助的数据结构。
/**
* 回溯
* 时间复杂度: O(n×n!)
* 空间复杂度: O(n)
*/
class Solution {
private List<List<Integer>> res;
private boolean[] used; // 记录 nums[i] 是否已经在排列中
public List<List<Integer>> permute(int[] nums) {
res = new LinkedList<>();
used = new boolean[nums.length];
dfs(nums, new LinkedList<>());
return res;
}
// 将 nums 的排列逐个加入 list 中
private void dfs(int[] nums, LinkedList<Integer> list) {
// 排列满了，存入结果集
if (list.size() == nums.length) {
res.add(new LinkedList<>(list));
return;
}
// 选出一个元素，加入排列中
for (int i = 0; i < nums.length; i++) {
if (!used[i]) {
list.add(nums[i]); // 加入排列
used[i] = true;
dfs(nums, list); // 将下一个元素放到排列中
list.removeLast(); // 回溯
used[i] = false;
}
}
}
}
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
# 相关问题
47. 全排列 II (opens new window)中等
给定一个可包含重复数字的序列
nums，按任意顺序 返回所有不重复的全排列。
核心思想就是，保证在排列 idx 位置上填入数字的时候，重复数字只会被尝试填入 1 次。
解法一：记录 idx 位置尝试过的数字
/** * 回溯 * 时间复杂度: O(n×n!) * 空间复杂度: O(n) */ class Solution1 { private List<List<Integer>> res; private boolean[] used; // 记录 nums[i] 是否已经在排列中 public List<List<Integer>> permuteUnique(int[] nums) { res = new ArrayList<>(); used = new boolean[nums.length]; dfs(nums, new LinkedList<>()); return res; } // 将有序数组 nums 的排列逐个加入 list 中 private void dfs(int[] nums, LinkedList<Integer> list) { if (list.size() == nums.length) { res.add(new LinkedList<>(list)); return; } HashSet<Integer> tried = new HashSet<>(); // 本位置尝试过的数字 for (int i = 0; i < nums.length; i++) { // (1) nums[i] 已经在排列中，跳过 // (2) 和 nums[i] 的数字已经在本位置尝试填入过了，跳过，保证了重复数字只会被填入一次 if (used[i] || tried.contains(nums[i])) continue; // 记录选择的数字 tried.add(nums[i]); // 填入排列中，并继续递归回溯 list.add(nums[i]); used[i] = true; dfs(nums, list); list.removeLast(); used[i] = false; } } }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解法二：排序 nums，每次只记录前一次在 idx 位置尝试的数字
/** * 回溯 * 时间复杂度: O(n×n!) * 空间复杂度: O(n) */ class Solution2 { private List<List<Integer>> res; private boolean[] used; // 记录 nums[i] 是否已经在排列中 public List<List<Integer>> permuteUnique(int[] nums) { res = new ArrayList<>(); used = new boolean[nums.length]; Arrays.sort(nums); // 必须先排序 dfs(nums, new LinkedList<>()); return res; } // 将有序数组 nums 的排列逐个加入 list 中 private void dfs(int[] nums, LinkedList<Integer> list) { if (list.size() == nums.length) { res.add(new LinkedList<>(list)); return; } // 选出一个元素，填入排列的 list，位置是 list.size() Integer lastChoice = null; // 记录最后选出尝试填入 list.size() 位置的元素，注意不是排列的上一个位置 list.size() - 1 for (int i = 0; i < nums.length; i++) { // (1) nums[i] 已经在排列中 // (2) 本位置没有尝试过和 nums[i] 相同的元素，利用 nums 有序的特点，重复元素是连续的，只有第一个会被选出尝试， // 后续的因为 lastChoice 的限制会跳过 if (used[i] || (lastChoice != null && nums[i] == lastChoice)) continue; // 记录选择的元素 lastChoice = nums[i]; // 填入排列中，并继续递归回溯 list.add(nums[i]); used[i] = true; dfs(nums, list); list.removeLast(); used[i] = false; } } }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
# 组合问题（组合）
这一节我们来看回溯算法解决的另一类问题——组合问题。
# 问题分析
给定两个整数
n和k，返回范围[1, n]中所有可能的k个数的组合。你可以按 任何顺序 返回答案。
解题分析可参考：回溯算法 + 剪枝（Java） (opens new window)
组合问题的递归回溯结构如下图所示。
上图即为从 4 个数中取两个数能得到的所有组合，这棵树看起来跟之前的树不一样，之前的树每个节点有集合孩子是固定的，这棵树不固定。但是它依然是这样一个树形的结构，我们依然可以使用递归解决，过程中我们依然能够看到回溯的过程。
上面的递归图跟我们小学做组合题目画的画有相似之处，可以结合起来理解。
我们在每次回溯后再次进行递归操作时，只需要考虑这个元素之后的元素即可，因为前面的元素已经考虑过了。
根据上述递归树实现回溯（多叉树回溯）
/** * 回溯 + 剪枝 */ class Solution { private List<List<Integer>> res; // 存放结果 public List<List<Integer>> combine(int n, int k) { res = new ArrayList<>(); dfs(n, k, 1, new LinkedList<>()); return res; } /** * 求解 C(n,k)，当前已经找到的组合存储在 path 中，需要从 start 开始搜索新的元素 * * @param n 区间大小 [1...n]（固定） * @param k 求 k 个元素的组合（固定） * @param start 从 start 开始往后找（递增） * @param path 存放组合元素（元素个数递增） */ private void dfs(int n, int k, int start, LinkedList<Integer> path) { // 如果已经找到了 k 个元素，保存返回 if (path.size() == k) { res.add(new LinkedList<>(path)); // 必须存副本 return; } // 还需要加入 k-path.size 个元素，还剩 n-i+1 个数字，需满足剩余数字个数大于还需个数， // 即 n - i + 1 >= k - path.size for (int i = start; n - i + 1 >= k - list.size(); i++) { path.addLast(i); // 向组合中加入一个元素 dfs(n, k, i + 1, path); // 继续递归 path.removeLast(); // 回溯，遍历下一个 } } }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对于每个数字，选择放入和不放入（二叉树回溯）
class Solution { private List<List<Integer>> res; public List<List<Integer>> combine(int n, int k) { res = new ArrayList<>(); dfs(n, k, new LinkedList<>()); return res; } /** * 从 [1, n] 中选出 k 个数字，放入 list 中，直到放满。 * 依次考察 n, n-1, n-2, ... , 1, 对于 n 考虑放入和不放入的情况。 */ private void dfs(int n, int k, LinkedList<Integer> list) { // 还需要放入 0 个元素，表示已经够了，加入结果集后返回 if (k == 0) { res.add(new LinkedList<>(list)); return; } // 如果 [1, n] 不够 k 个元素，直接返回 if (n < k) return; // (1) n 不放入组合，去 [1, n-1] 中选 k 个数字放入组合 dfs(n - 1, k, list); // (2) n 放入组合，去 [1, n-1] 中选 k-1 个数字放入组合 list.add(n); dfs(n - 1, k - 1, list); list.removeLast(); } }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
# 相关问题
给定一个无重复元素的正整数数组
candidates和一个正整数target，找出candidates中所有可以使数字和为目标数target的唯一组合。
candidates中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。对于给定的输入，保证和为
target的唯一组合数少于150个。
二叉树回溯，思路：组合总和 (opens new window)
思考的是对与每个元素加入或不加入
/** * 回溯法，二叉树 * 分叉为是否选取元素 candidates[i]，有两种选择 */ class Solution { private List<List<Integer>> res; // 存放结果 public List<List<Integer>> combinationSum(int[] candidates, int target) { res = new ArrayList<>(); dfs(candidates, target, 0, new LinkedList<>()); return res; } /** * 考虑将 candidates[index] 加入组合 list 中，使得组合的总和为 target */ private void dfs(int[] candidates, int target, int index, LinkedList<Integer> list) { if (index >= candidates.length) return; if (target == 0) { res.add(new LinkedList<>(list)); return; } // 情况一：不包含 index 元素 dfs(candidates, target, index + 1, list); // 情况二：包含 index 元素，加入到 list，需要回溯 if (candidates[index] <= target) { list.addLast(candidates[index]); dfs(candidates, target - candidates[index], index, list); list.removeLast(); } } }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多叉树回溯，思路：回溯算法 + 剪枝（回溯经典例题详解） (opens new window)
思考的是下一个加入组合的元素是谁
/** * 回溯法，多叉树 * 分叉为 candidates 的元素个数，每次选 i 及其之后的元素 */ class Solution2 { private List<List<Integer>> res; // 存放结果 public List<List<Integer>> combinationSum(int[] candidates, int target) { res = new ArrayList<>(); dfs(candidates, target, 0, new LinkedList<>()); return res; } /** * 考虑将 candidates 数组 start 及以后的元素加入组合 list 中，使得组合的总和为 target */ private void dfs(int[] candidates, int target, int start, LinkedList<Integer> list) { if (target == 0) { res.add(new LinkedList<>(list)); return; } for (int i = start; i < candidates.length; i++) { if (candidates[i] <= target) { list.addLast(candidates[i]); // 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错 dfs(candidates, target - candidates[i], i, list); list.removeLast(); // 重置状态 } } } }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
40. 组合总和 II (opens new window)中等
给定一个数组
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次。**注意：**解集不能包含重复的组合。
216. 组合总和 III (opens new window)中等
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
给你一个整数数组
nums，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
90. 子集 II (opens new window)中等
给你一个整数数组
nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
401. 二进制手表 (opens new window)简单
二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。
- 例如，下面的二进制手表读取
"3:25"。
给你一个整数
turnedOn，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。小时不会以零开头：
- 例如，
"01:00"是无效的时间，正确的写法应该是"1:00"。分钟必须由两位数组成，可能会以零开头：
- 例如，
"10:2"是无效的时间，正确的写法应该是"10:02"。
# 二维平面上的回溯法（单词搜索）
# 问题分析
给定一个
m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
class Solution {
// used[i][j] == true 表示 board[i][j] 已经被使用
private boolean[][] used;
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
used = new boolean[m][n];
// 选取起点
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 从任一起点出发能找到符合的路径，就成功
if (check(board, i, j, word, 0))
return true;
}
}
return false; // 所有路径都查找失败
}
/**
* 从 board[i][j] 开始，匹配单词 word 从 k 到末尾的部分
*/
private boolean check(char[][] board, int i, int j, String word, int k) {
// 角标越界，不成功
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length)
return false;
// 字符已被使用，或字符不匹配，不成功
if (used[i][j] || board[i][j] != word.charAt(k))
return false;
// 匹配且已经查找到单词末尾了，成功
if (k == word.length() - 1)
return true;
used[i][j] = true; // 标记已使用
// 递归到上下左右匹配单词剩余部分，任一匹配成功则成功
if (check(board, i + 1, j, word, k + 1)) return true;
if (check(board, i - 1, j, word, k + 1)) return true;
if (check(board, i, j + 1, word, k + 1)) return true;
if (check(board, i, j - 1, word, k + 1)) return true;
used[i][j] = false; // 回溯，清除使用标志
return false; // 四个方向都没匹配成功，失败
}
}
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
# 相关问题
130. 被围绕的区域 (opens new window)中等
给你一个
m x n的矩阵board，由若干字符'X'和'O'，找到所有被'X'围绕的区域，并将这些区域里所有的'O'用'X'填充。
417. 太平洋大西洋水流问题 (opens new window)中等
给定一个
m x n的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
# floodfill 算法，一类经典问题（岛屿数量）
# 问题分析
200. 岛屿数量 (opens new window)中等
给你一个由
'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
# 回溯法是经典人工智能的基础（N 皇后）
# 问题分析
n 皇后问题 研究的是如何将
n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数
n，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中
'Q'和'.'分别代表了皇后和空位。
# 相关问题
52. N皇后 II (opens new window)困难
n 皇后问题 研究的是如何将
n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数
n，返回 n 皇后问题 不同的解决方案的数量。
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。- 数字
1-9在每一列只能出现一次。- 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）数独部分空格内已填入了数字，空白格用
'.'表示。