代码随想录day27

93. 复原 IP 地址

https://leetcode.cn/problems/restore-ip-addresses/
参考上一题，本题需要的判断条件更多了一些，回溯时用“.”来判断。

class Solution {
    List<String> result = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    int num=0;
    public List<String> restoreIpAddresses(String s) {
        if(s.length()<4||s.length()>12) return result;
        realIp(s,0);
        return result;
    }
    private void realIp(String s,int start){
        if (num==4) {
            result.add(path.toString().substring(1, path.length()));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if(i-start>2||(s.length()-i-1)<(3-num)){
                break;
            }
            if ((s.length()-i-1)<=(3-num)*3&&isIp(s, start, i)) {
                String str = s.substring(start, i + 1);
                path.append(".");
                path.append(str);
                num++;
            } else {
                continue;
            }
            realIp(s, i + 1);
            num-=1;
            while(path.charAt(path.length()-1)!='.'){
                path.deleteCharAt(path.length()-1);
            }
            path.deleteCharAt(path.length()-1);
        }
    }
    private boolean isIp(String s,int start,int end){
        if(end>start&&s.charAt(start)=='0'){
            return false;
        }
        if(Integer.parseInt(s.substring(start, end+1))>=0&&Integer.parseInt(s.substring(start, end+1))<=255){
            return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

改进

class Solution {
    List<String> result = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    int num=0;
    public List<String> restoreIpAddresses(String s) {
        if(s.length()<4||s.length()>12) return result;
        realIp(s,0);
        return result;
    }
    private void realIp(String s,int start){
        if (num==4) {
            result.add(path.toString());
            return;
        }
        for (int i = start; i < s.length()&&i-start<3&&(s.length()-i-1)>=(3-num); i++) {
            if ((s.length()-i-1)<=(3-num)*3&&isIp(s, start, i)) {
                String str = s.substring(start, i + 1);
                path.append(str);
                if(num<3){
                    path.append(".");
                }
                num++;
            } else {
                continue;
            }
            realIp(s, i + 1);
            num-=1;
            path.delete(start + num, path.length());
        }
    }
    private boolean isIp(String s,int start,int end){
        if(end>start&&s.charAt(start)=='0'){
            return false;
        }
        if(Integer.parseInt(s.substring(start, end+1))>=0&&Integer.parseInt(s.substring(start, end+1))<=255){
            return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

78. 子集

https://leetcode.cn/problems/subsets/
和组合不同在于收集结果的位置不同。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        result.add(path);
        ziji(nums,0);
        return result;
    }
    private void ziji(int[] nums,int start){
        if(start>=nums.length){
            return;
        }
        for(int i=start;i<nums.length;i++){
            path.add(nums[i]);
            result.add(new ArrayList<>(path));
            ziji(nums,i+1);
            path.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

写在前面不用在主函数中先添加空子集了。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        ziji(nums,0);
        return result;
    }
    private void ziji(int[] nums,int start){
        result.add(new ArrayList<>(path));
        for(int i=start;i<nums.length;i++){
            path.add(nums[i]);
            ziji(nums,i+1);
            path.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

90. 子集 II

https://leetcode.cn/problems/subsets-ii/
在哪里去重是个问题。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        ziji(nums,0);
        return result;
    }
    private void ziji(int[] nums,int start){
        result.add(new ArrayList<>(path));
        for(int i=start;i<nums.length;i++){
            path.add(nums[i]);
            ziji(nums,i+1);
            path.removeLast();
            while(i+1<nums.length&&nums[i]==nums[i+1]){
                i++;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        ziji(nums,0);
        return result;
    }
    private void ziji(int[] nums,int start){
        result.add(new ArrayList<>(path));
        for(int i=start;i<nums.length;i++){
            if(i-start>0&&nums[i]==nums[i-1]){
                continue;
            }
            path.add(nums[i]);
            ziji(nums,i+1);
            path.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20