代码随想录27期|Python|Day29|回溯算法|491.递增子序列|46.全排列|47.全排列 II

491. 非递减子序列

本题不是单纯的去重题目,而是需要保持数字在原数组的顺序。

比如:[4,5,6,7]和[4,6,5,7]相比,后者就不能选择[5,6,7]这个排列,因为违反了设置的顺序。所以去重的方法就只有哈希表

需要在每一层设置一个哈希表,也就是进入for循环前,来查询是否之前出现过这个数字。由于数字范围是-100~100所以数组就够了。

1、参数和返回值:参数和一般的回溯模版一致,返回值不需要(因为是找到全遍历)

2、终止条件:path长度大于2即可

3、中间处理逻辑:除了回溯的3行以外,需要加两个并列的判断条件,满足一个说明重复了:

(1)当前nums里i指向的数字小于path的最后一个

(2)used数组储存过该数字

此外在添加每个数字的时候还需要设置used == 1,但是不需要在回溯的时候消除,因为是在树的每一层进行标记,而不是进入了递归的树枝。

class Solution(object):def findSubsequences(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""res = []self.backtracking(0, [], res, nums)return resdef backtracking(self, start_idx, path, res, nums):if len(path) > 1:res.append(path[:])# 每一层开始初始化used数组used = [0] * 201for i in range(start_idx, len(nums)):if (path and nums[i] < path[-1]) or used[nums[i]+100] == 1:continuepath.append(nums[i])used[nums[i]+100] = 1self.backtracking(i+1, path, res, nums)path.pop()

46. 全排列

本题需要明确“层间”还是“树枝”上去重,对于组合问题,前面的数字不能再取,所以是层间去重,回溯的时候不用修改当前层的used数组,但是在树枝上去重的时候,需要在used数组上同样进行回溯,used就是一个用来标记的“伴随”数组。保证回溯之后,这个数字依然可以取到。

1、参数和返回值:除了模版的参数以外,还需要used作为一个数组参数跟着回溯;返回值不需要,因为是全遍历

2、终止条件:全排列,每一个数字都要用到,所以是path和nums数组长度相等的时候

3、中间处理:和上面used设置在for层遍历之前并且不做回溯修改不同,本题used需要在for内(树枝)上修改,并且在回溯之后要消除操作

class Solution(object):def permute(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""res = []# used数组作为一个参数进入回溯used = [0] * 21self.backtracking(nums, [], res, used)return resdef backtracking(self, nums, path, res, used):if len(path) == len(nums):res.append(path[:])returnfor i in range(len(nums)):if used[nums[i]+10] == 1:continueused[nums[i]+10] = 1path.append(nums[i])self.backtracking(nums, path, res, used)path.pop()# used需要回溯used[nums[i]+10] = 0

47. 全排列 II

本题是去重+排列的杂交题。

难点在于如何在去重的同时不排除第一次遍历这个排列的情况。

1、参数和返回值:和上一题的排列一致,也是全局的used数组加入到模版写法里,返回值为空

2、终止条件:全排列path长度等于nums长度

3、中间处理:两个判断,分别用于去重和进入递归:

(1)去重:当且仅当前一个数字已经被遍历and现在的数字和之前的是一样的时候,需要continue

(2)进入递归:当前数字未被遍历(注意不是上一个逻辑的else,不然很多不满足三个跳过条件之一的情况也会被加入)

class Solution(object):def permuteUnique(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""nums.sort()res = []used = [0] * 9self.backtracking(nums, [], res, used)return resdef backtracking(self, nums, path, res, used):if len(path) == len(nums):res.append(path[:])returnfor i in range(len(nums)):# 跳过的判断条件:和前面一个重复,并且前一个已经遍历了(防止第一次被剔除)if i > 0 and nums[i] == nums[i-1] and used[i-1] == 1:continue# 进入下一级的条件:在不重复的前提下,当前节点没有被遍历到if used[i] == 0:used[i] = 1path.append(nums[i])self.backtracking(nums, path, res, used)path.pop()used[i] = 0

 第29天完结我的天呐!!!我完全就是一整个我的天呐!

要注意细节和对于模版的裁剪依照的是题目的特殊条件和树的裁剪。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2659747.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

leaflet学习笔记-初始化vue项目(一)

leaflet简介 Leaflet是一款开源的轻量级交互式地图可视化JavaScript库&#xff0c;能够满足大多数开发者的地图可视化需求&#xff0c;其最早的版本大小仅仅38 KB。Leaflet能够在主流的计算机或移动设备上高效运行&#xff0c;其功能可通过插件进行扩展&#xff0c;拥有易于使用…

【Linux】指令(本人使用比较少的)——笔记(持续更新)

文章目录 ps -axj&#xff1a;查看进程ps -aL&#xff1a;查看线程echo $?&#xff1a;查看最近程序的退出码jobs&#xff1a;查看后台运行的线程组fd 任务号&#xff1a;将后台任务提到前台bg 任务号&#xff1a;将暂停的后台程序重启netstat -nltp&#xff1a;查看服务及监听…

C#中的Attribute详解(下)

C#中的Attribute详解&#xff08;下&#xff09; 一、Attribute本质二、Attribute实例化三、Attribute实例化的独特之处四、元数据的作用五、自定义Attribute实例六、Attribute的附着目标七、附加问题 一、Attribute本质 从上篇里我们可以看到&#xff0c;Attribute似乎总跟pu…

SAP VA01 创建带wbs号的销售订单包 CJ067的错误

接口错误提示如下 SAP官方 CJ067 124177 - VA01: CJ067 during WBS acct assgmt with a different business area S4的core 刚好能用上 实施 这个note后成功

nestjs入门教程系列(一):让项目先跑起来

nestjs启动基本步骤 Nest (NestJS) 是一个用于构建高效、可扩展的 Node.js 服务器端应用的框架。 它使用渐进式 JavaScript&#xff0c;构建并完全支持 TypeScript&#xff08;但仍然允许开发者使用纯 JavaScript 进行编码&#xff09;并结合了 OOP&#xff08;面向对象编程&am…

第二节-数据封装+传输介质

数据传输的形式&#xff1a; 1.电路交换 2.报文交换&#xff1a; 在数据之外&#xff0c;加上能够标识接收者以及发送者的信息 3.分组交换&#xff1a; 依然进行报文交换&#xff0c;不过讲每个数据的大小进行定义 应用层&#xff08;数据data&#xff09;->传输层&am…

K8S部署Harbor仓库实战

K8S部署Harbor仓库实战 K8S部署Harbor仓库实战 - 简书 创建文件目录 chartmuseum目录: /var/nfs/data/harbor/chartmuseumdatabase目录: /var/nfs/data/harbor/databasejobservice目录: /var/nfs/data/harbor/jobserviceredis目录: /var/nfs/data/harbor/redisregistry目录:…

深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第五节 引用类型复制问题及用克隆接口ICloneable修复

深入浅出图解C#堆与栈 C# Heaping VS Stacking 第五节 引用类型复制问题及用克隆接口ICloneable修复 [深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第一节 理解堆与栈](https://mp.csdn.net/mdeditor/101021023)[深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第二节…

【头歌实训】kafka-入门篇

文章目录 第1关&#xff1a;kafka - 初体验任务描述相关知识Kafka 简述Kafka 应用场景Kafka 架构组件kafka 常用命令 编程要求测试说明答案代码 第2关&#xff1a;生产者 &#xff08;Producer &#xff09; - 简单模式任务描述相关知识Producer 简单模式Producer 的开发步骤Ka…

Python跳动的爱心完整代码

文章目录 环境需求完整代码详细分析环境需求 python3.11.4PyCharm Community Edition 2023.2.5pyinstaller6.2.0(可选,这个库用于打包,使程序没有python环境也可以运行,如果想发给好朋友的话需要这个库哦~)【注】 python环境搭建请见:https://want595.blog.csdn.net/arti…

深入理解Mysql MHA高可用集群搭建:从实验到实战

1. 简介 MHA&#xff08;Master High Availability&#xff09;是一个高效的开源MySQL高可用性解决方案。由日本开发者yoshinorim&#xff08;前DeNA员工&#xff0c;现在Facebook&#xff09;创建&#xff0c;MHA支持MySQL的主从复制架构&#xff0c;自动化主节点故障转移。当…

支付宝 v3 验签如何实现

上次给大家介绍了 支付宝 v3 自签名如何实现&#xff0c;这次顺便再把验签也写一下。 为什么要验签 说起为什么要验签&#xff0c;如果要详细一点解释的话&#xff0c;可以写很多很多...... 我们就简单一点来解释&#xff1a;验签可以证明接收到的信息是支付宝给我的&#xf…

【信息安全原理】——拒绝服务攻击及防御(学习笔记)

&#x1f4d6; 前言&#xff1a;拒绝服务攻击&#xff08;Denial of Service, DoS&#xff09;是一种应用广泛、难以防范、严重威胁网络安全&#xff08;破坏可用性&#xff09;的攻击方式。本章主要介绍DoS的基本概念、攻击原理及防御措施。 目录 &#x1f552; 1. 定义&#…

sonarqube安装踩坑记录

如果用java1.8和mysql&#xff0c;则sonarqube版本不能超过7.8&#xff0c;看这里。 sonarqube7.8安装包地址&#xff1a; https://binaries.sonarsource.com/Distribution/sonarqube/sonarqube-7.8.zip 安装步骤&#xff1a; 1、下载sonarqube安装包 wget https://binari…

计算机毕业设计---ssm+mysql+jsp实现的校园二手市场交易平台源码

项目介绍 本系统主要实现的功能有&#xff1a; 前台&#xff1a;&#xff08;1&#xff09;二手物品信息查看、搜索。 &#xff08;2&#xff09;学生注册登录、个人信息修改。 &#xff08;3&#xff09;二手物品信息发布、编辑。 &#xff08;4&#xff09;二手物品评论、回…

mybatisX自动生成sql语句,尝试测试方法报错

今天我使用mybatisx自定义mapper方法生成sql语句后&#xff0c;在测试时报错 错误是MyBatis 无法找到映射的语句&#xff08;Statement&#xff09;引起的 我是这样操作的&#xff0c;在mapper接口自定义了一个方法 然后alt加enter&#xff0c;自动生成sql 结果 mapper.xml文件…

手机流量卡推广分销网站php源码,多功能的号卡推广分销管理系统

源码简介 拥有多个接口&#xff0c;包括运营商接口&#xff0c;并支持无限三级代理。 最简单易用的PHP系统&#xff0c;它自带自动安装向导&#xff0c;可以让你轻松安装和部署。 该系统集成了多个第三方接口资源&#xff0c;能够满足你的不同需求。采用全系统双色主题&…

MYSQL 索引结构 B+树 hash索引

B-Tree树 当节点存在五个key时&#xff0c;中间的key向上分裂形成树 B树 所有的数据都会出现在叶子节点&#xff0c;叶子节点形成一个单向链表 哈希索引 优点

Vulnhub-Al-Web-1.0 靶机复现完整过程

一、信息收集 1.主机发现 arp-scan -l2.端口扫描 nmap -sV -p- 192.168.200.16PORTSTATESERVICEVERSIONMAC Address80/TCPOpenhttpApache httpd00:0C:29:C4:1B:78 (VMware) 3.目录扫描 python dirsearch.py -u http://192.168.200.16扫描出来这两个文件&#xff0c;首先先…

java基础-回忆性记录

java基础 Java概括 jaava是一种计算机交流的高级编程语言&#xff0c;1995年java衍生&#xff0c;詹姆斯高斯林被世人称之为java之父。 java语言具有跨平台性 java程序并非可以直接运行的&#xff0c;在java程序编译完成后会形成与编译无关的class文件。Java具有跨平台性&a…