• leetcode(力扣) 491. 递增子序列(回溯 & 去重思路)


    题目描述

    给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
    数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。

    示例 1:
    输入:nums = [4,6,7,7]
    输出:[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

    示例 2:
    输入:nums = [4,4,3,2,1]
    输出:[[4,4]]

    思路分析

    又是一道回溯题。
    老规矩 三步走:

    1.确定函数参数:
    这个题的参数没什么变化,就还是那个startindex,前面说过无数遍了,就不说了。

    2.确定终止条件:
    这是这道题比较有意思的地方,终止条件可以理解为,收集结果的地方,实际上对于包括之前的子集问题,是没有终止条件的,就是任何子节点的结果都需要,而这道题唯一需要注意的两个地方就是,当前记录的答案里面是不是的元素是不是大于1个,而且是不是递增的。
    是否递增可以去for循环里控制,这里只需要判断记录的答案里是不是元素是不是有2个及以上就行了。

     if len(path) >=2:
        res.append(path[:])  #注意这里不要加return,要取树上的节点
    
    • 1
    • 2

    3.确定循环体:

    因为这道题需要去重,而又不能用之前组合总和2里的那个去重思路,因为这是找子序列,不能排序,排序之后顺序就乱了。

    两个去重思路,一个是收集答案的时候,看看答案里有没有重复的,没有的话再收集。这个思路比较简单。

    另一个思路就是,建立一个数组repeat,记录本层树层使用过的元素,如果使用过就直接continue。

    细节;

    这里有一个需要注意的地方,就是去重数组repeat在哪里定义的问题,看下面的代码可以看到,我的答案集合res,和记录路径元素集合path都是在外面函数定义的,而reapeat是在回溯函数里定义的。

    要知道repeat去重的是树层,也就是本层里重复的元素,纵向的重复是不记录的,关于这点,在之前的组合里有说过,这就不细说了,总之就是一个答案内的元素可以重复,多个答案之间不能相同。

    而每一次向下一层走的时候都是一次递归,向下走一次(纵向)就是一个新的一层(横向),所以repeat = [] 定义在回溯,递归的函数里,每次向下走 就让他清空一次,记录新一层重复的值。

    完整代码

    思路1class Solution:
        def findSubsequences(self, nums: List[int]) -> List[List[int]]:
                res = []
                path = []
                def backtrack(startindex):
                    # 确定终止条件
                    if len(path) >=2:
                        if path[-1]>=path[-2] :
                            temp = path[:]
                            if temp not in res:
                                res.append(temp)
                        else:
                            return
                    for i in range(startindex,len(nums)):
                        path.append(nums[i])
                        backtrack(i+1)
                        path.pop()
                backtrack(0)
                return res
    
    思路2class Solution:
        def findSubsequences(self, nums: List[int]) -> List[List[int]]:
            res = []
            path = []
            def backtrack(startindex):
                # 确定终止条件
                repeat = []
                if len(path) >=2:
                    res.append(path[:])
                for i in range(startindex,len(nums)):
                    if nums[i] in repeat:
                        continue
                    if len(path) >=1 and path[-1] > nums[i]:
                        continue
                    repeat.append(nums[i])
                    path.append(nums[i])
                    backtrack(i+1)
                    path.pop()
            backtrack(0)
            return res
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
  • 相关阅读:
    Python制作七夕表白实例项目-让你的情人心动起来
    常用的数据库连接池、配置参数及相应的调优方法
    基于SSM的乡镇篮球队管理系统设计与实现
    图片铺满div元素不变形,超出部分隐藏,保留中心部分css代码
    vcruntime140.dll缺失如何修复,vcruntime140.dll重新安装方法分享
    Flask 学习-33.restful-full 请求参数校验reqparse.RequestParser()
    javaScript数组的方法
    苹果ios打包签名ipa文件应用app的验证的证书是怎么授信的原理是什么?
    2.区块链系列之部署合约
    『 Linux 』 进程间通信概述
  • 原文地址:https://blog.csdn.net/qq_38737428/article/details/127574133