CC's Boat

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

0%

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

Posted on

LeetCode 491.递增子序列

这道题和leetcode 90.子集有类似之处，但是有一些tricky的细节需要考虑，这是第一版，有些瑕疵。

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

    private List<List<Integer>> ans = new LinkedList<>();
    private Set<List<Integer>> set = new HashSet<>();
    private List<Integer> path = new LinkedList<>();

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

        backtracking(nums, 0);
        ans.addAll(set);
        return ans;

    }

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

        // as the minimum valid sequence contains at least two elements, thus 
        // add those path whose length is greater than 1
        if (path.size() > 1) {
            set.add(new LinkedList<>(path));
        }
        

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

            /*
             * actually this kind of remove duplicate is non-sense
             * as it only function when the given array is like [4 6 7 7]
             * if it is changed to [4 7 6 7] it still causes duplicates
             */

            // rule out duplicate elements in same level
            if (i > startIndex && nums[i] == nums[i - 1]){
                continue;
            }

            // we are not sure whether this time of calling would
            // add a element or not ,thus record the previous size
            int recordPathSize = path.size();

            // for the topest level elements, directly add it
            if (path.size() == 0) {
                path.add(nums[i]);
            }else if (path.size() > 0) {
                // if current element is greater and equals to last added element
                if ( nums[i] >= path.get(path.size() - 1)){
                    path.add(nums[i]);
                }
            }

            // recursively call this func
            backtracking(nums, i + 1);

            // if we do add elements into the path, remove it 
            if (path.size() > recordPathSize) {
                path.remove(path.size() - 1);
            }
        }
    }
}

Version 2:

注意remove处，一开始我试图使用条件判断来判断之前的语句是否成功添加了元素，然后根据结果决定是否remove最后的元素，但是这样太繁琐了， 而且很容易出错，所以最好使用其相反的逻辑，去除所有不可能的枝干。

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

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

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

        backtracking(nums, 0);
        return ans;

    }

    private void backtracking (int[] nums, int startIndex) {
        
        // when traversing all the tree, add those path whose length is equal
        // and greater than 2 
        if (path.size() > 1) {
            ans.add(new LinkedList<>(path));
        }

        // number [-100, 100] maps to array ranged [0, 200]
        // records whether this num has been used 
        int[] used = new int[201];

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

            // if path is not empty and elment is less than last num or it has been used, skip
            if ( (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) || used[nums[i] + 100] == 1 ) {
                continue;
            }

            path.add(nums[i]);
            used[nums[i] + 100] = 1;

            backtracking(nums, i + 1);

            // avoid uncertain backtrack, ensure that whichever approach here must be successful add
            path.remove(path.size() - 1);           
        }
    }
}

LeetCode 46.全排列

使用一个标记数组是最便捷的方法

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

    private List<List<Integer>> ans = new LinkedList<>();
    private List<Integer> path = new LinkedList<>();
    private boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backtracking(nums);
        return ans;
    }

    private void backtracking (int[] nums) {
        
        // exits
        if (path.size() == nums.length) {
            ans.add(new LinkedList<>(path));
        }
        
        for (int i = 0; i < nums.length; i++) {

            if(used[i]) {
                continue;
            };

            path.add(nums[i]);
            used[i] = true;

            backtracking(nums);

            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

LeetCode 47.全排列ii

注意去重的效率问题，很巧妙的，如果将判断条件设置为(i > 0 && used[i - 1] && nums[i] == nums[i - 1]) 那么对于[1 1 1 1 ]这样的数组，前三个元素的搜索子树都是无效遍历，如果将其设置为(i > 0 && !used[i - 1] && nums[i] == nums[i - 1]) 这样的话，在第一个1的子树搜索完后，后续三个子树都不会继续搜索，这样效率得到了极大的提高

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

    private List<List<Integer>> ans = new LinkedList<>();
    private List<Integer> path = new LinkedList<>();
    private boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backtracking(nums);
        return ans;
    }

    private void backtracking (int[] nums) {
        
        // exits
        if (path.size() == nums.length) {
            ans.add(new LinkedList<>(path));
        }
        
        for (int i = 0; i < nums.length; i++) {

            // here is pruning but in a branch level
            // as used[i - 1] = true means we are in the branch of nums[i -1]
            // which is less efficient than directly remove this whole branch 

            // if(used[i] || (i > 0 && used[i - 1] && nums[i] == nums[i - 1])) {
            //     continue;
            // };
            
            // here is the pruning in level level (the same level on the tree)
            if(used[i] || (i > 0 && !used[i - 1] && nums[i] == nums[i - 1])) {
                continue;
            };

            path.add(nums[i]);
            used[i] = true;

            backtracking(nums);

            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}