491. Non-decreasing Subsequences

目录

一、题目描述

方法一、直接回溯+哈希表

方法二、二进制枚举+数组哈希

方法三、递归枚举

---

一、题目描述

491. Non-decreasing Subsequences

方法一、直接回溯+哈希表

class Solution {vector<vector<int>> res;vector<int> aseq;
public:vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums,0);return res;}void backtracking(vector<int>& nums,int start){if(aseq.size()>=2){res.push_back(aseq);}unordered_set<int> used_set;for(int i = start;i < nums.size();i++){if(aseq.size()>0 && aseq.back() >nums[i])continue;if(used_set.contains(nums[i]))continue;used_set.insert(nums[i]);aseq.push_back(nums[i]);backtracking(nums,i+1);aseq.pop_back();}}
};

由于题目保证-100<=nums[i]<=100，去重的哈希表也可以用数组来实现。

class Solution {vector<vector<int>> res;vector<int> aseq;
public:vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums,0);return res;}void backtracking(vector<int>& nums,int start){if(aseq.size()>=2){res.push_back(aseq);}vector<bool> used_set(201,false);for(int i = start;i < nums.size();i++){if(aseq.size()>0 && aseq.back() >nums[i])continue;if(used_set[nums[i]+100])continue;used_set[nums[i]+100] = true;aseq.push_back(nums[i]);backtracking(nums,i+1);aseq.pop_back();}}
};

方法二、二进制枚举+数组哈希

class Solution {
public:vector<vector<int>> findSubsequences(vector<int>& nums) {vector<vector<int>> res;vector<int> aseq;int n = nums.size();int m = 1<<n;unordered_set<int> seq_set;for(int mask = 0;mask < m;mask++){aseq.clear();for(int i = 0;i < n;i++){if(mask & (1<<i)){if(aseq.size() >0 && aseq.back() >nums[i])continue;aseq.push_back(nums[i]);}}if(aseq.size()<2)continue;int seq_id = hash_func(aseq);if(seq_set.contains(seq_id))continue;seq_set.insert(seq_id);res.push_back(aseq);}return res;}int hash_func(vector<int> &seq){int mod = int(1e9)+7;int base = 263;int n = seq.size();int res = 0;for(int i = 0;i <n;i++){res = 1LL*res*base%mod + (seq[i]+101);res %=mod;}return res;}
};

方法三、递归枚举

class Solution {vector<vector<int>> res;vector<int> aseq;unordered_set<int> seq_set;
public:vector<vector<int>> findSubsequences(vector<int>& nums) {dfs(nums,0,INT_MIN);return res;}void dfs(vector<int>& nums,int index,int last){if(index == nums.size()){if(aseq.size() >= 2){res.push_back(aseq);}return;}if(nums[index] >= last){aseq.push_back(nums[index]);dfs(nums,index+1,nums[index]);aseq.pop_back();}if(nums[index]!=last){dfs(nums,index+1,last);}}
};

如果难以理解上面去重的逻辑，也可以用数组哈希在收集结果的时候去重

class Solution {vector<vector<int>> res;vector<int> aseq;unordered_set<int> seq_set;
public:vector<vector<int>> findSubsequences(vector<int>& nums) {dfs(nums,0,INT_MIN);return res;}void dfs(vector<int>& nums,int index,int last){if(index == nums.size()){if(aseq.size() >= 2){int seq_id = hash_func(aseq);if(!seq_set.contains(seq_id)){seq_set.insert(seq_id);res.push_back(aseq);}}return;}if(nums[index] >= last){//保证结果序列是非递减的aseq.push_back(nums[index]);dfs(nums,index+1,nums[index]);aseq.pop_back();}// if(nums[index]!=last){dfs(nums,index+1,last);// }}int hash_func(vector<int> &seq){int mod = int(1e9)+7;int base = 263;int n = seq.size();int res = 0;for(int i = 0;i <n;i++){res = 1LL*res*base%mod + (seq[i]+101);res %=mod;}return res;}
};