假设我们有一个整数数组,我们的任务是找到给定数组的所有不同可能的递增子序列,并且递增子序列的长度应至少为2。因此,如果数组类似于[4,6,7,7 ],则输出将类似于-[[[4,6],[4,7],[4,6,7],[4,6,7,7],[6,7],[6,7] ,7],[7,7],[4,7,7]。
为了解决这个问题,我们将遵循以下步骤-
定义一个名为res的数组以存储所有结果
制作一个称为“解决”的方法。这将需要nums数组,start和temp数组
如果temp的大小> 1,则将temp插入res
制作一组称为Visited
因为我在范围内开始到nums的大小
将x插入温度
调用solve(nums,i + 1,temp)
从临时结尾删除一个元素
x:= nums [i]
如果x在访问集中,则跳过循环的下一部分
将x插入访问集
如果temp为空或temp <= x的最后一个元素,则
在main方法中,调用solve(nums,0,temp)
返回资源
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<auto> > v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] << ", "; } cout << "],"; } cout << "]"<<endl; } class Solution { public: vector < vector <int> > res; void solve( vector <int>& nums, int start, vector <int> temp){ if(temp.size() > 1){ res.push_back(temp); } set <int> visited; for(int i = start; i < nums.size(); i++){ int x = nums[i]; if(visited.count(x))continue; visited.insert(x); if(temp.empty() || temp[temp.size() - 1] <= x){ temp.push_back(x); solve(nums, i + 1, temp); temp.pop_back(); } } } vector<vector<int>> findSubsequences(vector<int>& nums) { res.clear(); vector <int> temp; solve(nums, 0, temp); return res; } }; main(){ vector<int> v = {5,6,7,8}; Solution ob; print_vector(ob.findSubsequences(v)); }
[4,6,7,8]
输出结果
[[5, 6, ],[5, 6, 7, ],[5, 6, 7, 8, ],[5, 6, 8, ],[5, 7, ],[5, 7, 8, ],[5, 8, ],[6, 7, ],[6, 7, 8, ],[6, 8, ],[7, 8, ],]