代码随想录训练营Day 24|Python|Leetcode|491.递增子序列* 46.全排列* 47.全排列 II

news/2024/9/23 19:04:47/

491.非递增子序列

给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。

解题思路:

输入参数:def backtracking(nums, start_index)

停止条件:if len(path)>1: result.append(path)

递归逻辑:数层去重+检查是否递增

本题不必sort nums

class Solution:def findSubsequences(self, nums: List[int]) -> List[List[int]]:path = []result = []def backtracking(nums, start_index):if len(path)>1:result.append(path[:])# return#在每一层设置一个uset记录查重uset = set()for i in range(start_index, len(nums)):if path and nums[i] < path[-1]:continueif nums[i] in uset:continueuset.add(nums[i])path.append(nums[i])backtracking(nums, i+1)path.pop()backtracking(nums, 0)return result

46.全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

解题思路:

本题不用记录start_index只用记录使用过的数。当使用start_index时是为了让接下来可选择的数从当前数的下一个开始。

输入参数:def backtracking(nums, used)

停止条件:if len(path) == len(nums): append+return

回溯逻辑:检查该数字是否已经使用过,再进行递归

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:path = []result = []used = [0]*len(nums)def backtracking(nums, used):if len(path) == len(nums):result.append(path[:])returnfor i in range(len(nums)):if used[i] == 0:used[i] = 1path.append(nums[i])backtracking(nums, used)used[i] = 0path.pop()backtracking(nums, used)return result

47.全排列 II

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

解题思路:

本题要注意除重,判断上一个数字是否使用过,没有使用过并且前后数字相同就进行树层除重。

输入参数:def backtracking(nums, used)

停止条件:if len(path) == len(nums): result append

回溯逻辑:除重+除去使用已经用过的数字

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:path = []result = []used = [0]*len(nums)nums = sorted(nums)def backtracking(nums, used):if len(path) == len(nums):result.append(path[:])returnfor i in range(len(nums)):if i>0 and nums[i] == nums[i-1] and used[i-1] == 0:continueif used[i] == 0:used[i] = 1path.append(nums[i])backtracking(nums, used)used[i] = 0path.pop()backtracking(nums, used)return result


http://www.ppmy.cn/news/1428082.html

相关文章

windows安装多版本node.js

首先&#xff0c;你需要安装 nvm。如果你还没有安装 nvm&#xff0c;你可以在 bash 或者其他类似的 shell 中运行以下命令进行安装&#xff1a; curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.38.0/install.sh | bash这将下载并运行 nvm 的安装脚本。注意&#xf…

汽车牌照-C++

Description 小Y最近发现街上的汽车越来越多了.作为汽车的重要标志一汽车牌照也是越来越不够用了&#xff0c;已经从以前的十进制发展到三十六进制了.比如以前的一个汽车牌照“苏D88888&#xff0c;现在的牌照“苏DOYY11"。 小Y突发奇想&#xff0c;想知道他看到的大量汽…

FreeLearning C/C++ 译文集翻译完成

C 高级编程C 高级编程秘籍Qt Creator 应用开发C 游戏编程入门指南C 编程入门指南Boost.Asio C 网络编程Boost C 应用开发秘籍第二版C 数据结构与算法设计原理C Qt5 GUI 编程C 高性能编程C 反应式编程C 系统编程秘籍C 研讨会C 现代嵌入式编程秘籍C 专家编程&#xff1a;成为熟练…

Excel文件解析(Java)

一、概述 在应用程序的开发过程中&#xff0c;经常需要使用 Excel文件来进行数据的导入或导出。所以&#xff0c;在通过Java语言实现此类需求的时候&#xff0c;往往会面临着Excel文件的解析(导入&#xff09;或生成&#xff08;导出)。 在Java技术生态圈中&#xff0c…

STM32H750外设ADC之双重 ADC 模式

目录 概述 1 双重 ADC 模式介绍 1.1 双重 ADC模式 1.2 双重 ADC 模式的类型 2 双重 ADC 模式寄存器的配置 3 模式功能实现 3.1 注入同步模式 3.2 支持独立注入的常规同步模式 3.2.1 中断的方式 3.2.2 DMA 读取常规数据 3.3 支持独立注入的交替模式 3.3.1 中断触发…

【Rust】——项目实例:命令行实例(二)

&#x1f4bb;博主现有专栏&#xff1a; C51单片机&#xff08;STC89C516&#xff09;&#xff0c;c语言&#xff0c;c&#xff0c;离散数学&#xff0c;算法设计与分析&#xff0c;数据结构&#xff0c;Python&#xff0c;Java基础&#xff0c;MySQL&#xff0c;linux&#xf…

iPad苹果平板做电脑副屏

1 打开蓝牙 2 链接同样的wifi 3 系统偏好设置 4 添加显示器-选择自己的的ipad 4 显示器设置-选择“扩展显示器”&#xff08;这个一定要做才行&#xff09;

大屏-flex布局

<div class"container"><div class"title">标题</div><div class"content"><div class"item"></div><div class"item" style"width: calc((100% - 30) / 3 * 2)"><…