0%

leetcode每日一题-递增子序列

Posted on In ,

递增子序列

image1

方法一：深度优先搜索

1
List<List<Integer>> ans = new ArrayList<List<Integer>>();
2
List<Integer> temp = new ArrayList<Integer>();
3
public void dfs(int cur, int[] nums) {
4
    if (cur == nums.length) {
5
        // 判断是否合法，如果合法判断是否重复，将满足条件的加入答案
6
        if (isValid() && notVisited()) {
7
            ans.add(new ArrayList<Integer>(temp));
8
        }
9
        return;
10
    }
11
    // 如果选择当前元素
12
    temp.add(nums[cur]);
13
    dfs(cur + 1, nums);
14
    temp.remove(temp.size() - 1);
15
    // 如果不选择当前元素
16
    dfs(cur + 1, nums);
17
}

这是一个递归枚举子序列的通用模板，即用一个临时数组temp来保存当前选出的子序列，使用cur来表示当前位置的下标，在 dfs(cur, nums) 开始之前，$[0,cur-1]$这个区间内的所有元素都已经被考虑过，而$[cur,n]$ 这个区间内的元素还未被考虑。在执行 dfs(cur, nums) 时，我们考虑 cur 这个位置选或者不选，如果选择当前元素，那么把当前元素加入到 temp 中，然后递归下一个位置，在递归结束后，应当把 temp 的最后一个元素删除进行回溯；如果不选当前的元素，直接递归下一个位置。

为了保证子序列是递增的，规定只有当前的元素大于等于上一个选择的元素的时候才能选择这个元素，这样枚举出来的所有元素都是合法的。

为了保证子序列不重复，规定如果当前元素等于上一个选择的元素，那么当前元素必须被选择，只有当当前元素不等于上一个选择的元素，那么可以不选择当前元素。也就是说，因为如果有两个相同的元素，我们会考虑这样四种情况：

  1. 前者被选择，后者被选择

  2. 前者被选择，后者不被选择

  3. 前者不被选择，后者被选择

  4. 前者不被选择，后者不被选择

    其中第二种情况和第三种情况其实是等价的，我们这样限制之后，不会出现选择上一个元素而不选择当前元素，因为我们规定如果当前元素等于上一个选择的元素，那么当前元素必须被选择，也就是说我们舍弃了第二种，保留了第三种，于是达到了去重的目的。

1
class Solution {
2
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
3
    List<Integer> temp = new ArrayList<Integer>();
4
    public List<List<Integer>> findSubsequences(int[] nums) {
5
        dfs(0, Integer.MIN_VALUE, nums);
6
        return ans;
7
    }
8
9
    public void dfs(int cur, int last, int[] nums){
10
        if(cur == nums.length){
11
            if(temp.size() >= 2){
12
                ans.add(new ArrayList<Integer>(temp));
13
            }
14
            return;
15
        }
16
        if(nums[cur] >= last){
17
            temp.add(nums[cur]);
18
            dfs(cur+1, nums[cur], nums);
19
            temp.remove(temp.size()-1);
20
        }
21
        if(nums[cur] != last){
22
            dfs(cur+1, last, nums);
23
        }
24
    }
25
}

复杂度分析：

  • 时间复杂度：$O(n*2^n)$。
  • 空间复杂度：$O(n)$。

方法二：二进制枚举+哈希

我们可以对子字符串进行枚举，长度为n的字符串选择子序列有$2^n$种情况。之后需要解决去重问题，我们可以使用串哈希算法（即 Rabin-Karp 编码），每次我们找到一个合法序列的时候，都去计算这个序列的哈希值，用一个哈希表来记录已有的哈希值，如果该值已经出现在哈希表中，就舍弃这个序列，否则就把这个序列加入到答案中。

1
class Solution {
2
    List<Integer> temp = new ArrayList<Integer>();
3
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
4
    Set<Integer> set = new HashSet<Integer>();
5
    int n;
6
7
    public List<List<Integer>> findSubsequences(int[] nums) {
8
        n = nums.length;
9
        for (int i = 0; i < (1 << n); ++i) {
10
            findSubsequences(i, nums);
11
            int hashValue = getHash(263, (int) 1E9 + 7);
12
            if (check() && !set.contains(hashValue)) {
13
                ans.add(new ArrayList<Integer>(temp));
14
                set.add(hashValue);
15
            }
16
        }
17
        return ans;
18
    }
19
20
    public void findSubsequences(int mask, int[] nums) {
21
        temp.clear();
22
        for (int i = 0; i < n; ++i) {
23
            if ((mask & 1) != 0) {
24
                temp.add(nums[i]);
25
            }
26
            mask >>= 1;
27
        }
28
    }
29
30
    public int getHash(int base, int mod) {
31
        int hashValue = 0;
32
        for (int x : temp) {
33
            hashValue = hashValue * base % mod + (x + 101);
34
            hashValue %= mod;
35
        }
36
        return hashValue;
37
    }
38
39
    public boolean check() {
40
        for (int i = 1; i < temp.size(); ++i) {
41
            if (temp.get(i) < temp.get(i - 1)) {
42
                return false;
43
            }
44
        }
45
        return temp.size() >= 2;
46
    }
47
}

复杂度分析：

  • 时间复杂度：$O(n*2^n)$。
  • 空间复杂度：$O(2^n)$。