第七章 回溯算法part03
93.复原IP地址
本期本来是很有难度的，不过 大家做完 分割回文串 之后，本题就容易很多了
题目链接/文章讲解：https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html
视频讲解：https://www.bilibili.com/video/BV1XP4y1U73i/
错误答案：
class Solution {
List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
backtracking(s, 0);
return res;
}
StringBuilder sb = new StringBuilder();
public void backtracking (String s, int index){
if(index == s.length()){
res.add(sb.toString());
return;
}
for(int i = index; i < s.length(); i ++){
String temp = s.substring(index, i + 1);
if(ishf(temp)){
sb.append(temp);
sb.append('.');
backtracking(s, i + 1);
sb.deleteCharAt(sb.length() - 1);
sb.deleteCharAt(sb.length() - 1);
}else{
continue;
}
}
}
public boolean ishf(String s){
long num = Long.parseLong(s);
if(s.charAt(0) == '0') return false;
if(num < 0 || num > 255) return false;
return true;
}
}
错误结果：
s =
"101023"
输出
["10.10.2.3.","10.10.23.","10.10102.3."]
预期结果
["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
1 识别不了单独0 if(s.charAt(0) == '0' && num != 0) return false;
2 结尾的点 if(ishf(temp) && i != s.length() - 1){
sb.append(temp);
sb.append('.');
backtracking(s, i + 1);
sb.deleteCharAt(sb.length() - 1);
sb.deleteCharAt(sb.length() - 1);
}else if(ishf(temp)){
sb.append(temp);
backtracking(s, i + 1);
sb.deleteCharAt(sb.length() - 1);
}else{
continue;
}
加上 点 判断：
class Solution {
List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
backtracking(s, 0, 0);
return res;
}
StringBuilder sb = new StringBuilder();
public void backtracking (String s, int index, int count){
if(count == 3){
String temp = s.substring(index, s.length());
if(isValid(temp)){
sb.append(temp);
res.add(sb.toString());}
return;
}
for(int i = index; i < s.length(); i ++){
String temp = s.substring(index, i + 1);
if(isValid(temp) && i != s.length() - 1){
sb.append(temp);
sb.append('.');
backtracking(s, i + 1, count + 1);
sb.deleteCharAt(sb.length() - 1);
sb.deleteCharAt(sb.length() - 1);
}else{
continue;
}
}
}
public boolean isValid(String s){
if (s == null || s.length() == 0 || s.length() > 3) {
return false;
}
long num = Long.parseLong(s);
if(s.charAt(0) == '0' && s.length() != 1) return false;
if(num < 0 || num > 255) return false;
return true;
}
}
["1.0.10.23","1.0.10.102.3","1.0.1010.1.0.23","1.0.1010.1.10.2.3","1.0.1010.1.10101.0.2.3"]
预期结果
["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
问题 点还是多了 还是有数大于 255
正确：
class Solution {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
public List<String> restoreIpAddresses(String s) {
backtracking(s, 0, 0);
return res;
}
public void backtracking(String s, int index, int count) {
if (count == 3) {
String temp = s.substring(index);
if (isValid(temp)) {
sb.append(temp);
res.add(sb.toString());
sb.setLength(sb.length() - temp.length()); // 恢复之前的状态
}
return;
}
for (int i = index; i < s.length(); i++) {
String temp = s.substring(index, i + 1);
if (isValid(temp)) {
sb.append(temp).append('.');
backtracking(s, i + 1, count + 1);
sb.setLength(sb.length() - temp.length() - 1); // 恢复之前的状态
} else {
break; // 无需继续检查更长的字符串
}
}
}
public boolean isValid(String s) {
if (s == null || s.length() == 0 || s.length() > 3) {
return false;
}
if (s.charAt(0) == '0' && s.length() > 1) {
return false;
}
int num = Integer.parseInt(s);
return num >= 0 && num <= 255;
}
}
78.子集
子集问题，就是收集树形结构中，每一个节点的结果。 整体代码其实和 回溯模板都是差不多的。
题目链接/文章讲解：https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html
视频讲解：https://www.bilibili.com/video/BV1U84y1q7Ci
class Solution {
List<Integer> node = new LinkedList<>();
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
backtracking(nums, 0);
return list;
}
public void backtracking(int[] nums, int index){
list.add(new ArrayList<>(node));
if(index == nums.length){
return;
}
for(int i = index; i < nums.length; i ++){
node.add(nums[i]);
backtracking(nums, i+1);
node.removeLast();
}
}
}
90.子集II
大家之前做了 40.组合总和II 和 78.子集 ，本题就是这两道题目的结合，建议自己独立做一做，本题涉及的知识，之前都讲过，没有新内容。
题目链接/文章讲解：https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html
