代码随想录

2023-04-01 22:24| 来源: 网络整理| 查看: 265

491.递增子序列

链接：代码随想录

视频链接：https://www.bilibili.com/video/BV1EG4y1h78v

错误回答：

class Solution { public: // 数组中可能含有重复元素， //如出现两个整数相等，也可以视作递增序列的一种特殊情况 //子序列：不需要连续 //回溯的条件里加上要比上一层传过来的元素大 //不需要排序 //为了避免出现[4，7(第一个7)],[4，7(第二个7)]7这个数字只用第一个 vectorv; vectormv; vector findSubsequences(vector& nums) { backtracing(nums,0); return v; } void backtracing(vector &nums,int startIndex) { if(mv.size()>=2) { v.push_back(mv); } for(int j=startIndex;jstartIndex &&nums[j]==nums[j-1]) { continue; } if(nums[j]>=nums[startIndex])//保证递增 { mv.push_back(nums[j]); backtracing(nums,j+1); mv.pop_back(); } } } };

猜想：

这部分只能横向的约束递归树，无法纵向的约束。

修改条件，希望本层回溯节点必须比上层回溯节点值大

void backtracing(vector &nums,int startIndex) { if(mv.size()>=2) { v.push_back(mv); } for(int j=startIndex;jstartIndex &&nums[j]==nums[j-1]) { continue; } if(startIndex>=1 && nums[j]>=nums[startIndex-1])//保证递增 { mv.push_back(nums[j]); backtracing(nums,j+1); mv.pop_back(); } if(startIndex==0) { mv.push_back(nums[j]); backtracing(nums,j+1); mv.pop_back(); } } }

仍然不对，继续修改。pre=-101//记录上层回溯节点的值，本层回溯节点必须比上层回溯节点值大

class Solution { public: // 数组中可能含有重复元素， //如出现两个整数相等，也可以视作递增序列的一种特殊情况 //子序列：不需要连续 //回溯的条件里加上要比上一层传过来的元素大 //不需要排序 //为了避免出现[4，7(第一个7)],[4，7(第二个7)]7这个数字只用第一个 vectorv; vectormv; int pre=-101;//记录上层回溯节点的值，本层回溯节点必须比上层回溯节点值大 vector findSubsequences(vector& nums) { backtracing(nums,0,pre); return v; } void backtracing(vector &nums,int startIndex,int pre) { if(mv.size()>=2) { v.push_back(mv); } for(int j=startIndex;jstartIndex &&nums[j]==nums[j-1]) { continue; } if(nums[j]>=pre)//保证递增 { mv.push_back(nums[j]); int temp=pre; pre=nums[j]; backtracing(nums,j+1,pre); pre=temp; mv.pop_back(); } } } };

结果仍然不对。

去看了视频，发现我自己的横向去重部分的代码，还是建立在数组排序之上的，而这里给出的原数组根本没有排序，也就是说用

根本行不通。

老师这里用的是每一节点扩展的横向选择都重新建立一个unordered_set，从而对横向的进行去重。竖向的数枝和我想像的一样，不用去重。

另外，记录上一层的结果也不用像我一样单独加一个pre参数，而是使用了已经记录树枝路径的最后一个元素，也就是mv.back()去比较记录。用本层的nums[j]和mv.back ()进行比较。

结果：

class Solution { public: vectorv; vectormv; vector findSubsequences(vector& nums) { backtracing(nums,0); return v; } void backtracing(vector &nums,int startIndex) { if(mv.size()>=2) { v.push_back(mv); } //对于每一个要横向扩展的节点，新建unoredered_set去重 unordered_setuset; for(int j=startIndex;j

【本文地址】

代码随想录

代码随想录

今日新闻

推荐新闻