【递归、搜索与回溯】穷举vs暴搜vs深搜vs回溯vs剪枝

穷举vs暴搜vs深搜vs回溯vs剪枝

  • 1.全排列
  • 2.子集

在这里插入图片描述

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃

管他什么深搜、回溯还是剪枝,画出决策树就完事了~~~

1.全排列

题目链接:46. 全排列

题目描述:

在这里插入图片描述

算法原理:

其实这道题本身是一个穷举(枚举)的题,3个数你可以三层for循环,但是如果10个数,100个数呢?对于数多的显然不合适!此时我们就需要借助递归把所有情况都枚举出来。

解决回溯的步骤:

  1. 画出决策树,越详细越好!
  2. 设计代码
    全局变量
    dfs函数
    细节问题

1.画出决策树

就是在暴力枚举这道题过程中如何不重不漏的把所有情况枚举到,就是把自己的想想法按照树的样子画下来。

第一次选择可以直接选123中任何一个,接下来每次选择都是从123中选。但是此时你会发现比如第一次选1,下一次还选1就会有重复的情况,因此这个1我们是要把它剪掉的,不考虑有1的情况。第二次选择假设选择的是2,在往下选择就还是有123,但是此时剪掉的应该更多,12不能选,只能选3,所有最终这条分支就是123,同理其他也是这样选出。
在这里插入图片描述

决策树画的越详细越好,就是把每一步都画出来,这样你就会发现每一个节点干的事情都是一样的,都是枚举整个数组。无非就是一些分支被我们剪掉。当一直在干同一件事情的时候我们决策树就画成功了,因为可以改成递归的代码。

2.设计代码

1.全局变量
全局变量就看这个递归需要什么东西和以及最终要返回什么东西。

全局变量的使用仁者见仁智者见智,也可以把全局变量换成参数在递归函数中传递。看个人选择,不过还是建议使用全局变量

首先来递归要返回的二维数组,再来一个把每次选择都要记录的path。
当path.size() == nums.size() 说明已经找到一个符合的组合,此时把path放到ret里,然后回溯 ,注意要 恢复现场。在说这个之前我们要说一说这个剪枝的事情。

在这里插入图片描述

剪枝怎么解决?就是如果避免下一次选择重复的数字。
此时我们也需要一个数组,弄一个bool 类型的数组。来判断一下该条路径下的数是否已经被使用过了。bool数组中记录nums数组中的数字是否已经被使用过。
check[0] 对应 1, check[1] 对应 2 , check[2] 对应3,check初始化都为false,只有对应数字被使用了 check[i]=true,说明这个数字已经被使用过了,下一次就不要选这个数字了。

在这里插入图片描述

2.dfs函数
仅需关心,某一个节点在干什么事情。

3.细节问题
回溯
当我要回去的时候,需要把这个3干掉,就是向上回去把path最后一个元素干掉,但是别忘记了check也是一个全局的, 你用3的时候会把check对应位置置为true,那你向上返回这个3你都不用了,是不是要把3复原啊。

  1. 干掉 path 最后一个元素
  2. 修改 check 数组
    在这里插入图片描述

剪枝
这里前面说过。

递归出口
遇到叶子节点的时候,直接添加结果。不用在到空了。

这样的题一定是决策树画出来是最重要的,第二步设计代码你想到哪一点写那一点都可以。

class Solution {vector<vector<int>> ret;vector<int> path;bool check[7]={false};
public:vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}void dfs(vector<int>& nums){if(path.size() == nums.size()){ret.push_back(path);//返回之前可以 回溯 --> 恢复现场return;}for(int i=0;i<nums.size();++i){//剪枝if(check[i] == false){path.push_back(nums[i]);check[i]=true;dfs(nums);//返回之后也可以 回溯 ---> 恢复现场  ,建立返回之后check[i]=false;path.pop_back();      }}}
};

注意一定是决策树越详细后面代码设计越轻松,代码设计考虑一下全局变量、dfs函数、细节问题。

2.子集

题目链接:78. 子集

题目描述:

在这里插入图片描述

算法原理:

这里我们采用两种策略来解决这个问题,虽然是两种策略,但都是深搜,所以我们的思考方式是一样的。

解法一:

  1. 画出决策树
  2. 设计代码
    全局变量
    dfs
    细节:回溯、剪枝、递归出口

首先画决策树,我们想想如何能够把所有子集不重不漏全部枚举出来。我们从子集定义出发,子集是这个数组里面选or不选某些数形成新的集合就是它的子集。因此我们就单独盯着数组中每个数字考虑选or不选来画出我们的决策树。
在这里插入图片描述
此时所有叶子节点就是数组所有不重复的子集。

现在我们仅需把这颗决策树转换成代码就可以了。之前的题无非就是直接把树画好给我们了,现在是要我们自己画一颗树。

既然叶子节点是我们的结果,因此我们需要两个全局变量,一个二维数组ret,一个一维数组path,path把每次选or不选路径记录下来,然后ret把path记录下来。这道题我们并不需要剪枝。

dfs函数我们就盯着某一个位置在干什么。比如绿圈的位置,因为上面已经选过了,所以要需要考虑这一次的数选or不选,所以dfs不仅要这个nums,还要告诉我你当前选到了那个位置,dfs(nums,pos)
就加入到path里,然后dfs(nums,pos+1)下一层
不选直接 dfs(nums,pos+1)下一层
在这里插入图片描述
细节问题:回溯要恢复现场,因此我们在选的这条路径在递归返回之后把path最后一个位置pop掉,剪枝我们这里没有。递归出口当pos==nums.size()的时候,把path放到ret里,然后返回即可。

class Solution {vector<vector<int>> ret;vector<int> path;
public:vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}void dfs(vector<int>& nums,int pos){if(pos == nums.size()){ret.push_back(path);return;}// 选path.push_back(nums[pos]);dfs(nums,pos+1);path.pop_back(); // 恢复现场// 不选dfs(nums,pos+1);}
};

解法二:
也是上面一样的步骤,

  1. 画出决策树
  2. 设计代码
    全局变量
    dfs
    细节:回溯、剪枝、递归出口

这里我们换一种思考方式,当我们选的子集是没有元素、只有一个元素、只有两个元素、只有三个元素等等。前面的是盯着某一个数选or不选,现在我们直接看看最终要的子集要么没有,要么一个元素,要么两个元素,要么三个元素等等,从小到大去选。并且每次是从这个被选的数的后面再次选。并且每一个节点都是我们想要的结果。

在这里插入图片描述
你会发现我们这种解法比上面少了很多没有必要的情况。

全局变量还是上面那两个,dfs函数 从当前节点位置开始向后枚举,所以也要知道当前位置 dfs(nums,pos)。for(int i=pos;i<nums.size();++i) 把路径上的节点放入path,然后递归到下一层dfs(nums,pos+1),当递归返回收把path最后一个位置pop掉。 回溯也要恢复现场,把path最后一个位置pop掉,这里我们不用剪枝递归出口,每次进入递归函数后先把path先放到ret里。然后也不需要出口,循环条件不满足就出去了。

class Solution {vector<vector<int>> ret;vector<int> path;
public:vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}void dfs(vector<int>& nums,int pos){ret.push_back(path);for(int i=pos;i<nums.size();++i){path.push_back(nums[i]);dfs(nums,i+1);path.pop_back(); // 恢复现场}}
};

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

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

相关文章

【Java】解决Java报错:NoClassDefFoundError

文章目录 引言1. 错误详解2. 常见的出错场景2.1 类路径配置错误2.2 依赖库缺失2.3 类文件被删除或损坏2.4 类加载器问题 3. 解决方案3.1 检查类路径配置3.2 检查依赖库3.3 检查类文件3.4 调试类加载器问题 4. 预防措施4.1 使用构建工具管理依赖4.2 定期进行构建和测试4.3 使用I…

【Unity+AI01】在Unity中调用DeepSeek大模型!实现AI对话功能!

要在Unity中调用DeepSeek的API并实现用户输入文本后返回对话的功能&#xff0c;你需要遵循以下步骤&#xff1a; 获取API密钥&#xff1a; 首先&#xff0c;你需要从DeepSeek获取API密钥。这通常涉及到注册账户&#xff0c;并可能需要订阅相应的服务。 集成HTTP请求库&#xf…

【APP移动端自动化测试】第一节.环境配置和adb调试工具

文章目录 前言一、Java环境搭建二、AndroidSDK环境搭建三、Android模拟器安装四、adb调试工具基本介绍 4.1 adb构成和基本原理 4.2 adb获取包名&#xff0c;界面名 4.3 adb文件传输 4.4 adb获取app启动时间 4.5 adb获取手机日志 4.6 adb其他有关…

python的resample()函数

介绍 在Python中,resample()函数是一个常用的工具,用于对时间序列数据进行重新采样。这个函数可以将时间序列数据从一个频率转换为另一个频率,比如将每天的数据转换为每月的数据。在本教程中,我将向你展示如何使用resample()函数,并解释每个步骤的具体含义。 整体流程 首先…

独具魅力的 App UI 风格才能称之为优秀

独具特色的App UI 长什么样&#xff01;看这里

Java案例:找素数

文章目录 题目问题反思代码改进 题目 找素数 判断101-200之间有多少个素数&#xff0c;并输出所有素数 只需要除到 n/2 即可。 算数平方根。&#xff08;j*j<i&#xff09;实际上可以更高效地只除到Math.sqrt(n)&#xff08;或者说Math.sqrt(n) 1为了处理整数除法&#xf…

Master-Worker 架构的灰度发布难题

作者&#xff1a;石超 一、前言 Master-Worker 架构是成熟的分布式系统设计模式&#xff0c;具有集中控制、资源利用率高、容错简单等优点。我们数据中心内的几乎所有分布式系统都采用了这样的架构。 &#xfeff; 我们曾经发生过级联故障&#xff0c;造成了整个集群范围的服…

文件IOoooo

1.1 文件路径 文件路径分为两种&#xff1a; 1、绝对路径&#xff1a;以C:、D:等盘符开头的&#xff0c;就是我们所说的绝对路径&#xff0c;根据它可以直接找到文件的具体位置。 2、相对路径&#xff1a;需要先指定一个目录作为基准目录&#xff0c;从基准目录出发&#xf…

SpringSecurity入门(四)

18、权限管理/授权 18.1、针对url配置 配置SecurityConfig package com.wanqi.config;import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration; import org.springframework.security.config.annotation.web.bu…

(免费领源码)基于 node.js#vue#mysql的网上游戏商城35112-计算机毕业设计项目选题推荐

摘 要 本论文主要论述了如何使用node.js语言开发一个基于vue的网上游戏商城&#xff0c;本系统将严格按照软件开发流程进行各个阶段的工作&#xff0c;本系统采用的数据库是Mysql&#xff0c;使用node.js的koa技术技术构建的一个管理系统&#xff0c;实现了本系统的全部功能。在…

云计算-期末复习题-选择/判断/填空/简答(1)

目录 填空题/简答题 单选题 多选题 判断题 云计算期末复习部分练习题&#xff0c;下一章会补全。祝大家好好复习&#xff0c;顺利通过课程。 填空题/简答题 >保障云基本安全的对策包括&#xff08;&#xff09;、&#xff08;&#xff09;和&#xff08;&#xff09; &…

Linux:桌面系统中的文件后缀和类型

相关阅读 Linuxhttps://blog.csdn.net/weixin_45791458/category_12234591.html?spm1001.2014.3001.5482 Linux中的文件后缀与Windows系统有些不同&#xff0c;因为其似乎没有很重要&#xff0c;一个文件是否可执行对后缀没有要求。但是&#xff0c;后缀依然可以用于表示文件…

机器学习笔记:label smoothing

在传统的分类任务中&#xff0c;我们通常使用硬标签&#xff08;hard labels&#xff09; 即如果一个样本属于某个类别&#xff0c;其对应的标签就是一个全0的向量&#xff0c;除了表示这个类别的位置为1。例如&#xff0c;在一个3类分类任务中&#xff0c;某个样本的标签可能是…

实用软件分享---简单菜谱 0.3版本 几千种美食(安卓)

专栏介绍:本专栏主要分享一些实用的软件(Po Jie版); 声明1:软件不保证时效性;只能保证在写本文时,该软件是可用的;不保证后续时间该软件能一直正常运行;不保证没有bug;如果软件不可用了,我知道后会第一时间在题目上注明(已失效)。介意者请勿订阅。 声明2:本专栏的…

【Python】 装饰器,可不只是装饰作用!

Python 是一种高级编程语言&#xff0c;以其清晰的语法和代码可读性而著称。在 Python 中&#xff0c;“at” 符号&#xff08;&#xff09;通常被称为装饰器&#xff08;Decorator&#xff09;的语法符号。装饰器是一种设计模式&#xff0c;用于修改或增强函数、方法或类的行为…

Spring Cloud Gateway详解

一、前言Spring Cloud Gateway的作用 路由转发&#xff1a; Spring Cloud Gateway作为微服务架构中的网关服务&#xff0c;充当所有请求的入口。它可以根据请求的路径、Host、Header、请求参数等多种条件进行路由&#xff0c;将请求转发到相应的微服务实例。路由信息由ID、目的…

2024蓝桥杯初赛决赛pwn题全解

蓝桥杯初赛决赛pwn题解 初赛第一题第二题 决赛getting_startedbabyheap 初赛 第一题 有system函数&#xff0c;并且能在bss上读入字符 而且存在栈溢出&#xff0c;只要过掉check函数即可 check函数中&#xff0c;主要是对system常规获取权限的参数&#xff0c;进行了过滤&…

git版本控制工具常用命令

一、本地仓库管理 push 向远程推送代码 pulll 拉取代码 二、远程仓库管理 三、分支操作 本地主分支master 远程主分支main head指向当前分支 查看&#xff1a;git branch 创建分支: git branch 名字 切换分支&#xff1a;git checkout 名字 合并分支&#xff1a;git…

VS2019创建c++动态链接库dll与调用方法

VS2019创建c动态链接库dll与调用方法 1.点击文件-》新建-》项目&#xff0c;输入dll,选择具有导出项的(DLL)动态链接库 2.输入一个文件名&#xff1a;dll2 头文件.h 3.添加加减法函数&#xff1a; // 下列 ifdef 块是创建使从 DLL 导出更简单的 // 宏的标准方法。此 DLL 中的…

爱普生SMD3225贴片晶振升级版TSX-3225

爱普生有一款外形尺寸3.2*2.5mm的无源贴片晶振&#xff0c;型号TSX-3225&#xff0c;也是非常直观的能从型号分辨其封装尺寸大小的&#xff0c;被广泛应用于便携式的无线传输设备&#xff0c;同时&#xff0c;这也是一款非常成熟的产品&#xff0c;毕竟SMD3225封装是目前市场主…