CC's Boat

一顾青山舟远去，归来仍是顾青山

0%

代码随想录算法训练营第二十七天

Posted on

LeetCode 93.复原ip地址

和分割字符串有一起同工之妙，剪枝还能再优化。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {

    List<String> ans = new LinkedList<>();
    List<String> path = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) {
            return ans;
        }
        backtracking(s, 0, 0);
        return ans;
    }

    private void backtracking (String s, int startIndex, int cnt) {

        // recursion exits
        if (cnt == 4) {
            if (startIndex >= s.length()) {
                String str = path.stream().collect(Collectors.joining("."));
                ans.add(str);
            }
            return;
        }
        
        for (int i = startIndex; i < s.length() - (4 - path.size()) + 1; i++) {
            // if the subString from [startIndex, i] is valid
            String subStr = s.substring(startIndex, i + 1);
            if (isValidIP(subStr)){
                
                path.add(subStr);
            }else {
                continue;
            }
            backtracking(s, i + 1, cnt + 1);
            path.remove(path.size() - 1);
        }
    }


    // used to check the given string is valid ip or not
    private boolean isValidIP (String str) {

        if (str != null) {

            if (str.length() > 3) {
                return false;
            }

            int num = Integer.valueOf(str) ;

            if (num < 0 || num > 255) {
                return false;
            }

            if (str.length() > 1 && str.charAt(0) == '0') {
                return false;
            }
            return true;
        }
        return false;
    }
}

LeetCode 78.子集

这道题一开始想的复杂了,一开始把它视为77组合问题的变体，求k = 0， k = nums.length 的组合，但是这样其实重复遍历了很多节点。其实换一个角度思考的话，把整颗树遍历过程中的每个节点都记录下来最后返回即可。

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
45
46
47
48
49
50
51
52
53
54
55
class Solution {

    List<List<Integer>> res = new LinkedList<>();
    List<Integer> path = new LinkedList<>();

    // high complexity
    // public List<List<Integer>> subsets(int[] nums) {

    //     for (int i = 0; i <= nums.length; i++) {
    //         backtracking1(nums, i, 0);
    //     }
        
    //     return res;
    // }

    // private void backtracking1 (int[] nums, int k, int index) {
    //     // recursion exits
    //     if (path.size() == k) {
    //         List<Integer> sub = new LinkedList<>();
    //         sub.addAll(path);
    //         res.add(sub);
    //         return;
    //     }

    //     // this is to remove those unvalid recursion
    //     for (int i = index; i < nums.length - (k - path.size()) + 1; i++) {
    //         path.add(nums[i]);
    //         backtracking(nums, k, i + 1);
    //         path.remove(path.get(path.size() - 1));
    //     }
    // }


    public List<List<Integer>> subsets(int[] nums) {
        helper(nums, 0);
        return res;
    }

    private void helper ( int[] nums, int startIndex) {

        // add very node during traverse
        res.add(new LinkedList<>(path));

        if (startIndex >= nums.length) {
            return;
        }

        for (int i = startIndex; i < nums.length; i++) {
            
            path.add(nums[i]);
            helper(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

LeetCode 90.子集-ii

没什么新奇的东西，数组有重复元素所以要先排列，在添加元素到path前判断是否已经基于相同元素遍历过一次了。

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
class Solution {

    List<List<Integer>> ans = new LinkedList<>();
    List<Integer> path = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        // as there are duplicates elements, thus we need to sort the array first
        Arrays.sort(nums);
        backtracking(nums, 0);
        return ans;
    }

    private void backtracking (int[] nums, int startIndex) {
        ans.add(new LinkedList<>(path));

        for (int i = startIndex; i < nums.length; i++) {

            if (i > startIndex && nums[i] == nums[i - 1]) {
                continue;
            }else {
                path.add(nums[i]);
            }

            backtracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}