Day 28

01. 复原 IP 地址（No. 93）

题目链接

代码随想录题解

1.1 题目

有效 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 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]

示例 2：

输入：s = “0000”
输出：[“0.0.0.0”]

示例 3：

输入：s = “101023”
输出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

1.2 笔记

如果要更好的理解这道题目，建议先去做一下

分割回文字符串（No. 131）

这里附上我的题解 代码随想录刷题笔记 DAY 26 | 组合总和 No.39 | 组合求和 II No.40 | 分割回文串 No.131

其实分割问题和组合问题非常类似，分割问题就是 对分割位置 的组合。

通过不断移动切割的位置来讲所有的情况遍历。

在切割过程中需要注意的是

1. 一共只能分割三次，因为 IP 是由四个整数组成的
2. 每次分割时要进行检测

下面来讲解具体的代码实现：

首先就是如何实现字符串的切割：这里用到的方法和上面分割回文字符串相同，也就是通过 index 表示本次切割的起点，通过循环变量 i 表示切割的终点

for (int i = index; i < s.length(); i++) {if ((i - index + 1) <= 3 && isValid(s, index, i)) {pointNum++;path.add(s.substring(index, i + 1));} else {continue;}backtracking(i+1, s);pointNum--;path.remove(path.size() - 1);
}

同时因为一共分割四次的限制，所以需要有一个变量来记录分割的次数 pointNum

分割的终点就是这个 pointNum 达到 3 的时候，也就是分割了三次，这时候要验证最后一段是否符合，如果符合就将其存入结果中

    if (pointNum == 3) {if (isValid(s, index, s.length()-1)) {// 对结果的处理String temp = String.join(".", path);temp += ".";temp += s.substring(index, s.length());res.add(temp);}return;}

最后就是如何判断分割的部分是否符合标准，总结一下判断标准

1. 不能是 0 开头的数字
2. 数字范围在 0 到 255

所以可以得出这样的逻辑：

• 首先判断字符串长度是否小于 3 同时大于 0（避免了转换越界的情况）
• 然后判断这个数字是否是以0 开头的数字
• 再去判断转换的数字是否在规定范围内

其中第一步在上面的 for 循环中已经做过了 if ((i - index + 1) <= 3 && isValid(s, index, i)) 这里只需要判断 0 即可

    public boolean isValid(String s, int startIndex, int endIndex) {int length = endIndex - startIndex + 1;if (length > 0) {String substr = s.substring(startIndex, endIndex+1);int number = Integer.parseInt(substr);// 表明是含有前导 0 的if (substr.length() > 1 && substr.startsWith("0")) {return false;}// 整数大小不符合规范if (!(number >= 0 && number <= 255)) {return false;}return true;} else {return false;}}

1.3 代码

class Solution {List<String> res = new ArrayList<>();List<String> path = new ArrayList<>(); // 路径变量int num = 0; // 统计分割的次数int pointNum = 0;public List<String> restoreIpAddresses(String s) {backtracking(0, s);return res;}public void backtracking(int index, String s) {if (pointNum == 3) {if (isValid(s, index, s.length()-1)) {String temp = String.join(".", path);temp += ".";temp += s.substring(index, s.length());res.add(temp);}return;}for (int i = index; i < s.length(); i++) {if ((i - index + 1) <= 3 && isValid(s, index, i)) {pointNum++;path.add(s.substring(index, i + 1));    } else {continue;}backtracking(i+1, s);pointNum--;path.remove(path.size() - 1);}}/**判断是否是正确的 IP 地址*/public boolean isValid(String s, int startIndex, int endIndex) {int length = endIndex - startIndex + 1;if (length > 0) {String substr = s.substring(startIndex, endIndex+1);int number = Integer.parseInt(substr);// 表明是含有前导 0 的if (substr.length() > 1 && substr.startsWith("0")) {return false;}// 整数大小不符合规范if (!(number >= 0 && number <= 255)) {return false;}return true;} else {return false;}}
}

02. 子集（No. 78）

题目链接

代码随想录题解

2.1 题目

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

2.2 笔记

子集问题其实就是组合问题的一种变式，组合问题是收集长度为 k 的组合，而子集问题就是收集长度为 0 到 nums.length 的所有组合。

这也就导致了其收集结果的位置和组合问题不同

这是收集长度为 2 的组合的递归树

这是收集子集的递归树

上述粉色的部分表示收集的结果，可以看出，子集就是对每个节点都做了信息的收集

for (int i = index; i < nums.length; i++) {path.add(nums[i]);res.add(new ArrayList(path));backtracking(i+1, nums);path.remove(path.size() - 1);
}

就是讲 res.add() 放到了 for 循环中

递归的终点就是起点越界的时候：

if (index > nums.length - 1) {return;
}

最后不要忘记将空集加上即可

2.3 代码

class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {res.add(new ArrayList<>());backtracking(0, nums);return res;}public void backtracking(int index, int[] nums) {if (index > nums.length - 1) {return;}for (int i = index; i < nums.length; i++) {path.add(nums[i]);res.add(new ArrayList(path));backtracking(i+1, nums);path.remove(path.size() - 1);}}
}

03. 子集 II（No. 90）

题目链接

代码随想录题解

3.1 题目

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

3.2 笔记

做过 组合总和II 的朋友对这种题目一定不陌生，这道题目其实就是 组合总和II 与上一题 子集的结合，组合总和II 的详解在这里，建议先做完再来尝试本题。

代码随想录刷题笔记 DAY 26 | 组合总和 No.39 | 组合求和 II No.40 | 分割回文串 No.131

本题的特点就是题目中出现了有相同元素的数组，所以需要做到层级去重，收集结果的方式和上面一题完全相同，这里直接给出代码。

3.3 代码

class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);res.add(new ArrayList<>());backtracking(0, nums);return res;}public void backtracking(int index, int[] nums) {// 和上题相同的出口if (index > nums.length - 1) {return;}for (int i = index; i < nums.length; i++) {// 层级的去重if (i > index && nums[i-1] == nums[i]) {continue;} else {path.add(nums[i]);}res.add(new ArrayList<>(path));backtracking(i+1, nums);path.remove(path.size() - 1);}}
}