代码随想录算法训练营第二十一天 | 93.复原IP地址 | 78.子集
Day 20 总结
- 自己实现中遇到哪些困难
- 一句话讲明白问题分类
- 组合问题和分割问题都是收集树的叶子节点，子集问题是找树的所有节点！
- 切割字符串问题回顾
- 昨天的切割回文子串，和今天的切割ip地址，都是需要将字符串拆分成 n 份。
- 只不过每一小份的长度不定，切完当前这一小份，再交给下层去切割剩余部分。
- 一句话讲明白问题分类
- 今日收获，记录一下自己的学习时间
- 17:30 - 19:00
93.复原IP地址
题目链接/文章讲解：代码随想录
题目链接：https://leetcode.cn/problems/restore-ip-addresses/
题目描述：
有效 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 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
实现思路：
将字符串分隔成四个部分，并且每个部分都是有效的数字0-255。
1.字符串分隔：一定是从前向后进行切割，先切割一个数字出来，然后再对剩下的字符串再次进行切割。然后要检查当前切割出来的字符串是不是合格的，如果前面都切不出来合格的字符串，后面的切割也没有意义，直接结束该分支的搜索。找到了一个合适的字符串，就传递到下层一次，再剩余字符串中继续切割。当前层切割的字符串长度慢慢递增。
2.检查切割的结果：到达搜索树的结尾时，要确保整个字符串已经切割完了，并且切割成了四个部分。排除不符合条件的分支，并把切割完的字符串收集到结果集合中。
回溯模板：
代码实现：
class Solution {
public List<String> results = new ArrayList<>();
public List<String> path = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
backtrack(s, 0);
return results;
}
// 参数：
// 返回值:
public void backtrack(String s, int startIndex) {
// 终止条件
if (path.size() > 4) {return;}
if (startIndex == s.length() && path.size() == 4) {
StringBuffer ipAddr = new StringBuffer();
for (int i=0; i<4; i++) {
ipAddr.append(path.get(i));
if (i < 3) {ipAddr.append(".");}
}
results.add(ipAddr.toString());
}
// 回溯单层搜索过程
for (int i=startIndex; i<s.length(); i++){
if (!isValid(s, startIndex, i+1)) {continue;}
path.add(s.substring(startIndex, i+1));
backtrack(s, i+1);
path.remove(path.size()-1);
}
}
public boolean isValid(String s, int start, int end) {
if (end - start > 3) {return false;}
if (s.charAt(start) == '0') {
if (end - start > 1) {return false;}
}
if (end - start > 2) {
if (s.charAt(start) == '0') {return false;}
if (Integer.parseInt(s.substring(start,end)) > 255) {return false;}
}
return true;
}
}
// 实现方案2
class Solution {
List<Integer> path = new ArrayList<>();
List<String> results = new ArrayList<>();
char[] arr;
public List<String> restoreIpAddresses(String s) {
arr = s.toCharArray();
backtrack(0);
return results;
}
public void backtrack(int startIdx) {
if (path.size() > 4 || startIdx > arr.length) return;
if (startIdx == arr.length && path.size() == 4) {
String s = "";
for (Integer i : path) s = s+i+".";
results.add(s.substring(0,s.length()-1));
}
for (int i=startIdx; i<arr.length; i++) {
int num = getNum(startIdx, i);
if (num == -1) return;
path.add(num);
backtrack(i+1);
path.remove(path.size()-1);
}
}
public int getNum(int start, int end) {
// 小于四位数
if (end - start >= 3) return -1;
// 没有前导0
if (arr[start] == '0') {
if (end > start) return -1;
return 0;
}
// 1-255
int num = 0;
while (start <= end) {
num = num * 10 + (int)(arr[start++]-'0');
}
if (num > 255) return -1;
return num;
}
}78.子集
题目链接/文章讲解：代码随想录
题目链接：https://leetcode.cn/problems/subsets/
题目描述：
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
实现思路：
收集搜索树上的所有节点。
回溯模板：
代码实现：
class Solution {
// 全局变量免去参数传递
List<List<Integer>> results = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int[] nums;
public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
results.add(new ArrayList<>(path)); // 空集
backtrace(0);
return results;
}
public void backtrace(int startIdx) {
// 到达底搜索树底层，向上返回
if (startIdx >= nums.length) return;
for (int i=startIdx; i<nums.length; i++) {
path.add(nums[i]);
results.add(new ArrayList<>(path)); // 收集所有情况
backtrace(i+1);
path.remove(path.size()-1);
}
}
}原文地址：https://blog.csdn.net/Noah_aa/article/details/143920742
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！