题解报告：LeetCode#22 括号生成
描述：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3输出：["((()))","(()())","(())()","()(())","()()()"]
解题思路：
这里我们主要讲解回溯思想，深度优先遍历，以n=2为例，画树形结构图。方法是“做减法”。
画图以后，可以分析出的结论：
- 当前左右括号都有大于 00 个可以使用的时候，才产生分支；
- 产生左分支的时候，只看当前是否还有左括号可以使用；
- 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；
- 在左边和右边剩余的括号数都等于 00 的时候结算。
参考代码：
public class Solution {
// 做减法
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
// 特判
if (n == 0) return res;
// 执行深度优先遍历，搜索可能的结果
dfs("", n, n, res);
return res;
}
/**
* @param curStr 当前递归得到的结果
* @param left 左括号还有几个可以使用
* @param right 右括号还有几个可以使用
* @param res 结果集
*/
private void dfs(String curStr, int left, int right, List<String> res) {
// 因为每一次尝试，都使用新的字符串变量，所以无需回溯
// 在递归终止的时候，直接把它添加到结果集即可，注意与「力扣」第 46 题、第 39 题区分
if (left == 0 && right == 0) {
res.add(curStr);
return;
}
// 剪枝（如图，左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节）
if (left > right) return;
if (left > 0) dfs(curStr + "(", left - 1, right, res);
if (right > 0) dfs(curStr + ")", left, right - 1, res);
}
}
我们运行 n = 2 的情况，得到结果 [(()), ()()] ，说明分析的结果是正确的。
如果我们不用减法，使用加法，即 left 表示“左括号还有几个没有用掉”，right 表示“右括号还有几个没有用掉”，可以画出另一棵递归树。
参考代码：
public class Solution {
// 做加法
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
// 特判
if (n == 0) {
return res;
}
dfs("", 0, 0, n, res);
return res;
}
/**
* @param curStr 当前递归得到的结果
* @param left 左括号已经用了几个
* @param right 右括号已经用了几个
* @param n 左括号、右括号一共得用几个
* @param res 结果集
*/
private void dfs(String curStr, int left, int right, int n, List<String> res) {
if (left == n && right == n) {
res.add(curStr);
return;
}
// 剪枝
if (left < right) return;
if (left < n) dfs(curStr + "(", left + 1, right, n, res);
if (right < n) dfs(curStr + ")", left, right + 1, n, res);
}
}
题解报告：LeetCode#46 全排列
描述：
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解题思路：
我们尝试在纸上写3个数字、4个数字、5个数字的全排序，相信不难找到这样的方法。以数组[1, 2, 3]的全排列为例。
- 先写以 11 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列（注意：递归结构体现在这里）；
- 再写以 22 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；
- 最后写以 33 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。
总结搜索的方法：按顺序枚举每一位可能出现的情况，已经选择的数字在 当前 要选择的数字中不能出现。按照这种策略搜索就能够做到不重不漏。这样的思路，可以用一个树形结构表示。
说明：
- 每一个结点表示了求解全排列问题的不同的阶段，这些阶段通过变量的“不同的值”体现，这些变量的不同的值，称之为状态；
- 使用深度优先遍历有【回头】的过程，在【回头】以后，状态变量需要设置成为和先前一样，因此在回到上一层结点的过程中，需要撤销上一次的选择，这个操作称之为【状态重置】；
- 深度优先遍历，借助系统栈空间，保存所需要的状态变量，在编码中只需要注意遍历到相应的结点的时候，状态变量的值是正确的，具体的做法是：往下走一层的时候，
path变量在尾部追加，而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此path变量是一个栈； - 深度优先遍历通过【回溯】操作，实现了全局使用一份状态变量的效果。
使用编程的方法得到全排列，就是在这样的一个树形结构中完成遍历，从树的根节点到叶子结点形成的路径就是其中一个全排列。
代码示例：
注意：下面的代码是错误的，可以运行测试用例，发现原因，然后再阅读后面的内容
public class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
// 使用一个动态数组保存所有可能的全排列
List<List<Integer>> res = new ArrayList<>();
if (len == 0) return res;
boolean[] used = new boolean[len];
List<Integer> path = new ArrayList<>();
dfs(nums, len, 0, path, used, res);
return res;
}
private void dfs(int[] nums, int len, int depth,
List<Integer> path, boolean[] used,
List<List<Integer>> res) {
if (depth == len) {
res.add(path);
return;
}
// 在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
for (int i = 0; i < len; i++) {
if (!used[i]) {
path.add(nums[i]);
used[i] = true;
dfs(nums, len, depth + 1, path, used, res);
// 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
used[i] = false;
path.remove(path.size() - 1);
}
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
Solution solution = new Solution();
List<List<Integer>> lists = solution.permute(nums);
System.out.println(lists);
}
}
执行main方法以后输出如下：
[[], [], [], [], [], []]
原因出现在终止递归条件这里：
if (depth == len) {
res.add(path);
return;
}
变量path所指向的列表 在深度优先遍历的过程中只有一份，深度优先遍历完成以后，回到了根节点，成为空列表。
在 Java 中，参数传递是 值传递，对象类型变量在传参的过程中，复制的是变量的地址。这些地址被添加到 res 变量，但实际上指向的是同一块内存地址，因此我们会看到 66 个空的列表对象。解决的方法很简单，在 res.add(path); 这里做一次拷贝即可。
修改的部分：
if (depth == len) {
res.add(new ArrayList<>(path));
return;
}
题解报告：LeetCode#47 全排列Ⅱ
描述：
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例：
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
解题思路：
这一题是在 LeetCode#46 的基础上增加了“序列中的元素可重复”这一条件，但要求返回的结果又不能有重复元素。
思路：在一定会产生重复结果集的地方剪枝。
一个比较容易想到的办法是在结果集中去重。但是问题又来了，这些结果集的元素是一个又一个列表，对列表去重不像用哈希表对基本元素去重那么容易。
如果要比较两个列表是否一样，一个很显然的办法是分别排序，然后逐个比对。既然要排序，我们可以在搜索之前就对候选数组排序，一旦发现这一支搜索下去可能搜索到重复的元素就停止搜索，这样结果集中不会包含重复元素。
产生重复结点的地方，正是图中标注了“剪刀”，且被绿色框框住的地方。
大家也可以把第 2 个 1 加上 ‘ ，即 [1, 1’, 2] 去想象这个搜索的过程。只要遇到起点一样，就有可能产生重复。这里还有一个很细节的地方：
1、在图中 ② 处，搜索的数也和上一次一样，但是上一次的 1 还在使用中；
2、在图中 ① 处，搜索的数也和上一次一样，但是上一次的 1 刚刚被撤销，正是因为刚被撤销，下面的搜索中还会使用到，因此会产生重复，剪掉的就应该是这样的分支。
代码示例：
代码实现方面，在第 46 题的基础上，要加上这样一段代码：
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue;
}
这段代码就能检测到标注为 ① 的两个结点，跳过它们。注意：这里 used[i - 1] 不加 !，测评也能通过。有兴趣的朋友可以想一想这是为什么。建议大家做这样几个对比实验：
1、干脆就不写 !used[i - 1] 结果是什么样？
2、写 used[i - 1] 结果是什么，代码又是怎样执行的。这里给的结论是：!used[i - 1] 这样的剪枝更彻底。附录会分析原因。
接下来看下参考代码：
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) return res;
// 排序（升序或者降序都可以），排序是剪枝的前提
Arrays.sort(nums);
boolean[] used = new boolean[len];
// 使用 Deque 是 Java 官方 Stack 类的建议
Deque<Integer> path = new ArrayDeque<>(len);
dfs(nums, len, 0, used, path, res);
return res;
}
private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
if (depth == len) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < len; ++i) {
if (used[i]) continue;
// 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
// 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
path.addLast(nums[i]);
used[i] = true;
dfs(nums, len, depth + 1, used, path, res);
// 回溯部分的代码，和 dfs 之前的代码是对称的
used[i] = false;
path.removeLast();
}
}
}
题解报告：LeetCode#60 第K个排序
描述：
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"
给定 n 和 k，返回第 k 个排列。
说明：
- 给定 n 的范围是 [1, 9]。
- 给定 k 的范围是[1, n!]。
示例 :
示例1：
输入: n = 3, k = 3
输出: "213"
示例 2:
输入: n = 4, k = 9
输出: "2314"
思路：
这里很容易想到，全排列的回溯搜索算法，依次得到全排列，输出第 k 个全排列即可。但是在实际解题中，我们并不需要求出所有的全排列。
基于以下几点考虑：
- 所求排列一定在叶子结点处得到，进入每一个分支，可以根据已经选定的数的个数，进而计算还未选定的数的个数，然后计算阶乘，就知道这一分支的叶子结点的个数：
- 如果 k 大于这一分支将要产生的叶子结点数，直接跳过这个分支，这个操作叫【剪枝】；
- 如果 k 小于等于这一个分支将要产生的叶子结点数，那说明所求的全排列一定在这一个分支将要产生的叶子结点里，需要递归求解。
代码实现：
在编写代码之前，还有几点需要注意：
- 计算阶乘的时候，可以使用循环计算。注意：0! = 1，它表示了没有数可选的时候，即表示到达叶子结点了，排列数只剩下 1 个。
- 题目中说【给定 n 的范围是[1, 9]】，那么可以把从 0 到 9 的阶乘计算好，放在一个数组里，可以根据索引直接获得阶乘值；
- 编码的时候，+1 还是 -1，大于还是大于等于，这些不能靠猜。常见的做法是：代入一个具体的数值，认真调试。
public class Solution {
// 记录数字是否被使用过
private boolean[] used;
// 阶乘数组
private int[] factorial;
private int n;
private int k;
public String getPermutation(int n, int k) {
this.n = n;
this.k = k;
calculateFactorical(n);
// 查找全排列需要的布尔数组
used = new boolean[n + 1];
StringBuilder path = new StringBuilder();
dfs(0, path);
return path.toString();
}
private void dfs(int index, StringBuilder path) {
if (index == n) return;
// 计算还未确定的数字的全排列的个数，第 1 次进入的时候是n
int cnt = factorial[n - 1 - index];
for (int i = 1; i <= n; i++) {
if (used[i]) continue;
if (cnt < k) {
k -= cnt;
continue;
}
path.append(i);
used[i] = true;
dfs(index + 1, path);
// 注意1：这里没有回溯（状态重置）的必要
// 注意2：这里要加 return，后面的数没有必要遍历去尝试了
return;
}
}
// 计算阶乘的得出数组
private void calculateFactorical(int n) {
factorial = new int[n + 1];
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
factorial[i] = factorial[i-1] * i;
}
}
}
题解报告：LeetCode#93 复原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 地址。
示例：
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "1111"
输出：["1.1.1.1"]
示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
解题思路：
回溯算法事实上就是在一个树形问题上做深度优先遍历，因此首先需要把问题转换为树形问题。我们可以模拟一下如何通过指定的字符串s生成IP地址的过程，把树形图画出来。
在画树形图的过程中，你一定会发现有些枝叶是没有必要的，把没有必要的枝叶剪去的操作就是剪枝，在代码中一般通过break或者continue和return（表示递归终止）实现。
分析剪枝条件（下面只写出一些我想到的要点，有些点能想到，但是编码很复杂，我就没有写了）：
- 一开始，字符串长度小于 4 或者大于 12，一定不能拼凑出合法的 IP 地址（这一点可以一般化到中间节点的判断中，以产生剪枝行为）；
- 每一个结点可以选取截取的方法只有3种：截 1 位、截 2 位、截 3 位，因此每一个结点可以生长出的分支最多只有 3 条分支；
根据截取出来的字符串判断是否是合理的 ip 段，这里写法比较多，可以先截取，再转换成 int ，再判断。我采用的做法是先转成 int，是合法的 ip 段数值以后，再截取。 - 由于 ip 段最多就 4 个段，因此这棵三叉树最多 4 层，这个条件作为递归终止条件之一；
- 每一个结点表示了求解这个问题的不同阶段，需要的状态变量有：
splitTimes：已经分割出多少个 IP 段；begin：截取 IP 段的起始位置；path：记录从根节点到叶子结点的一个路径（回溯算法常规变量，是一个栈）；res：记录结果集的变量，常规变量。总结：这个问题思想不难，但是细节比较繁琐，什么时候递归终止，如何手动截取字符串，再转换成 int 类型，还有如何在中间结点发现可以剪枝，这些细节需要在编码的时候考虑清楚。
代码实现：
这一版代码比较慢，原因有可能是剪枝判断太多了，也有可能是 ipSegment + "" 这个操作耗时。
public class Solution {
public List<String> restoreIpAddress(String s) {
int len = s.length();
List<String> res = new ArrayList<>();
//如果长度不够/过长，不搜索
if(len < 4 || len > 12) {
return res;
}
Deque<String> path = new ArrayDeque<>(4);
int splitTimes = 0;
dfs(s, len, splitTimes, 0, path, res);
return res;
}
/**
* 判断 s 的子区间 [left, right] 是否能够成为一个 ip 段
* 判断的同时顺便把类型转了
*/
private int judgeIfIpSegment(String s, int left, int right) {
int len = right - left + 1;
//大于 1 位的时候，不能以 0 开头
if (len > 1 && s.charAt(left) == '0') {
return -1;
}
//转成 int 类型
int res = 0;
for (int i = left; i <= right; i++) {
res = res * 10 + s.charAt(i) - '0';
}
if (res > 255) {
return -1;
}
return res;
}
private void dfs(String s, int len, int split, int begin, Deque<String> path, List<String> res) {
if (begin == len) {
if (split == 4) {
res.add(String.join(".", path));
}
return;
}
// 看到剩下的不够了，就退出（剪枝），len - begin 表示剩余的还未分割的字符串的位数
if (len - begin < (4 - split) || len - begin > 3 * (4 - split)) {
return;
}
for (int i = 0; i < 3; i++) {
if (begin + i >= len) {
break;
}
int ipSegment = judgeIfIpSegment(s, begin, begin + i);
if (ipSegment != -1) {
// 在判断是 ip 段的情况下，才去做截取
path.addLast(ipSegment + "");
dfs(s, len, split + 1, begin + i + 1, path, res);
path.removeLast();
}
}
}
}
与参考代码 1 不同之处只在于剪枝少判断，而且也是先判断截取的 ip 段是否合法，然后用截取函数截取字符串，执行结果上会快一些。
public class Solution {
public List<String> restoreIpAddresses(String s) {
int len = s.length();
List<String> res = new ArrayList<>();
if (len > 12 || len < 4) {
return res;
}
Deque<String> path = new ArrayDeque<>(4);
dfs(s, len, 0, 4, path, res);
return res;
}
// 需要一个变量记录剩余多少段还没被分割
private void dfs(String s, int len, int begin, int residue, Deque<String> path, List<String> res) {
if (begin == len) {
if (residue == 0) {
res.add(String.join(".", path));
}
return;
}
for (int i = begin; i < begin + 3; i++) {
if (i >= len) {
break;
}
if (residue * 3 < len - i) {
continue;
}
if (judgeIpSegment(s, begin, i)) {
String currentIpSegment = s.substring(begin, i + 1);
path.addLast(currentIpSegment);
dfs(s, len, i + 1, residue - 1, path, res);
path.removeLast();
}
}
}
private boolean judgeIpSegment(String s, int left, int right) {
int len = right - left + 1;
if (len > 1 && s.charAt(left) == '0') {
return false;
}
int res = 0;
while (left <= right) {
res = res * 10 + s.charAt(left) - '0';
left++;
}
return res >= 0 && res <= 255;
}
}
复杂度分析：
- 时间复杂度：因为这个问题限制在有效 IP 段内，因此需要截取和检查的次数有上限，分析清楚这个复杂度在我的能力范围之外（欢迎大家指导）。很多回溯问题的复杂度分析都比较 “复杂”，所以我选择暂时搁浅。
- 空间复杂度：O(h)，也是由于这个问题限制在有效 IP 段内，树最多 4 层，保存的结果集也是有限个，基于一般性，需要记录递归过程的信息，这个空间大小是递归树的高度 hh。
若有收获，就点个赞吧
0 人点赞
