算法系列--递归,回溯,剪枝的综合应用(1)

news/2024/6/24 8:06:31/文章来源:https://blog.csdn.net/Mylvzi/article/details/137054317

💕"对相爱的人来说,对方的心意,才是最好的房子。"💕
作者:Lvzi
文章主要内容:算法系列–递归,回溯,剪枝的综合应用(1)
在这里插入图片描述

大家好,今天为大家带来的是算法系列--递归,回溯,剪枝的综合应用(1)

1.全排列(重点)

链接:
https://leetcode.cn/problems/permutations/description/
在这里插入图片描述

分析:

1.画出决策树

所谓的决策树就是我们小时候学排列画的树状图,通过一个树枚举出所有的情况
在这里插入图片描述
画出决策树之后,分析每一层干的事情是否相同(一般都是相同的),对于本题,每一层干的事可以总结为

  • 枚举出所有符合条件的排列情况

注意:决策树画的越详细越好(包括所有不符合条件的情况也画出来),有助于我们后面设计代码

2.设计代码

设计代码主要从两个方面考虑

  1. 全局变量
  2. dfs函数

1.全局变量

模拟决策的过程,想想需要哪些变量,首先题目要求的返回值是一个二维数组,所以需要设计一个ret作为返回值,当我们在枚举出所有的情况时,要考虑到枚举的数字是否被使用,如果被使用就不能被枚举,所以要标记搜索路径上数字的使用情况,所以要创建一个布尔类型的数组,接着当我们走到叶子结点时,需要保存当前排列的情况,一共就三个数字,所以需要使用一个数组进行保存,接着当从叶子结点向上返回时,我们需要舍弃掉数组中最后一个数字,这个操作比较简单,可以直接对数组进行变动即可

  • List<List> ret: 最后的返回值,用于记录所有排列情况
  • List path: 用于记录每一次dfs的结果
  • boolean[] check : 用于标记搜索过程中数字的使用情况

2.dfs函数

和递归相同,dfs函数的设计我们只需要关注某一个子问题的具体操作即可

把数组中所有的数都枚举一遍,只要没有用过,就添加到path后面

3.细节问题

  • 剪枝:在check中被标记为true,就进行剪枝

  • 回溯:如图
    在这里插入图片描述

  • 递归出口:当path中元素的数目和nums中元素的数目相同时,递归结束,将path中的所有元素添加到ret之中

4.代码实现

class Solution {// 全局变量List<List<Integer>> ret;// 返回值List<Integer> path;// 记录搜索路径boolean[] check;// 标记是否被使用过public List<List<Integer>> permute(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];dfs(nums);return ret;}public void dfs(int[] nums) {// 递归出口if(nums.length == path.size()) {ret.add(new ArrayList<>(path));return;}// 函数体for(int i = 0; i < nums.length; i++) {if(check[i] == false) {path.add(nums[i]);check[i] = true;dfs(nums);// 回溯check[i] = false;path.remove(path.size() - 1);}}}
}

为什么不是ret.add(path);

在这里插入图片描述

2.⼦集

链接:
https://leetcode.cn/problems/subsets/description/

分析:
画决策树:

根据定义选或者不选当前数
在这里插入图片描述

每一层都在干啥
分别枚举出选当前数字选和不选当前数的所有情况

设计代码:

全局变量:模拟整个过程,需要两个变量

  • ret:接收每次搜索的结果,是最终的返回值
  • path: 表示搜索路径的结果

dfs: 需要一个数组和当前的位置(下标),因为我需要知道当前的数是谁

细节问题:

  • 剪枝:不需要
  • 回溯:只有当选择选当前数的情况时,在返回的时候需要删除这个数
  • 递归出口:当pos走到n.length时表示数组遍历完毕,结束递归,将path添加进ret之中

代码:

class Solution {// 全局变量List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs(nums,0);return ret;}public void dfs(int[] nums,int pos) {// 递归出口if(pos == nums.length) {ret.add(new ArrayList<>(path));return;}// 选path.add(nums[pos]);dfs(nums,pos + 1);path.remove(path.size() - 1);// 回溯// 不选dfs(nums,pos + 1);}
}

这种决策树的遍历类似于二叉树遍历中的后序遍历

第二种决策树

在这里插入图片描述

以当前位置的值为起始位置,枚举出后面所有的数字的情况

class Solution {// 全局变量List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs(nums,0);return ret;}public void dfs(int[] nums,int pos) {// 这个遍历类似于前序遍历  根左右ret.add(new ArrayList<>(path));// 刚进来的时候path为空 空集也是子集的一种// 从当前位置一直遍历到结束for(int i = pos; i < nums.length; i++) {path.add(nums[i]);dfs(nums,i+1);path.remove(path.size() - 1);// 回溯}}
}

这种遍历的方式类似于二叉树遍历中的前序遍历,先打印根节点的值,再去遍历左右子树

总结:

  1. 画出具体详细的决策树,模拟每一步都是在干啥,明确操作
  2. 设计代码,具体来说是要设计出需要的全局变量和dfs,设计dfs和我们之前递归过程中设计函数头,函数体,递归出口一样,这不过这里的逻辑会更加的复杂一点
  3. 注意细节问题:主要从两个方面考虑
    • 剪枝
    • 回溯

3.找出所有⼦集的异或总和再求和

链接:
https://leetcode.cn/problems/sum-of-all-subset-xor-totals/

分析:
在这里插入图片描述

代码:

class Solution {// 全局变量int ret;int path;public int subsetXORSum(int[] nums) {dfs(nums,0);return ret;}public void dfs(int[] nums,int pos) {ret += path;for(int i = pos; i < nums.length; i++) {path ^= nums[i];dfs(nums,i + 1);// 递归下一个位置path ^= nums[i];// 回溯}}
}

注意这里面利用了^运算的性质,a ^ a = 0

还是那句话,画出决策树一切都好办!!!

四.全排列II

链接:
https://leetcode.cn/problems/permutations-ii/

分析:

相较于全排列I多了个限制条件不能有重复的组合出现,那么只需分析出所有的不合法的情况即可
1.

  1. 同一层中(同一位置比如选择第一个位置的数),不能选择重复的数字
  2. 和全排列I一样,不能选择已经使用过的数字

对于2的处理和全排列I的处理方式相同,使用一个布尔类型的check数组标记即可,对于1需要判断出 不合法的数据,首先要和前面的数字相同nums[i] == nums[i - 1],i不能越界i != 0,其次上述两个条件还不能完全判定出是不合法的数据,还必须要保证前一个数字是同一层的,check[i - 1] == false

总结来说就是:

  1. nums[i] == nums[i-1] && 在同一层–>不合法数据–>不能dfs
  2. nums[i] == nums[i-1] && 不在同一层–>合法数据–>能dfs

此外,为了保证相同的数据是紧挨着的,还需要进行排序

代码:

class Solution {// 全局变量List<List<Integer>> ret;// 返回值List<Integer> path;// 记录搜索路径boolean[] check;// 标记是否被使用过public List<List<Integer>> permuteUnique(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];Arrays.sort(nums);dfs(nums);return ret;}public void dfs(int[] nums) {// 递归出口if(path.size() == nums.length) {ret.add(new ArrayList<>(path));return;}// 函数体for(int i = 0; i < nums.length; i++) {// 剪枝  不合法的数据if(check[i] == true || (i != 0 && nums[i] == nums[i - 1] && check[i - 1] == false)) {continue;}path.add(nums[i]);check[i] = true;dfs(nums);// 回溯check[i] = false;path.remove(path.size() - 1);}}
}

5.电话号码的字⺟组合

链接:
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
分析:

每一层所做的事情:

  • 枚举出当前数字对应的字符串中所有的字符

设计代码:
1.全局变量
ret:返回值
path
string[] map:映射关系

2.dfs(digits,pos)
pos表示digits中字符的下标
递归出口:
走到最后一个节点的位置

回溯:
删除最后添加的数字

剪枝:无

在这里插入图片描述
代码:

class Solution {List<String> ret;// 返回值StringBuffer path;// 记录搜索路径String[] map= {"","","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};// 建立映射关系public List<String> letterCombinations(String digits) {ret = new ArrayList<>();path = new StringBuffer();if(digits.length() == 0) return ret;// 处理为空的情况dfs(digits,0);return ret;}private void dfs(String digits, int pos) {if(pos == digits.length()) {// 递归出口ret.add(path.toString());return;}String s = map[digits.charAt(pos) - '0'];// 获取当前层的字符串for(int i = 0; i < s.length(); i++) {path.append(s.charAt(i));// 追加字符dfs(digits, pos + 1);path.deleteCharAt(path.length() - 1);// 回溯}}
}

dfs是往下,是递归,每一层是要做的事情是子问题

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

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

相关文章

Higress 基于自定义插件访问 Redis

作者&#xff1a;钰诚 简介 基于 wasm 机制&#xff0c;Higress 提供了优秀的可扩展性&#xff0c;用户可以基于 Go/C/Rust 编写 wasm 插件&#xff0c;自定义请求处理逻辑&#xff0c;满足用户的个性化需求&#xff0c;目前插件已经支持 redis 调用&#xff0c;使得用户能够…

蓝桥杯-岛屿个数

solution 数1的块数题&#xff0c;加了内岛不计入的小限制&#xff0c;以及输入数据间没有空格&#xff0c;不是矩阵形式的整数输入。 判断是否是子岛屿&#xff1a;如果该岛屿有边缘部分或者可以通过外海走到边缘部分说明不是子岛屿 #include<iostream> #include<…

Django创建多app应用

目录 1. 引言 2. 多app创建的两种方式 2.1 多个app结构 2.2 单个apps多个app 3. 最后 1. 引言 在平常业务开发中&#xff0c;我们遇到的功能可能会有很多&#xff0c;单个app的应用可能无法满足我们 这个时候&#xff0c;我们就需要多app应用&#xff0c;例如&#xff1a…

基于SSM+Jsp+Mysql的固定资产管理系统

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

在线考试系统的设计与实现|Springboot+ Mysql+Java+ B/S结构(可运行源码+数据库+设计文档)

本项目包含可运行源码数据库LW&#xff0c;文末可获取本项目的所有资料。 推荐阅读300套最新项目持续更新中..... 最新ssmjava项目文档视频演示可运行源码分享 最新jspjava项目文档视频演示可运行源码分享 最新Spring Boot项目文档视频演示可运行源码分享 2024年56套包含ja…

Linux 系统 安装redis

Linux 系统 安装redis 下载redis安装包&#xff0c;并上传到服务器指定安装目录 一、解压安装包并安装 1、 tar xzf redis-4.0.9.tar.gz 2、先通过gcc -v是否有安装gcc&#xff0c;如果没有安装 统一安装Gcc rpm -Uvh *.rpm --nodeps --force 3、cd /usr/local/red…

前端之HTML——网页的骨架!!

目录 一、HTML介绍 二、HTML标签 &#xff08;一&#xff09;基础标签 &#xff08;二&#xff09;其他标签 2.1 6个常用标签 2.2 8个文本标签 2.3 6个列表标签 2.4 4个表格标签 2.5 4个媒体标签 2.6 1个嵌入标签 2.7 …

HBuilder uniapp发行h5遇到报错:此应用 DCloud appid 为 __UNI__95950AD ,您不是这个应用的项目成员。

uniapp打包遇到不是项目成员问题&#xff0c;如下截图&#xff1a; 解决方法如下&#xff1a; 打开项目的mainfest.json文件&#xff0c;在AppID位置点击重新获取&#xff0c;获取后重新点发行打包即可 另遇到HBuilder账号认证问题&#xff0c;如公司wifi打不开认证地址&#…

一文入门Ubuntu22

目录 1.安装Ubuntu22 2.常用目录 3.常用指令 1.sudo 超级用户权限运行命令 2.ls 罗列当前文件信息 3.文件目录相关&#xff1a; 1.cd改变工作路径&#xff1a; 2.pwd 3.创建目录和文件&#xff1a; 4.which 5.ps 6.kill 7.ping 4.用户相关 5.ssh与scp 6.服务相关…

【氮化镓】GaN器件中关态应力诱导的损伤定位

概括总结&#xff1a; 这项研究通过低频1/f噪声测量方法&#xff0c;探究了在关态&#xff08;OFF-state&#xff09;应力作用下&#xff0c;AlGaN/GaN高电子迁移率晶体管&#xff08;HEMTs&#xff09;中由应力引起的损伤的定位。研究中结合了电致发光&#xff08;EL&#xf…

谈谈MVCC机制

在MySQL中&#xff0c;MVCC&#xff08;多版本并发控制&#xff09;是InnoDB存储引擎使用的并发控制机制。它提供对数据的并发访问&#xff0c;并确保多用户环境中数据的一致性和隔离性。 InnoDB通过“Undo log”存储每条记录的多个版本&#xff0c;提供历史记录供读取&#x…

Spring Boot项目启动速度优化

1、配置自动配置排除列表&#xff0c;减少启动自动配置扫描&#xff0c;配置项spring.autoconfigure.exclude 2、启动类添加索引注解Indexed&#xff0c;去除启动过程中 Components 的扫描步骤&#xff0c;直接从索引文件读取。 import org.springframework.stereotype.lndexe…

自定义 Unity Scene 的界面工具

介绍 文档中会进行SceneView的自定义扩展&#xff0c;实现显示常驻GUI和添加自定义叠加层&#xff08;Custom Overlay&#xff09;。 最近项目开发用回了原生的Unity UI相关内容。对于之前常用的FairyGUI来说&#xff0c;原生的UGUI对于UI同学来讲有些不太方便。再加上这次会…

【精品方案】智慧金融大数据分析平台总体架构方案

以下是部分PPT内容&#xff0c;请您参阅。如需下载完整PPTX文件&#xff0c;请前往星球获取&#xff1a; 1.实现数据共享 通过数据平台实现数据集中&#xff0c;确保金融集团各级部门均可在保证数据隐私和安全的前提下使用数据&#xff0c;充分发挥数据作为企业重要资产的业务价…

String Encryptor custom Bean not found with name ‘jasyptStringEncryptor‘...

项目采用 spring boot 2.6.13 jasypt-spring-boot-starter 3.0.5 apollo-client 1.6.0 自定义jasyptStringEncryptor&#xff0c;服务器上启动死活报找不到bean jasyptStringEncryptor&#xff0c;采用默认的&#xff0c;密文配置项自然解密失败导致服务无法启动。 经过一…

华为云RDS for Mysql入门与配置

华为云RDS for MySQL支持混合SSD实例&#xff0c;它结合了华为云容器、本地SSD盘和高速云盘。 优势&#xff1a; 主备实例提供故障自动切换和手动切换&#xff0c;业务中断时间为秒级&#xff0c;以及异地灾难备份&#xff0c;最大程度上在出现故障的情况下保障整个数据库集群…

基于STM32的汽车防窒息系统

文章目录 基于STM32的汽车防窒息系统系统简介材料展示视频制作硬件连接原理图PCB实物图GSM模块使用GSM模块代码 SGP30模块SGP30模块代码 步进电机驱动步进电机代码 其他模块主逻辑代码 总结 基于STM32的汽车防窒息系统 系统简介 随着社会的发展目前汽车的流行&#xff0c;汽车大…

WebSocket 和 HTTP 的区别:简单易懂

在当今的数字时代&#xff0c;及时交付内容和维持用户互动已成为网络应用不可或缺的要素。这一需求催生了新的通信规范——WebSocket 和 HTTP&#xff0c;尽管两者都服务于网络通讯&#xff0c;它们之间却存在显着的差异。本篇文章旨在剖析这两种协议在应用案例、技术细节、性能…

C语言动态内存讲解+通讯录2.0

文章目录 前文malloc和freecallocrealloc枚举常量的简单说明及使用 通讯录2.0动态开辟通讯录,满了就扩容保存数据和载入数据 通讯录2.0演示推荐好用的软件 前文 本文主要介绍动态开辟的几个函数,以及改进之前的通讯录。 我们局部变量等是在栈区上开辟空间的,而我们动态开辟的空…

微信小程序开发【从入门到精通】——页面导航

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…