首页 > 其他分享 >【力扣】非递减子序列

【力扣】非递减子序列

时间:2024-03-09 16:34:33浏览次数:24  
标签:nums int back 力扣 startindex vector 序列 path 递减

题目

image
代码如下:

class Solution {
public:
vector<vector<int>> res;
vector<int> path;
bool occured(vector<int>& nums, int key, int startindex){
    for(int i = startindex; i < key; i++){
        if(nums[key] == nums[i]){
            return true;
        }
    }
    return false;
}
void backtrace(vector<int>& nums, int startindex, int length){
    if(length >= 2 && path.size() == length){
        //去重
        res.push_back(path);
    }
    if(startindex >= nums.size()){
        //控制子序列为非递减
        return ;
    }

    for(int i = startindex; i < nums.size(); i++){
        if(i != startindex && occured(nums, i,startindex)){
           continue;
        }
        if(nums[i] < path.back()){
            continue;
        }
        path.push_back(nums[i]);
        backtrace(nums, i+1, length+1);
        path.pop_back();
    }
}
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        res.clear();
        path.clear();
        for(int i = 0; i < nums.size(); i++){
            //先在path中遍历第一个元素
            //这一步写在backtrace里的话会很不好处理
            if(i != 0 && occured(nums, i,0)){
                continue;
            }
            path.push_back(nums[i]);
            backtrace(nums,i+1, 1);
            path.pop_back();
        }
        return res;
    }
};

如果把对path第一个元素的处理也写在backtrace里的话:

没写出来,不写了

标签:nums,int,back,力扣,startindex,vector,序列,path,递减
From: https://www.cnblogs.com/satsuki26681534/p/18062792

相关文章

  • 【力扣】子集II(回溯法)(排序函数的一种隐藏用法?)
    题目描述可以套回溯模版的题,但是在写的过程中发现,如果数组中有多个相同元素分散存在的话,就会有一些子集无法得到像这里的1,4,4,如果对数组从左到右枚举的话是无论如何都得不到的。对这样的数组使用排序函数后,造成的效果就是相同的元素都堆在了一起,这样就能正确地得到所有子集......
  • 【力扣】复原IP地址(回溯法)(分割问题)
    问题描述在这个题中,因为结果的数据类型为vector<string>所以直接在s中添加分割点比较方便,先看一下代码:classSolution{private:vector<string>result;//记录结果//startIndex:搜索的起始位置,pointNum:添加逗点的数量voidbacktracking(string&s,intst......
  • php xss 反序列化漏洞
    介绍反序列化漏洞,利用了后端服务的设计缺陷序列化和反序列化对象=(序列化)》字符串对象《(反序列化)=字符串序列化字符串构建首先,理解下对象序列化后是个嘛玩意儿上代码<?phpclasstest{public$a='hello';private$b='hello';protected$c='h......
  • day58 动态规划part15 代码随想录算法训练营 392. 判断子序列
    题目:392.判断子序列我的感悟:理解难点:听课笔记:我的代码:通过截图:代码易错点:老师代码:扩展写法-双指针:classSolution:defisSubsequence(self,s:str,t:str)->bool:#初始化两个指针,分别指向s和t的第一个字符i,j=0,0#......
  • 力扣回溯之 39. 组合总和
    //剪枝优化classSolution{  publicList<List<Integer>>combinationSum(int[]candidates,inttarget){    List<List<Integer>>res=newArrayList<>();    List<Integer>path=newArrayList<>();    A......
  • 【力扣】组合总和3(组合的去重)
    问题描述注意,如果数组里有两个元素的值相同,那么这两个元素是可以出现在同一个组合里的:但是:如果按前面的思路分析的话,会发现结果中出现很多相同的组合。像这样:这很明显是由于两个相同的1造成的,因为当前的startindex对应第一个1时,向下一层递归后,starindex定位的还是1,。如......
  • LeetCodeHot100 1.两数之和 46.字母异位词分组 128.最长连续序列
    1.两数之和https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-likedpublicint[]twoSum(int[]nums,inttarget){HashMap<Integer,Integer>map=newHashMap<>();for(inti=0;i<nums.l......
  • 【力扣】组合总数(回溯法)
    题目描述#include<iostream>#include<vector>usingnamespacestd;vector<vector<int>>res;vector<int>path;intaccumulate(vector<int>path){ intsum; for(inti=0;i<path.size();i++){ sum+=path[i]; } r......
  • spring-JSON序列化
    1,使用场景。SpringBoot默认json为JackJson。在Controller需要返回Json数据时,我们使用了RestController,如果想对返回的数据进行一定的处理,也就是序列化对象为Json时使用。反序列化,就是当接收的参数想做一定处理,获取到处理后的数据时候。2,JsonSerializer序列化1,自定......
  • day57 动态规划part14 代码随想录算法训练营 1143. 最长公共子序列
    题目:1143.最长公共子序列我的感悟:你永远不知道自己有多厉害!加油!理解难点:递推公式如何想,通过图,来记忆。听课笔记:我的代码:classSolution:deflongestCommonSubsequence(self,text1:str,text2:str)->int:#假设text1为内层,text2为外层n......