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

张开发
• 2026/4/12 1:05:31 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

代码随想录一刷记录Day25——leetcode491.递增子序列
前言之前就有刷代码随想录但奈何总是三天打鱼两天晒网而且刷的也很囫囵吞枣于是乎决定参加代码随想录训练营准备精刷一遍希望自己能坚持下去结营后自己的算法水平能更上一个level冲ingleetcode491.递增子序列题目链接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:vectorvectorintresult;vectorintpath;voidbacktracking(vectorintnums,intstartIndex){if(path.size()1){result.push_back(path);// 注意这里不要加return要取树上的节点}unordered_setintuset;// 使用set对本层元素进行去重for(intistartIndex;inums.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,i1);path.pop_back();}}public:vectorvectorintfindSubsequences(vectorintnums){result.clear();path.clear();backtracking(nums,0);returnresult;}};leetcode题目链接思路代码leetcode题目链接思路代码

更多文章