Leetcode：491. 递增子序列（C++）

news/2024/11/16 20:38:41/

问题描述：

实现代码与解析：

回溯：

原理思路：

优化版：

原理思路：

问题描述：

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

实现代码与解析：

回溯：

class Solution {
public:vector<int> path;//记录路径vector<vector<int>> result;//记录结果void backtracking(vector<int> nums,int startIndex){//至少有两个元素if(path.size()>=2){result.push_back(path);}unordered_set<int> used;//记录本层使用过的数，去重for(int i=startIndex;i<nums.size();i++){//和上一个数比较,若小于，或与前面成功循环的数相同，则跳过此次循环，去重if((!path.empty()&&nums[i]<path.back())||used.find(nums[i])!=used.end()) continue;used.insert(nums[i]);path.push_back(nums[i]);//处理backtracking(nums,i+1);//递归path.pop_back();//回溯}return;}vector<vector<int>> findSubsequences(vector<int>& nums) {   backtracking(nums,0);return result;}
};

原理思路：

首先就是保证得到结果递增，我们在非第一个数时判断是否大于等于前一个数即可，若小于则跳过此次循环，进行下一次循环。

然后，此题与其他递归题不同的是，此题不能和其他回溯题一样来用排序去重，此题的顺序是规定不能变的，所以我们去重的话，就设置一个哈希表set来记录当前层用过的数，若发现已经用过，则跳过此层循环。

unordered_set<int> used;//记录本层使用过的数，去重

//和上一个数比较,若小于，或与前面成功循环的数相同，则跳过此次循环，去重
if((!path.empty()&&nums[i]<path.back())||used.find(nums[i])!=used.end()) continue;

最后，注意一下要记录用过的数，还有这里要记录每一个结点的结果，不要在记录结果时就返回掉了。

//至少有两个元素
if(path.size()>=2)
{result.push_back(path);
}

优化版：

class Solution {
public:vector<int> path;//记录路径vector<vector<int>> result;//记录结果void backtracking(vector<int> nums,int startIndex){//至少有两个元素if(path.size()>=2){result.push_back(path);}int used[201]={0};//记录本层使用过的数，去重for(int i=startIndex;i<nums.size();i++){//和上一个数比较,若小于，或与前面成功循环的数相同，则跳过此次循环，去重if((!path.empty()&&nums[i]<path.back())||used[nums[i]+100]==1) continue;used[nums[i]+100]=1;//等于1说明被用过了path.push_back(nums[i]);//处理backtracking(nums,i+1);//递归path.pop_back();//回溯}return;}vector<vector<int>> findSubsequences(vector<int>& nums) {   backtracking(nums,0);return result;}
};