93.复原IP地址
思路
cr：代码随想录
- 本题需要额外处理，需要判断这个字串是否合法
伪代码
//全局变量 result
private List<String> result = new ArrayList<>(); // 记录结果
// startIndex: 搜索的起始位置，pointNum:添加逗点的数量
private void backtracking(StringBuilder s, int startIndex, int pointNum) {
if (pointNum == 3) { // 逗点数量为3时，分隔结束
// 判断第四段子字符串是否合法，如果合法就放进result中
if (isValid(s.toString(), startIndex, s.length() - 1)) {
result.add(s.toString());
}
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isValid(s.toString(), startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
s.insert(i + 1, '.'); // 在i的后面插入一个逗点
pointNum++;
backtracking(s, i + 2, pointNum); // 插入逗点之后下一个子串的起始位置为i+2
pointNum--; // 回溯
s.deleteCharAt(i + 1); // 回溯删掉逗点
} else {
break; // 不合法，直接结束本层循环
}
}
}
// 判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法
private boolean isValid(String s, int start, int end) {
if (start > end) { //检查子串是否为空。
return false;
}
if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
return false;
}
int num = 0;
for (int i = start; i <= end; i++) {
if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到非数字字符不合法
return false;
}
// 将字符串形式的数字转换为整数形式
num = num * 10 + (s.charAt(i) - '0');
if (num > 255) { // 如果大于255了不合法
return false;
}
}
return true;
}
public List<String> restoreIpAddresses(String s) {
result.clear();
if (s.length() < 4 || s.length() > 12) return result; // 剪枝
backtracking(new StringBuilder(s), 0, 0);
return result;
}
class Solution {
private List<String> result = new ArrayList<>();
private void backtracking(StringBuilder s, int startIndex, int dotNum){
if(dotNum == 3) {
if(isValid(s.toString(), startIndex, s.length()-1)){
result.add(s.toString());
}
return;
}
for(int i = startIndex; i < s.length(); i++){
if(isValid(s.toString(), startIndex, i)){
s.insert(i+1, '.');
dotNum++;
backtracking(s, i+2, dotNum);
dotNum--;
s.deleteCharAt(i+1);
}else{
break;
}
}
}
private boolean isValid(String s, int start, int end) {
if(start > end) return false;
//if(s.charAt(start) == '0' && s.charAt(start) != s.charAt(end)) return false; //这里不能这样写
if(s.charAt(start) == '0' && start != end) return false;
int num = 0;
for(int i = start; i <= end; i++){ //注意这里是start和end
if(s.charAt(i) > '9' || s.charAt(i) < '0') return false; //注意这里比较的是char
num = num * 10 + (s.charAt(i) - '0');
if(num > 255) return false;
}
return true;
}
public List<String> restoreIpAddresses(String s) {
result.clear();
if(s.length() > 12 || s.length() < 4) return result;
backtracking(new StringBuilder(s), 0, 0);
return result;
}
}
78.子集
题目链接/文章讲解
子集问题，就是收集树形结构中，每一个节点的结果。 整体代码其实和 回溯模板都是差不多的。
思路
cr：代码随想录
- 每一个子集都是一个组合
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int[] nums, int startIndex) {
result.add(new ArrayList<>(path)); // 收集子集，要放在终止添加的上面，否则会漏掉自己
// 终止条件可以不加，因为startIndex >= nums.length，本层for循环本来也结束了
if (startIndex >= nums.length) {
return;
}
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backtracking(nums, i + 1); // 注意从i+1开始，元素不重复取。比如取了(1,2)就没有必要取（2,1）
path.remove(path.size() - 1); // 回溯
}
}
public List<List<Integer>> subsets(int[] nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3};
List<List<Integer>> subsets = solution.subsets(nums);
System.out.println(subsets); // 输出子集组合
}
}
class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> result = new ArrayList<>();
private void backtracking(int[] nums, int startIndex){ //这里一开始居然忘写返回值了。。。。
result.add(new ArrayList<>(path));
if(startIndex > nums.length) return;
for(int i = startIndex; i < nums.length; i++){
path.add(nums[i]);
backtracking(nums, i+1);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> subsets(int[] nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
}
90.子集II
题目链接/文章讲解
大家之前做了 40.组合总和II 和 78.子集 ，本题就是这两道题目的结合，建议自己独立做一做，本题涉及的知识，之前都讲过，没有新内容。
思路
-
本题中可以有重复元素，所以有去重操作
image.png
使用 used 数组来去重的版本
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int[] nums, int startIndex, boolean[] used) {
result.add(new ArrayList<>(path));
for (int i = startIndex; i < nums.length; i++) {
// used[i - 1] == true，说明同一树枝 nums[i - 1] 使用过
// used[i - 1] == false，说明同一树层 nums[i - 1] 使用过
// 而我们要对同一树层使用过的元素进行跳过
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
path.add(nums[i]);
used[i] = true;
backtracking(nums, i + 1, used);
used[i] = false;
path.remove(path.size() - 1);
}
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
result.clear();
path.clear();
boolean[] used = new boolean[nums.length];
Arrays.sort(nums); // 去重需要排序
backtracking(nums, 0, used);
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 2};
List<List<Integer>> subsets = solution.subsetsWithDup(nums);
System.out.println(subsets); // 输出子集组合
}
}
不使用 used 数组来去重的版本
i 是当前考虑的元素的索引，startIndex 是当前递归层的起始索引。检查 nums[i] == nums[i - 1] 可以检测当前元素是否与前一个元素相同。结合 i > startIndex，可以确保这种比较只在同一层级内进行。
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int[] nums, int startIndex) {
result.add(new ArrayList<>(path));
for (int i = startIndex; i < nums.length; i++) {
// 而我们要对同一树层使用过的元素进行跳过
if (i > startIndex && nums[i] == nums[i - 1]) { // 注意这里使用 i > startIndex
continue;
}
path.add(nums[i]);
backtracking(nums, i + 1);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
result.clear();
path.clear();
Arrays.sort(nums); // 去重需要排序
backtracking(nums, 0);
return result;
}
}
