当前位置: 首页 > news >正文

系统学习算法:专题九 穷举vs暴搜vs深搜vs回溯vs剪枝

其中标题的深搜,回溯,剪枝我们之前专题都已经有过学习和了解,这里多了两个穷举和暴搜,其实意思都差不多,穷举就是穷尽力气将所有情况都列举出来,暴搜就是暴力地去一个一个情况搜索,所以就是全部遍历的意思

而实现全部遍历之前,我们需要将所有情况以树状来大致画出来,这棵树就叫做决策树,也就是在上学时数学的某一小节学过的决策树,如下图

将123的所有排列情况列举出来

 就是填空一样,将不同情况画出树

那么这就涉及深搜,回溯和剪枝,只不过之前是二叉树,现在变为了多叉树

但过程都大致差不多,只要画出清晰的决策树,就可以将决策转化为代码

题目一:

 思路:

先画出决策树,就是上面我们举例的决策树

 其中我们需要一个全局变量二维数组ret来存储所有排列的情况,也是我们要返回的结果集

然后我们还需要一个全局变量一维数组path来记录其中一次的排列情况,也就做其中一条路径

然后还需要一个全局变量布尔数组来记录数字的使用情况,没使用过为false,使用过为true

然后我们就开始遍历,但注意我们是深搜dfs,不是宽搜bfs,即虽然画决策树的时候是先填第一个空1,2,3,但实际遍历我们是填1之后,将1对应的所有情况都搜索完之后,再回到2这里,即dfs的搜索顺序,而不是bfs

结束条件也很好想,就是当path的元素个数等于数组元素个数就说明排完了,那么就将该path填入结果集ret中(但注意path要重新new一个出来,不然传的是地址,后续搜索其他排列时,对path修改会连带着修改之前填入的path,即所有path都指向同一个path),填入之后还可以用剪枝稍微优化一下,因为填就说明全部元素用到了,后面的其他元素都没必要再搜索了,因为结果都是不可能的

而往下遍历的时候都是for循环数组的所有元素,调用布尔数组,如果该元素用过就不加,没用过就加,然后继续往下搜索

碰到结束条件后就该回溯,那么就该修改布尔数组和path,将该数的布尔值修改为false,再删除path的最后一个元素

最后返回ret即可

代码:

class Solution {//保存所有全排列的结果集List<List<Integer>> ret=new ArrayList<>();//用于判断该数字是否使用过boolean[] check;//其中一个排列List<Integer> path=new ArrayList<>();public void dfs(int[] nums){//如果排列元素的个数等于数组元素的个数,说明排完了if(path.size()==nums.length){//添加该排列情况(要new一个新的,不然就是传地址)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);}}}public List<List<Integer>> permute(int[] nums) { check=new boolean[nums.length];dfs(nums);return ret;}
}

题目二:

思路:

还是先画决策树,不同的决策树画法有不同的代码,但只要决策树画对,代码实现了就一定是对的

 求子集大概有两种决策树画法

解法1:

 这种决策树画法就是遍历数组,每遍历一个就出现两种决策,选或者不选,最后叶子结点就是所有的子集

代码1:

class Solution {//结果集List<List<Integer>> ret = new ArrayList<>();//其中一个子集List<Integer> path = new ArrayList<>();//k表示到数组的哪一个元素了public void dfs(int[] nums, int k) {//如果遍历完数组了if(k==nums.length){ret.add(new ArrayList<>(path));return;}//选path.add(nums[k]);dfs(nums,k+1);//恢复现场path.remove(path.size()-1);//不选dfs(nums,k+1);}public List<List<Integer>> subsets(int[] nums) {dfs(nums, 0);return ret;}
}

解法2:

这种决策树的画法就是以子集中的元素个数来进行决策,一开始为0个,也就是空集,然后为1个,就是1,2,3,再然后为2个……其中是否选择以当前元素的位置为标准,比如1就找后面的2,3,而2就找后面的3,而3就没得找了,这样子就能避免出现重复的情况

则每一个结点都是一个结果,所以每次dfs的时候都要添加

代码2:

class Solution {//结果集List<List<Integer>> ret = new ArrayList<>();//其中一个子集List<Integer> path = new ArrayList<>();//k表示到数组的哪一个元素了public void dfs(int[] nums, int k) {//先添加ret.add(new ArrayList<Integer>(path));//从当前元素开始往后遍历for (int i = k; i < nums.length; i++) {//添加该元素path.add(nums[i]);//再次基础上往后遍历dfs(nums, i + 1);//恢复现场path.remove(path.size() - 1);}}public List<List<Integer>> subsets(int[] nums) {dfs(nums, 0);return ret;}
}

但综合来看,肯定是解法2更优,因为每一个结点都是结果,没有多余的浪费,而解法1则全部枚举了出来,但最后只选择了叶子结点,非叶子结点就多余了

总结:

解决全排列,集合这种需要枚举许多情况并回溯的,先画出决策树,决策树不唯一,只要思路是对的,通过代码来实现,其中需要注意回溯后要恢复现场,最后就是正确的

相关文章:

系统学习算法:专题九 穷举vs暴搜vs深搜vs回溯vs剪枝

其中标题的深搜&#xff0c;回溯&#xff0c;剪枝我们之前专题都已经有过学习和了解&#xff0c;这里多了两个穷举和暴搜&#xff0c;其实意思都差不多&#xff0c;穷举就是穷尽力气将所有情况都列举出来&#xff0c;暴搜就是暴力地去一个一个情况搜索&#xff0c;所以就是全部…...

解决 Pandas DataFrame 索引错误:KeyError:0

在使用 Pandas 处理数据时&#xff0c;KeyError 是一个常见的问题&#xff0c;尤其是在尝试通过索引访问数据时。本文将通过一个实际案例&#xff08;使用SKLearn中的MINIST数据集为例&#xff09;&#xff0c;详细分析 KeyError 的原因&#xff0c;并提供解决方法。 1 问题背…...

deepseek的对话风格

概述 deepseek的对话风格&#xff0c;比一般的模型的回答多了思考过程&#xff0c;这是它比较可爱的地方&#xff0c;模型的回答有了思考过程&#xff0c;对用户而言大模型的回答不完全是一个黑盒。 deepseek的对话风格 train_prompt_style """Below is an…...

制造业设备状态监控与生产优化实战:基于SQL的序列分析与状态机建模

目录 1. 背景与挑战 2. 数据建模与采集 2.1 数据表设计 设备状态表(记录设备实时状态变更)...

Javaweb学习之Mysql(Day5)

(一)Mysql概述 (1)MYSQL通用语法 SQL语句可以单行或多行书写,以分号结尾。 SQL语句可以使用空格/缩进来增强语句的可读性(即,空格和缩进不影响代码的执行)。 MySQL数据库的SQL语句不区分大小写。 注释: 1. 单行注释: -- 注释内容 或 # 注释内容 (MySQL 特有 …...

C++ Primer 迭代器

欢迎阅读我的 【CPrimer】专栏 专栏简介&#xff1a;本专栏主要面向C初学者&#xff0c;解释C的一些基本概念和基础语言特性&#xff0c;涉及C标准库的用法&#xff0c;面向对象特性&#xff0c;泛型特性高级用法。通过使用标准库中定义的抽象设施&#xff0c;使你更加适应高级…...

Java的String与StringBuilder例题

​​ package com.jiachen.StringBuilderDemo1;import java.util.Scanner;public class Exercise2 {public static void main(String[] args) {Scanner scanner new Scanner(System.in);String s scanner.nextLine().trim(); // 读取输入并去除前后空格String result;// 根据…...

Vue.js 如何选择合适的组件库

Vue.js 如何选择合适的组件库 大家在开发 Vue.js 项目的时候&#xff0c;都会面临一个问题&#xff1a;我该选择哪个组件库&#xff1f; 市面上有很多优秀的 Vue 组件库&#xff0c;比如 Element Plus、Vuetify、Quasar 等&#xff0c;它们各有特点。选择合适的组件库&#xf…...

github下载失败网页打开失败 若你已经知道github地址如何cmd下载

直接打开命令行&#xff1a; winr cmd 输入&#xff1a;git clone 地址 eg&#xff1a;git clone https://github.com/akospasztor/stm32f103-dfu-bootloader...

排序算法--计数排序

统计每个元素出现的次数&#xff0c;直接计算元素在有序序列中的位置&#xff0c;要求数据是整数且范围有限。适用于数据为小范围整数&#xff08;如年龄、成绩&#xff09;&#xff0c;数据重复率较高时效率更优。可用于小范围整数排序、基数排序的底层排序(作为基数排序的稳定…...

[特殊字符]const在函数前后的作用详解(附经典案例)

理解const在函数前后的位置差异&#xff0c;是掌握C精髓的重要一步。下面用几个超形象的例子&#xff0c;带你彻底搞懂这个知识点&#xff01; 情况1&#xff1a;const在函数后面&#xff08;成员函数限定符&#xff09; 作用&#xff1a;承诺这个成员函数不会修改对象的状态&…...

【字节青训营-7】:初探 Kitex 字节微服务框架(使用ETCD进行服务注册与发现)

本文目录 一、Kitex概述二、第一个Kitex应用三、IDL四、服务注册与发现 一、Kitex概述 长话短说&#xff0c;就是字节跳动内部的 Golang 微服务 RPC 框架&#xff0c;具有高性能、强可扩展的特点&#xff0c;在字节内部已广泛使用。 如果对微服务性能有要求&#xff0c;又希望…...

给AI用工具的能力——Agent

ReAct框架&#xff1a; Reason Action&#xff0c;推理与行动结合 可以借助思维链&#xff0c;用小样本提示展示给模型一个ReAct框架 推理&#xff1a;针对问题或上一步观察的思考 行动&#xff1a;基于推理&#xff0c;与外部环境的一些交互&#xff08;调用外部工具&…...

Jupyter Lab的使用

Lab与Notebook的区别: Jupyter Lab和Jupyter notebook有什么区别&#xff0c;这里找到一篇博客不过我没细看&#xff0c; Jupyter Lab和Jupyter Notebook的区别 - codersgl - 博客园 使用起来Lab就是一个更齐全、功能更高级的notebook&#xff0c; 启用滚动输出: 有时候一个…...

【从零开始的LeetCode-算法】922. 按奇偶排序数组 II

给定一个非负整数数组 nums&#xff0c; nums 中一半整数是 奇数 &#xff0c;一半整数是 偶数 。 对数组进行排序&#xff0c;以便当 nums[i] 为奇数时&#xff0c;i 也是 奇数 &#xff1b;当 nums[i] 为偶数时&#xff0c; i 也是 偶数 。 你可以返回 任何满足上述条件的…...

RabbitMQ深度探索:前置知识

消息中间件&#xff1a; 消息中间件基于队列模式实现异步 / 同步传输数据作用&#xff1a;可以实现支撑高并发、异步解耦、流量削峰、降低耦合 传统的 HTTP 请求存在的缺点&#xff1a; HTTP 请求基于响应的模型&#xff0c;在高并发的情况下&#xff0c;客户端发送大量的请求…...

『 C++ 』中不可重写虚函数的实用案例

文章目录 框架设计&#xff1a;保障核心逻辑稳定避免误操作&#xff1a;防止逻辑混乱确保接口一致&#xff1a;库与API设计 在C编程里&#xff0c;用final关键字修饰、不允许被继承&#xff08;重写&#xff09;的虚函数其实很有用。接下来我就结合实际案例&#xff0c;给大家讲…...

Redis - String相关命令

目录 setgetmsetmgetsetnx、setex、psetexincr、incrby、decr、decrby、incrbyfloatappendgetrangesetrangestrlen字符串类型编码方式总结 Redis - String Redis存储的字符串&#xff0c;是直接按二进制方式存储&#xff0c;不会做任何编码转换&#xff0c;存的是什么&#xff…...

pytorch基于FastText实现词嵌入

FastText 是 Facebook AI Research 提出的 改进版 Word2Vec&#xff0c;可以&#xff1a; ✅ 利用 n-grams 处理未登录词 比 Word2Vec 更快、更准确 适用于中文等形态丰富的语言 完整的 PyTorch FastText 代码&#xff08;基于中文语料&#xff09;&#xff0c;包含&#xff1…...

3D人脸建模:高精度3D人脸扫描设备快速生成真人脸部3D模型

什么是3D人脸建模? 3D人脸建模&#xff0c;即借助特定技术手段&#xff0c;获取人脸三维数据&#xff0c;并构建出能精准呈现人脸形状、纹理等特征的三维模型。这一技术广泛应用于计算机视觉、人机交互、虚拟现实、影视制作等多个领域&#xff0c;为各行业都带来了前所未有的创…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...