[Leetcode][第491题][JAVA][递增子序列][回溯][RK算法]

╰半橙微兮° 2022-11-30 15:54 82阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

#### 【解答思路】 ####

###### 1. 二进制枚举 + 哈希 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

**复杂度**  
![在这里插入图片描述][20200825103459941.png_pic_center]

class Solution { 
        List<Integer> temp = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Set<Integer> set = new HashSet<Integer>();
        int n;
    
        public List<List<Integer>> findSubsequences(int[] nums) { 
            n = nums.length;
            //遍历所有可能 3位 由000-111（7=1<<3）
            for (int i = 0; i < (1 << n); ++i) { 
                findSubsequences(i, nums);
                int hashValue = getHash(263, (int) 1E9 + 7);
                if (check() && !set.contains(hashValue)) { 
                    ans.add(new ArrayList<Integer>(temp));
                    set.add(hashValue);
                }
            }
            return ans;
        }
    //7 ->111 全都选
        public void findSubsequences(int mask, int[] nums) { 
            temp.clear();
            for (int i = 0; i < n; ++i) { 
                if ((mask & 1) != 0) { 
                    temp.add(nums[i]);
                }
                mask >>= 1;
            }
        }
    //RK算法 
        public int getHash(int base, int mod) { 
            int hashValue = 0;
            for (int x : temp) { 
            //数组中有负数，范围是[-100, 100]，加101相当于将数组中的数往上提了100，并不会影响hash函数值的唯一性
                hashValue = hashValue * base % mod + (x + 101);
                hashValue %= mod;
            }
            return hashValue;
        }
    //检查是否有序
        public boolean check() { 
            for (int i = 1; i < temp.size(); ++i) { 
                if (temp.get(i) < temp.get(i - 1)) { 
                    return false;
                }
            }
            return temp.size() >= 2;
        }
    }

###### 2. 递归枚举 + 减枝 ######

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]

**复杂度**  
![在这里插入图片描述][20200825105006317.png_pic_center]

class Solution { 
        List<Integer> temp = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
        public List<List<Integer>> findSubsequences(int[] nums) { 
            dfs(0, Integer.MIN_VALUE, nums);
            return ans;
        }
    
        public void dfs(int cur, int last, int[] nums) { 
            if (cur == nums.length) { 
                if (temp.size() >= 2) { 
                    ans.add(new ArrayList<Integer>(temp));
                }
                return;
            }
            if (nums[cur] >= last) { 
                temp.add(nums[cur]);
                dfs(cur + 1, nums[cur], nums);
                temp.remove(temp.size() - 1);
            }
            if (nums[cur] != last) { 
                dfs(cur + 1, last, nums);
            }
        }
    }
    
    
    链接：https://leetcode-cn.com/problems/increasing-subsequences/solution/di-zeng-zi-xu-lie-by-leetcode-solution/

#### 【总结】 ####

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

###### 2.RK算法 哈希散列表 ######

[【数据结构与算法】字符串匹配 BF算法 RK算法  
][BF_ RK_]

转载链接：https://leetcode-cn.com/problems/increasing-subsequences/solution/di-zeng-zi-xu-lie-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/0aa6297f61074c9da5adb114bc658cad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/b11f42dc1e7e4e5b87334e8c2d4b6bd9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/056dc081cda542b392e1777e053c8404.png
[20200825103459941.png_pic_center]: /images/20221123/148f95d7af394142bb85f5220aa2b750.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/7b3eca1e4e7540798ba03a8a165525d1.png
[20200825105006317.png_pic_center]: /images/20221123/a7f172faa8b74ce6a1522c4fee1ffb4c.png
[BF_ RK_]: https://blog.csdn.net/dadongwudi/article/details/108206019