代码随想录Day24

目录

93.复原IP地址

78.子集

90.子集II

93.复原IP地址

本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。

注意注释部分。

class Solution {List<String> res = new ArrayList<>();public List<String> restoreIpAddresses(String s) {StringBuilder s1 = new StringBuilder(s);fun(s1, 0, 0);return res;}public void fun(StringBuilder s,int index,int count){// System.out.println(s+" count:"+count);if(count==3){if(check(s,index,s.length()-1)){res.add(s.toString());}return;}for(int i=index;i<s.length();i++){if(check(s,index,i)){s.insert(i+1,'.');fun(s,i+2,count+1);//count++不行s.deleteCharAt(i+1);}else{break;}}}public boolean check(StringBuilder s,int start,int end){if(start>end) return false;if(s.charAt(start)=='0' && start!=end){return false;}int num=0;for(int i = start; i <= end; i++){int temp=s.charAt(i)-'0';num=num*10+temp;if(num>255) return false;}return true;}
}

78.子集

或者直接先记录，就可以避免需要先录入空数组

class Solution {List<List<Integer>> result=new ArrayList<>();LinkedList<Integer> cur=new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {result.add(new ArrayList<>());fun(0,nums);return result;}public void fun(int index,int[] nums){if(index>=nums.length){return;}for(int i=index;i<nums.length;i++){cur.add(nums[i]);result.add(new ArrayList<>(cur));fun(i+1,nums);cur.removeLast();}}
}

90.子集II

class Solution {List<List<Integer>> res=new ArrayList<>();LinkedList<Integer> cur=new LinkedList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);fun(nums,0);return res;}public void fun(int[] nums,int index){res.add(new ArrayList<>(cur));if(index>=nums.length){return;}for(int i=index;i<nums.length;i++){if(i>index &&nums[i]==nums[i-1]) continue;//注意是大于index，而不是大于0cur.add(nums[i]);            fun(nums,i+1);          cur.removeLast();}}
}