93. 复原 IP 地址
List<String> result = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
/**
* <A href="https://leetcode.cn/problems/restore-ip-addresses/"> 93.复原IP地址 </A>
*/
public void backTracing(String s, int startIndex, int dotNum) {
if (dotNum == 4 && sb.length() < s.length() + 4) {
return;
}
if (dotNum == 4 && sb.length() == s.length() + 4) {
result.add(sb.toString());
return;
}
for (int i = startIndex; i < startIndex + 3 && i < s.length() && isValid(s, startIndex, i + 1); i++) {
sb.append(s.substring(startIndex, i + 1));
sb.append('.');
dotNum++;
backTracing(s, i + 1, dotNum);
dotNum--;
sb.delete(sb.length() - 1, sb.length()); // 移除点
sb.delete(sb.length() - (i + 1 - startIndex), sb.length()); // 移数字
}
}
public boolean isValid(String s, int startingIndex, int endIndex) {
if (endIndex - startingIndex != 1 && s.charAt(startingIndex) == '0') {
return false;
}
String d = s.substring(startingIndex, endIndex);
return Integer.parseInt(d) >= 0 && Integer.parseInt(d) <= 255;
}
这两题就很像,简单的我都不敢相信,我...
78. 子集
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
backTracing(nums, 0);
return res;
}
public void backTracing(int[] nums, int startIndex) {
res.add(new ArrayList<>(path));
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backTracing(nums, i + 1);
path.removeLast();
}
}
90. 子集 II
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backTracing2(nums, 0);
return res;
}
public void backTracing2(int[] nums, int startIndex) {
res.add(new ArrayList<>(path));
for (int i = startIndex; i < nums.length; i++) {
if (i > startIndex && nums[i] == nums[i - 1]) {
continue;
}
path.add(nums[i]);
backTracing2(nums, i + 1);
path.removeLast();
}
}
标签:10,AC,nums,int,length,startIndex,两题,new,sb
From: https://www.cnblogs.com/Chain-Tian/p/17041617.html