93.复原IP地址
题目链接:93.复原IP地址
我的思路用的是和气割回文串一样的思路,先保存子穿,然后拼接之后再加入,与代码随想录里的方法有所不同。
代码
class Solution {
List<String> result = new ArrayList<>();
List<String> temp = new ArrayList<>();
StringBuilder str = new StringBuilder();
public List<String> restoreIpAddresses(String s) {
backtracking(s, 0);
return result;
}
public void backtracking(String s, int startIndex) {
if(temp.size() == 4) {
StringBuilder tempS = new StringBuilder(); // 用tempS来拼接temp集合里的元素
for(String st : temp) {
tempS.append(st);
}
if(tempS.toString().equals(s)) {
// 如果拼接之后相等,则说明这个temp集合是有效的
// 如果可以成为有效IP则开始加逗号
tempS = new StringBuilder();
tempS.append(temp.get(0));
for(int i = 1; i < temp.size(); i++) {
tempS.append("." + temp.get(i));
}
result.add(tempS.toString());
return;
}else {
return;
}
}
// 单层逻辑类似于切割回文子串
for(int i = startIndex; i < s.length(); i++) {
String sub = s.substring(startIndex, i + 1);
if(!isIP(sub)) {
continue;
}
temp.add(sub);
backtracking(s, i + 1);
temp.remove(temp.size() - 1);
}
}
public boolean isIP(String s) {
if(s.length() > 3) {
return false;
}else if((s.length() > 1 && s.charAt(0) == '0') || !(Integer.parseInt(s) >= 0 && Integer.parseInt(s) <= 255)) {
return false;
}else {
return true;
}
}
}
78. 子集
很简单,直接套模板,不用终止条件也行,因为有for循环,也会停止
class Solution {
List<Integer> temp = new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
backtracking(nums, 0);
return result;
}
public void backtracking(int[] nums, int startIndex) {
result.add(new ArrayList<>(temp));
for(int i = startIndex; i < nums.length; i++) {
temp.add(nums[i]);
backtracking(nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}
90.子集II
有两种办法去重,一种是先排序,然后用Set集合的特性,存储结果集,最后转化为List类型集合。第二中也是先排序,然后在回溯之后判断下一个元素是否重复,来去重。
代码1(哈希法)
class Solution {
List<Integer> temp = new ArrayList<>();
Set<List<Integer>> result = new HashSet<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backtracking(nums, 0);
List<List<Integer>> an = new ArrayList<>();
for(List<Integer> list : result) {
an.add(list);
}
return an;
}
public void backtracking(int[] nums, int startIndex) {
result.add(new ArrayList<>(temp));
for(int i = startIndex; i < nums.length; i++){
temp.add(nums[i]);
backtracking(nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}
代码2(常规去重法)
class Solution {
List<Integer> temp = new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backtracking(nums, 0);
return result;
}
public void backtracking(int[] nums, int startIndex) {
result.add(new ArrayList<>(temp));
for(int i = startIndex; i < nums.length; i++){
temp.add(nums[i]);
backtracking(nums, i + 1);
temp.remove(temp.size() - 1);
while(i + 1 < nums.length && nums[i + 1] == nums[i]) {
i++;
}
}
}
}
显然,常规去重法比哈希法快了1ms