• 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
  • 相关阅读:
    论文选题分享及思路(一)《基于C51单片机的自动化测量产线的设计》
    Sentinel
    基于matlab实现的中点放炮各类地震波时距曲线程序
    Web框架Gin
    Go 函数的健壮性、panic异常处理、defer 机制
    uboot 和 内存地址
    R语言ggplot2可视化:使用ggpubr包的ggviolin函数可视化小提琴图
    物联网设备通过MQTT接入华为iot平台
    如何满足计算机化系统验证(CSV):制药企业的指南
    C++ STL(十) --------- 位图模拟实现
  • 原文地址:https://blog.csdn.net/qq_38737428/article/details/127574133