代码随想录算法训练营 Day29 | LeetCode491.递增子序列、LeetCode46.全排列、LeetCode47.全排列 II

LeetCode491.递增子序列

该题强调与之前的题目的不同在于给的数组顺序不能变换,这就导致了不能用used数组+判断与前一个元素是否相同的方法进行去重的操作,因此该题加入了一个set,不和前一个元素比,而是判断之前有没有处理过这个值来进行去重的操作。

细节:1、本题set写在回溯函数内部,也就是树每深入一层就创建一个新的set,而我们是树层去重,只要保证每一层的树使用的是同一个set即可,并且set不需要进行回溯操作。
2、剪枝操作利用的是continue;因为不是排序数组,所以即时有不符合条件的数组,后面的结果也是可能符合要求的。
3、本题还有一个效率比较高的去重操作,不使用set,而是使用哈希,因为题目中对数的范围做了限制,所以可以定义一个200容量的数组,将数的值作为哈希数组的下标,修改对应下标的值来说明该元素被处理过,同样的,这个数组需要定义在回溯函数里面。

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums,int startIndex){if(path.size()>1) result.push_back(path);if(startIndex==nums.size()){return;}unordered_set<int> used;for(int i=startIndex;i<nums.size();i++){if(used.find(nums[i])!=used.end() ||(!path.empty() && nums[i]<path.back())){continue;}used.insert(nums[i]);path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}return;}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums,0);return result;}
};

LeetCode46.全排列

本题就是强调排列顺序,那么原理也比较简单,去重为也可以理解与组合问题类似,组合问题去重则是不考虑当前索引之前的元素,而排列问题去重则是不考虑上一次考虑过的元素,还是有一些区别的。在一条树枝下,如果取过了这个值,就不再取了,需要用到一个used数组作为参数传入进来,并涉及回溯的操作。

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums,vector<bool> used){if(path.size()==nums.size()){result.push_back(path);return;}for(int i=0;i<nums.size();i++){if(used[i]==true){continue;}path.push_back(nums[i]);used[i]=true;backtracking(nums,used);used[i]=false;path.pop_back();}}vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(),false);backtracking(nums,used);return result;}
};

LeetCode47.全排列 II

本题包含重复元素,就又需要涉及到去重操作了,重复元素的去重步骤参考if语句的前两个条件,但关键是要实现树层去重,也就是used[i-1]==false的条件,因为如果在树枝上也会满足前两个条件,加了第三个条件就可以保证是树层去重。在组合问题中,因为有startIndex,就自动将树枝去重问题排除掉了。

那发现本题used[i-1]不管等于true还是false,都可以通过,但是不能不写,等于false才是真正树层去重的逻辑,去掉的分支更多一点,因此也效率更高。

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums,vector<bool> used){if(path.size()==nums.size()){result.push_back(path);return;}for(int i=0;i<nums.size();i++){if(i>0 && nums[i]==nums[i-1] && used[i-1]==false) continue; if(used[i]==true) continue;path.push_back(nums[i]);used[i]=true;backtracking(nums,used);used[i]=false;path.pop_back();}return;}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());vector<bool> used(nums.size(),false);backtracking(nums,used);return result;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

网工内推 | 项目经理,软考证书优先,最高26K,加班补贴

01 龙盈智达 招聘岗位&#xff1a;项目经理 职责描述&#xff1a; 1 根据业务员需求&#xff0c;完成生态圈下账簿中心系统的开发管理工作。 2 负责账簿中心实施过程中的需求调研分析、方案设计、开发测试、系统上线等工作的计划、组织协调、沟通等方面管理工作。 3 完成系统核…

golang学习6,glang的web的restful接口传参

1.get传参 //get请求 返回json 接口传参r.GET("/getJson/:id", controller.GetUserInfo) 1.2.接收处理 package controllerimport "github.com/gin-gonic/gin"func GetUserInfo(c *gin.Context) {_ c.Param("id")ReturnSucess(c, 200, &quo…

RabbitMQ的常见工作模式

Work queues 工作队列模式 模式说明 通过Helloworld工程我们已经能够构建一个简单的消息队列的基本项目&#xff0c;项目中存在几个角色:生产 者、消费者、队列&#xff0c;而对于我们真实的开发中 &#xff0c;对于消息的消费者通过是有多个的。 比如在实现用户注册功能时&…

社区团购小程序有哪些功能 怎么制作开通

​随着社区团购的兴起&#xff0c;越来越多的人开始关注社区团购小程序的制作。社区团购小程序是一种基于移动互联网的新型购物方式&#xff0c;通过小程序&#xff0c;用户可以在社区内方便地参与团购活动&#xff0c;享受到更优惠的价格和更方便的购物体验。下面具体介绍社区…

Vite 构建的 Vue3 项目如何整合 Monaco Editor 代码编辑器

目录 &#x1f981; 一. 前言&#x1f981; 二. 探索过程2.1 安装2.2 配置 Monaco Editor2.3 编写 Monaco Editor 代码编辑器2.3.1 创建 Coding Editor 组件2.3.2 父组件使用 CodingEditor 组件 2.4 效果展示 三. 总结 &#x1f981; 一. 前言 各位好&#xff01;我是&#x1…

【分布式事务 XA模式】MySQL XA模式详解

MYSQL中的XA事务 写在前面1. XA事务的基本原理2. MySQL XA事务操作 写在前面 MySQL 的 5.0.3 版本开始支持XA分布式事务&#xff0c;并且只有innoDB存储引擎支持XA事务。 1. XA事务的基本原理 XA事务本质上是一种基于两阶段提交的分布式事务&#xff0c;分布式事务可以理解成…

R语言数学建模(二)—— tidymodels

R语言数学建模&#xff08;二&#xff09;—— tidymodels 文章目录 R语言数学建模&#xff08;二&#xff09;—— tidymodels前言一、示例数据集二、拆分数据集2.1 拆分数据集的常用方法2.2 验证集2.3 多层次数据2.4 其他需考虑问题 三、parsnip用于拟合模型3.1 创建模型3.2 …

redis启动错误

错误&#xff1a; Creating Server TCP listening socket 127.0.0.1:6379: bind: No error redis-server.exe redis.windows.conf redis-cli.exe shutdown auth "yourpassword"

嵌入式 Linux 下的 LVGL 移植

目录 准备创建工程修改配置修改 lv_drv_conf.h修改 lv_conf.h修改 main.c修改 Makefile 编译运行更多内容 LVGL&#xff08;Light and Versatile Graphics Library&#xff0c;轻量级通用图形库&#xff09;是一个轻量化的、开源的、在嵌入式系统中广泛使用的图形库&#xff0c…

配电房轨道式巡检机器人方案

一、应用背景 在变电站、配电房、开关站等各种室内变配电场所内&#xff0c;由于变配电设备的数量众多、可能存在各类安全隐患&#xff0c;为了保证用电的安全可靠&#xff0c;都要进行日常巡检。 但目前配电房人工巡检方式有以下主要问题&#xff1a; 巡检工作量大、成本高 …

k8s初始化报错 [ERROR CRI]: container runtime is not running: ......

一、环境参数 linux系统为centos7kubernetes版本为v1.28.2containerd版本为1.6.28 二、报错内容 执行初始化命令kubeadm init命令时报错&#xff0c;内容如下 error execution phase preflight: [preflight] Some fatal errors occurred:[ERROR CRI]: container runtime is…

HarmonyOS开发云工程与开发云函数

创建函数 您可直接在DevEco Studio创建函数、编写函数业务代码、为函数配置调用触发器。 1.右击“cloudfunctions”目录&#xff0c;选择“New > Cloud Function”。 2.输入函数名称后&#xff0c;点击“OK”。 函数名称仅支持小写英文字母、数字、中划线&#xff08;-&a…

1.1 编程环境的安装

汇编语言 汇编语言环境部署 第二个运行程序直接双击安装一直下一步即可MASM文件复制到D盘路径下找到dosbox安装路径&#xff1a;C:\Program Files (x86)\DOSBox-0.74找到该文件双击打开它&#xff0c;修改一下窗口大小 把这两行改成如下所示 运行dos&#xff0c;黑框中输入mou…

Go Run - Go 语言中的简洁指令

原文&#xff1a;breadchris - 2024.02.21 也许听起来有些傻&#xff0c;但go run是我最喜欢的 Go 语言特性。想要运行你的代码&#xff1f;只需go run main.go。它是如此简单&#xff0c;我可以告诉母亲这个命令&#xff0c;她会立即理解。就像 Go 语言的大部分功能一样&…

vue 部署后修改配置文件(接口IP)

近期&#xff0c;有一个项目&#xff0c;运维在部署的时候&#xff0c;接口ip还没有确定&#xff0c;而且ip后面的路径一直有变动&#xff0c;导致我这里一天打包至少四五次才行&#xff0c;很麻烦&#xff0c;然后看了下有没有打包后修改配置文件修改接口ip的方法&#xff0c;…

自定义View中的ListView和ScrollView嵌套的问题

当我们在使用到ScrollView和ListView的时候可能会出现显示不全的问题。那我们可以进行以下分析 ScrollView在测量子布局的时候会用UNSPECIFIED。通过源码观察&#xff0c; 在ScrollView的onMeasure方法中 Overrideprotected void onMeasure(int widthMeasureSpec, int heightMe…

AI对话系统app开源

支持对接gpt&#xff0c;阿里云&#xff0c;腾讯云 具体看截图 后端环境&#xff1a;PHP7.4MySQL5.6 软件&#xff1a;uniapp 废话不多说直接上抗揍云链接&#xff1a; https://mny.lanzout.com/iKFRY1o1zusf 部署教程请看源码内的【使用教程】文档 欢迎各位转载该帖/源码

webrtc

stun服务 阿里云服务器安全组添加端口开放 webrtc-streamer视屏流服务器搭建 - 简书

Dockerfile(1) - FROM 指令详解

FROM 指明当前的镜像基于哪个镜像构建dockerfile 必须以 FROM 开头&#xff0c;除了 ARG 命令可以在 FROM 前面 FROM [--platform<platform>] <image> [AS <name>]FROM [--platform<platform>] <image>[:<tag>] [AS <name>]FROM […

naive-ui-admin 表格去掉工具栏toolbar

使用naive-ui-admin的时候&#xff0c;有时候不需要显示工具栏&#xff0c;工具栏太占地方了。 1.在src/components/Table/src/props.ts 里面添加属性 showToolbar 默认显示&#xff0c;在不需要的地方传false。也可以默认不显示 &#xff0c;这个根据需求来。 2.在src/compo…