代码随想录一刷记录Day25——leetcode491.递增子序列

前言

之前就有刷代码随想录，但奈何总是三天打鱼两天晒网，而且刷的也很囫囵吞枣，于是乎决定参加代码随想录训练营，准备精刷一遍，希望自己能坚持下去，结营后自己的算法水平能更上一个level，冲ing！

leetcode491.递增子序列

题目链接leetcode491.递增子序列

思路

本题与昨天做的90.子集II看着（又是不能重复，又是收集每个子集，看着相似）只是多了递增的需求，实则区别较大。
1、在90.子集II 中是通过排序，再加一个标记数组来达到去重的目的。而本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了（例如{ 4 6 7 6 }排序完{ 4 6 6 7}很明显是一个递增子集，但是在{ 4 6 7 6 }中是根本找不到这个递增子集的）。
2、终止条件，本题要求递增子序列大小至少为2，所以终止条件为 当 path.size() > 1 时， result.push_back(path);收集
3、单层搜索逻辑，本题使用set来对本层元素进行去重。本题递归函数上面的uset.insert(nums[i]);，下面没有对应的pop之类的操作，这也是需要注意的点，unordered_set uset; 是记录本层元素是否重复使用，新的一层uset都会重新定义（清空），uset只负责本层！

代码

classSolution{private:vector<vector<int>>result;vector<int>path;voidbacktracking(vector<int>&nums,intstartIndex){if(path.size()>1){result.push_back(path);// 注意这里不要加return，要取树上的节点}unordered_set<int>uset;// 使用set对本层元素进行去重for(inti=startIndex;i<nums.size();i++){if((!path.empty()&&nums[i]<path.back())||uset.find(nums[i])!=uset.end()){continue;}uset.insert(nums[i]);// 记录这个元素在本层用过了，本层后面不能再用了path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}public:vector<vector<int>>findSubsequences(vector<int>&nums){result.clear();path.clear();backtracking(nums,0);returnresult;}};

leetcode

题目链接

思路

代码

leetcode

题目链接

思路

代码