回溯——8.递增子序列

2024-09-07 13:36
文章标签 递增 序列 回溯

本文主要是介绍回溯——8.递增子序列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

力扣题目链接

给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是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]]

说明:

  • 给定数组的长度不会超过15。
  • 数组中的整数范围是 [-100,100]。
  • 给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况。

解题思路总结

  • 递归树的构建:程序通过回溯构建一个递归树,每一个节点代表一个数组元素,每条从根到叶的路径代表一个可能的子序列。通过遍历整个递归树,生成所有可能的子序列。
  • 递增条件:通过比较当前元素与子序列最后一个元素的大小,保证子序列是递增的。
  • 去重:每一层递归中使用 set 来去重,防止同一层中出现重复的元素。
  • 剪枝:通过条件 (path and nums[i] < path[-1]) 来剪掉不符合递增条件的分支,提升效率。

最终,程序返回所有找到的递增子序列。

完整代码如下:

class Solution:def findSubsequences(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):if len(path) > 1:result.append(path[:])  # 注意要使用切片将当前路径的副本加入结果集# 注意这里不要加return,要取树上的节点uset = set()  # 使用集合对本层元素进行去重for i in range(startIndex, len(nums)):if (path and nums[i] < path[-1]) or nums[i] in uset:continueuset.add(nums[i])  # 记录这个元素在本层用过了,本层后面不能再用了path.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()
class Solution:def findSubsequences(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return result
  • findSubsequences 是整个程序的入口函数,接收一个数组 nums 作为参数。
  • result 用来存储所有满足条件的递增子序列。
  • path 记录当前递归过程中的路径,也就是当前的子序列。
  • self.backtracking(nums, 0, path, result) 是回溯函数,目的是从数组 nums 中找到所有递增的子序列,并存入 result
  • return result 最后返回存储所有子序列的 result
def backtracking(self, nums, startIndex, path, result):if len(path) > 1:result.append(path[:])  # 使用切片将当前路径的副本加入结果集# 注意这里不要加return,要取树上的节点
  • startIndex:控制当前递归的起始点,防止重复计算。
  • path 的长度大于 1 时,表示 path 已经构成了一个符合条件的递增子序列,所以将其复制并加入 result使用切片 path[:] 是为了防止之后修改 path 时影响到 result 中已保存的结果
  • 这里没有直接返回,因为需要继续探索后面的递归,即使已经找到了一个合法的子序列,也可能找到更长的子序列。
    uset = set()  # 使用集合对本层元素进行去重for i in range(startIndex, len(nums)):if (path and nums[i] < path[-1]) or nums[i] in uset:continue
  • uset:用于存储当前层已经使用过的元素,避免在同一层递归中出现重复的子序列。
  • for i in range(startIndex, len(nums)):遍历数组中从 startIndex 开始的每一个元素。
  • 条件判断 (path and nums[i] < path[-1]) or nums[i] in uset
    • 如果 path 不为空并且当前元素 nums[i] 小于 path 的最后一个元素,表示当前子序列不是递增的,跳过这个元素。
    • 如果 nums[i] 已经在 uset 中,说明当前元素在本层已经使用过了,跳过这个元素。
  • uset.add(nums[i]):将当前元素加入 uset,以保证同一层递归中不会再次使用该元素。
        path.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()

  • path.append(nums[i]):将当前元素加入 path,构成当前的子序列。
  • self.backtracking(nums, i + 1, path, result):递归调用,继续从 i + 1 位置开始寻找下一个元素。
  • path.pop():回溯操作,将当前的元素从 path 中移除,回到上一层递归状态,探索其他可能的子序列。

 

这篇关于回溯——8.递增子序列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1145204

相关文章

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

day-50 求出最长好子序列 I

思路 二维dp,dp[i][h]表示nums[i] 结尾,且有不超过 h 个下标满足条件的最长好子序列的长度(0<=h<=k),二维数组dp初始值全为1 解题过程 状态转换方程: 1.nums[i]==nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h]+1) 2.nums[i]!=nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h-1

回溯——9.全排列

力扣题目链接 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 问题建模:题目要求给出一个数组的所有排列组合,属于典型的全排列问题,这可以用回溯法来解决。回溯法通过递归的方式,依次将数组中的每个元素放入排列中,直到生成

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

3177. 求出最长好子序列 II 题目链接 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ,那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。 实例1: 输入:nums = [1,2,1,1,3],

用Python实现时间序列模型实战——Day 14: 向量自回归模型 (VAR) 与向量误差修正模型 (VECM)

一、学习内容 1. 向量自回归模型 (VAR) 的基本概念与应用 向量自回归模型 (VAR) 是多元时间序列分析中的一种模型,用于捕捉多个变量之间的相互依赖关系。与单变量自回归模型不同,VAR 模型将多个时间序列作为向量输入,同时对这些变量进行回归分析。 VAR 模型的一般形式为: 其中: ​ 是时间  的变量向量。 是常数向量。​ 是每个时间滞后的回归系数矩阵。​ 是误差项向量,假

时间序列|change point detection

change point detection 被称为变点检测,其基本定义是在一个序列或过程中,当某个统计特性(分布类型、分布参数)在某时间点受系统性因素而非偶然因素影响发生变化,我们就称该时间点为变点。变点识别即利用统计量或统计方法或机器学习方法将该变点位置估计出来。 Change Point Detection的类型 online 指连续观察某一随机过程,监测到变点时停止检验,不运用到

Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的,但是可能代码比较复杂,这回来个简洁版的,这个是递归版本 可以看看之前的版本,两个版本面试用哪个都保过 解法都在代码里,不懂就留言或者私信 class Solution {/**对于之前的解法,我现在提供一共更优的解,但是这种可能会比较难懂一些(思想方面)代码其实是很简洁的,总体思想如下:不需要排序直接把所有数放入map,map的key是当前数字,value是当前数开始的

go json反序列化成指定类型

简介 简单的介绍一下使用go的json库,将json字符串反序列化成接口中指定的实现类 代码如下 package usejsontype ExamInterface interface {CheckRule(data any) bool}type IntStru struct {DefalutVal int `json:"defalut_val"`Max int `json: