leetcode 93. 复原 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 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
题目链接
https://leetcode.cn/problems/restore-ip-addresses/
解题思路
核心是将三个 .放在哪儿？
- 不能有前导
0 - 整数位于
0到255之间
用 pointNum记录已插入 .的数量，index记录当前截断字符串的起始下标。那么只有当 index == s.length()和 pointNum == 4同时满足时，才是将整个字符串分割完成，即一次有效分割，添加结果到结果集合。其余情况均为无效分割。
同时只有当 pointNum < 3时，才在当前路径后添加 .
剪枝情况：
i - index < 3每一段ip至多不超过3个字符i > index && s.charAt(index) == '0'去除前导0Integer.parseInt(s.substring(index, i + 1)) > 255去除大于255的情况，由于题目明确s只包含数字，所以满足上述情况，其数值一定大于0，不用再做这部分剪枝
另一个关键点，使用 lenBefore记录当前情况的长度，之后使用 setLength(lenBefore)进行回溯删除。
class Solution {
List<String> ans = new ArrayList<>();
StringBuilder sb = new StringBuilder();
public List<String> restoreIpAddresses(String s) {
traceBack(s, 0, 0);
return ans;
}
public void traceBack(String s, int index, int pointNum) {
if (index == s.length() && pointNum == 4) {
ans.add(sb.toString());
return;
}
if (index == s.length() || pointNum == 4) return;
for (int i = index; i < s.length() && i - index < 3; i++) {
if (s.charAt(index) == '0' && i > index) break;
int num = Integer.parseInt(s.substring(index, i + 1));
if (num > 255) break;
int lenBefore = sb.length(); // 记录长度
sb.append(s, index, i + 1);
if (pointNum < 3) sb.append('.');
traceBack(s, i + 1, pointNum + 1);
sb.setLength(lenBefore); // 回溯删除
}
}
}
leetcode 78. 子集
题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
题目链接
https://leetcode.cn/problems/subsets
解题思路
在每次访问中记录当前的访问情况。终止状态可以不用写。
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
traceBack(nums, 0);
return ans;
}
public void traceBack(int[] nums, int index) {
ans.add(new ArrayList<>(path));
/*
if (index == nums.length) {
return;
}
*/
for (int i = index; i < nums.length; i++) {
path.add(nums[i]);
traceBack(nums, i + 1);
path.removeLast();
}
}
}
leetcode 90. 子集 II
题目描述
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
题目链接
https://leetcode.cn/problems/subsets-ii
解题思路
和上一题一样，不同的是，需要先对数组排序，然后使用 i > index && nums[i] == nums[i - 1]剪枝
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
traceBack(nums, 0);
return ans;
}
public void traceBack(int[] nums, int index) {
ans.add(new ArrayList<>(path));
if (index == nums.length) {
return;
}
for (int i = index; i < nums.length; i++) {
// i > index， 不是i > 0。只有用过了，才能筛，而不是从头开始
if (i > index && nums[i] == nums[i - 1]){
continue;
}
path.add(nums[i]);
traceBack(nums, i + 1);
path.removeLast();
}
}
}
评论