No.1
题目
复原IP地址
思路
- 写一个函数,判断是否是有效的IP地址元素(即两点之间的部分是否合法)
- 这是一个分割问题
- 回溯法
递归分析
- 全局变量:``List path
,
List result`
- 返回值:空,参数:原始字符串,
startIndex
- 终止条件
- 字符串用光了,且
path
有4个元素,存储结果,返回
- 单层递归逻辑
- 处理当前节点
- 如果合法,且
path
不超过4个成员,进入下层递归
- 回溯,抛出当前节点
代码
public boolean judger(String str) {
int len = str.length();
// 超过3位
if (len > 3)
return false;
// 有先导0
if (len > 1 && str.indexOf("0") == 0)
return false;
// 超过255
if (Integer.parseInt(str) > 255)
return false;
return true;
}
private List<String> path;
private List<String> result;
public void restoreHelper(String s, int startIndex) { // before, not included
if (startIndex >= s.length() && path.size() == 4) {
StringBuilder sb = new StringBuilder();
for (String value : path) {
sb.append(value);
sb.append(".");
}
sb.deleteCharAt(sb.length() - 1); // 去掉最后多余的"."
result.add(sb.toString());
}
for (int i = startIndex; i < s.length(); i++) {
String subStr = s.substring(startIndex, i + 1);
if (path.size() < 4) { // 保证path不超过4个元素
path.add(subStr);
if (judger(subStr))
restoreHelper(s, i + 1);
path.remove(path.size() - 1);
}
}
}
public List<String> restoreIpAddresses(String s) {
path = new ArrayList<>();
result = new ArrayList<>();
restoreHelper(s, 0);
return result;
}
No.2
题目
子集
思路
- 回溯法
- 首先要对数组排序
- 和之前的组合收集叶子节点不同,这里要收集树的所有节点,所以递归退出的地方没有任何操作,而在每次节点更新后,同步更新
result
代码
private List<Integer> path;
private List<List<Integer>> result;
public void subsetHelper(int[] nums, int startIndex) {
if (startIndex >= nums.length)
return;
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
result.add(new ArrayList<>(path));
subsetHelper(nums, i + 1);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> subsets(int[] nums) {
path = new ArrayList<>();
result = new ArrayList<>();
result.add(new ArrayList<>()); // 先塞一个[]
Arrays.sort(nums);
subsetHelper(nums, 0);
return result;
}
No.3
题目
子集 II
思路
- 回溯法
- 稍微精简了代码
- 输入存在重复元素,要排序后去重
代码
private List<Integer> path;
private List<List<Integer>> result;
public void subsetHelper(int[] nums, int startIndex) {
result.add(new ArrayList<>(path));
if (startIndex >= nums.length)
return;
for (int i = startIndex; i < nums.length; i++) {
// 去除重复结果
if (i > startIndex && nums[i] == nums[i - 1])
continue;
path.add(nums[i]);
subsetHelper(nums, i + 1);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
path = new ArrayList<>();
result = new ArrayList<>();
Arrays.sort(nums);
subsetHelper(nums, 0);
return result;
}