【递归、搜索与回溯】综合练习一

综合练习一

  • 1.找出所有子集的异或总和再求和
  • 2.全排列 II
  • 3.电话号码的字母组合
  • 4.括号生成

在这里插入图片描述

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

1.找出所有子集的异或总和再求和

题目链接：1863. 找出所有子集的异或总和再求和

题目描述：

在这里插入图片描述

先找出所有子集，然后把每个子集异或的和加起来返回去。
在这里插入图片描述

算法原理：
这道题和我们上一道思路完全是一模一样，

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

因为我们有上一道题的基础，我们直接就画出决策树
在这里插入图片描述
这里我们需要两个全局变量，一个path记录到沿途每个子集的异或，然后sum负责每个字节的异或和加起来。dfs函数，还是需要一个pos记录当前异或的位置，dfs(nums,pos)，回溯利用异或的规则，两个相同的数异或为0。这里也没有剪枝， 递归出口 循环结束就是递归出口。

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

2.全排列 II

题目链接：47. 全排列 II

题目分析：

在这里插入图片描述

重复的数全排列后会有重复的结果，这道题就是要求去掉重乎之后的全排列

在这里插入图片描述

算法原理：
这道题几乎和全排列1 一模一样，我们就不在细说那些决策树怎么画，代码应该怎么写等等。这里主要就是剪枝的问题。

下面我们边画决策树变分析问题，把全排列所有不重复不漏的情况画出来，越详细越好。 我们只用关心四个位置，每个位置每次从数组中4个数选择一个树放到一个位置上就行了。只用选四次就行了。

第一次可以选第一个1、第二个1、第三个1、2，但是注意这里就存在剪枝的问题了，如果第一个位置还把第二个1和第三个1选上，此时就会存在重复问题！因为后面三个位置是从112中选的。
在这里插入图片描述
此时就出现了第一种剪枝情况

同一个节点的所有分支中，相同的元素只能选择一次

在这里插入图片描述

然后我们再往下走，第二个位置也可以从数组中4个数字中选任意一个。但是第一个1我们要把它剪掉，因为第一个位置已经把第一个1选过了，只能选一次。此时就有了第二种剪枝情况，这个是和全排列1一模一样的。

同一个位置的数，只能使用一次 ，
还是用bool类型的check数组可以实现，check[i] = true 表明已经使用过了，
check[i] = false 说明还没有使用过。
在这里插入图片描述

但是这里还会出现剪枝情况，第一个1不能用，那我可以把第二个1放在第二个位置，但是第三个1不能出现了，因为同一个节点分支相同的数只能出现一次！

在这里插入图片描述
接下来我们就不画了，我们就可以写代码了。代码逻辑和全排列1几乎一模一样，这里我们主要分析，剪枝应该怎么写。剪枝可以从两个角度写。其实就是两个if判定语句。
1.只关心 “不合法” 的分支。 不合法的直接不让递归下去
2.只关心 “合法” 的分支 合法的就递归
虽然是两个角度，但是最终得到结果都是一样的。

只关心 “不合法” 的分支

  1. 当有一个位置已经选了这个数了下一个位置就不能在选这个位置，check[i] == true
  2. 属于同一个分支节点，前面的数和当前的数相等 就不能选当前的数了。nums[i] == nums[i-1]，但是这里有一个问题，我们这个数组里面的数字是有序的，可以这样写，如果无序就不能这样写，因此最开始先对数组进行排序。但是还是有问题，目前nums[i] == nums[i-1]这个条件太广泛了，注意看它目前只适用于第一个位置中不选择相同数，但是在第二个位置中又出现第二个1可以选第三个1不选的情况。因此还要再加条件，注意我们是从第一个位置递归下去到第二个位置然后出现相同的位置不选，但是当我们递归返回的时候这个数又可以选了。这个check[i]==true是上一层的和当前属于第二层无关！我们关注的是同一层相同元素只能选一次。因此这个条件是
    nums[i] == nums[i-1] && check[i-1] == false，但是还不够，可能会有越界的风险，因此这个条件最终是 i != 0 && nums[i] == nums[i-1] && check[i-1] == false

在这里插入图片描述
把上面两个条件组合在一起就得到只关心 “不合法” 的分支
在这里插入图片描述

只关心 “合法” 的分支

  1. 当一个数没人选的时候可以选这个数 check[i] == false，
  2. 但注意到同一层可能有相同的数，第一个相同的数没人选因为是第一次出现确实是可以选的，但是如果当前的数和前面的数相同即使当前数没人选也是不能选的，因此 还要满足 nums[i] != num[i-1] 只要这个数不和前面相同说明就是第一次出现了绝对可以选！。但是还有一种情况，如果有相同的数字，也就是 nums[i] != num[i-1] 不满足的情况，那就是满足 nums[i] == num[i-1] 前面数和后面数相同的情况，如果上一个位置选了前面的数，那走下到下一个位置的时候，因为这个数已经选过了check[i] == true，其实也就说明这个数是上一个位置的数，和我本次第二个位置选数无关，即使是相同的数子也没有关系，我也是能够选择这个后面相同的数。也就是要满足 check[i-1] == true 前面的相同数被上一个位置选了。还有最后一个情况，刚开始i==0肯定是第一次出现的数并且这个数字没人选的时候，可以选。

在这里插入图片描述

class Solution {vector<vector<int>> ret;vector<int> path;bool check[9];
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());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){// 剪枝// 1.只关心不合法// if(check[i] == true ||(i != 0 && nums[i] == nums[i-1] && check[i-1] == false))//     continue;// path.push_back(nums[i]);// check[i]=true;// dfs(nums);// check[i]=false;// path.pop_back();//恢复现场// 2.只关心合法if(check[i] == false && (i == 0 || nums[i] != nums[i-1] || check[i-1] == true)){path.push_back(nums[i]);check[i]=true;dfs(nums);check[i]=false;path.pop_back();//恢复现场}}}
};

3.电话号码的字母组合

题目链接：17. 电话号码的字母组合

题目分析：

在这里插入图片描述
就是数字对应的字符串进行排列组合。对于这种搜索啊、暴搜啊，我们已经知道要用到递归，回溯、剪枝了。
在这里插入图片描述
算法原理：
有了前面的基础，这个题我们就不写那么步骤了，画出决策树，我们直接写出对应需要的东西。不过在此之前我们需要先将数字与字符串映射关系搞和，我们可以用哈希表映射，或者其他方法，这里最简单的就是弄一个字符串数组把数字和字符串映射一下。

接下来就是画出决策树然后分析一下，首先需要两个全局变量 ret记录结果，path记录每条路径到叶子节点的组合，递归函数 给我一个digits和数字然后递归函数把组合后的结果返回出来，相信它一定能完成任务。dfs(digits,pos)，然后回溯 记得恢复现场，递归出口 到叶子节点，这道题没有剪枝。

在这里插入图片描述

class Solution {
public:string numberletter[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string> ret;string path;vector<string> letterCombinations(string digits) {if(digits.empty()) return ret;dfs(digits,0);return ret;}void dfs(string& digits,int pos){if(pos == digits.size()){ret.push_back(path);return;}string str=numberletter[digits[pos]-'0'];for(int i=0;i<str.size();++i){path+=str[i];dfs(digits,pos+1);path.pop_back();}}
};

4.括号生成

题目链接：22. 括号生成

题目分析：

在这里插入图片描述
给几对括号，然后把括号组合一下形成 有效括号
在这里插入图片描述
算法原理：
首先我们要知道什么是 有效括号的组合
1.左括号的数量 = 右括号的数量
2.从头开始的任意一个子串，左括号数量 >= 右括号数量

如下面第二种情况，虽然满足条件1但是并不满足条件2，画线字串右括号数量 > 左括号数量
在这里插入图片描述

对于这样暴力枚举的所有情况的问题，我们还是画一颗决策树，把所有情况不重不漏的情况都画出来，然后根据这棵树我们写代码。

每个位置都有两种选择，但是注意到刚开始就有剪枝的情况，刚开始不能选右括号，因为不满足条件2，所以右括号我们要分情况剪枝。当右括号数量大于等于左括号的数量时此时不能添加右括号 right >= left。还有当左括号的数量大于等于n时此时就没有左括号可以选了，left >= n。后面情况都是这样分析的，因此我们就可以做写代码的准备了。
在这里插入图片描述
全局变量，需要一个 left 记录左括号的数量，right 记录右括号的数量，还有一个n记录有几对括号要组合。还需要一个ret记录结果，path记录每条路径的结果。递归函数 每个位置都有两种选择。因为上面都是用的全局变量，因此递归函数参数什么都不用传了。dfs()。回溯 当把path放到ret里，返回后要恢复现场。pop掉path最后一个位置元素。剪枝 前面已经分析了。递归出口 当right==n的时候说明括号组合完了。

class Solution {
public:int left=0,right=0;vector<string> ret;string path;vector<string> generateParenthesis(int n) {dfs(n);return ret;}void dfs(int& n){if(right == n){ret.push_back(path);return;}if(left < n) //添加左括号{path+='(';++left;dfs(n);path.pop_back();--left;//恢复现场}if(right<left)//添加右括号{path+=')';++right;dfs(n);path.pop_back();--right;//恢复现场}}
};

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

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

相关文章

Unity射击游戏开发教程：（27）创建带有百分比的状态栏

Unity射击游戏开发教程：（27）创建带有百分比的状态栏

创建带有弹药数和推进器百分比的状态栏 在本文中，我将介绍如何创建带有分数和百分比文本的常规状态栏。 由于 Ammo Bar 将成为 UI 的一部分，因此我们需要向 Canvas 添加一个空的 GameObject 并将其重命名为 AmmoBar。我们需要一个文本和两个图像对象，它们是 AmmoBar 的父级。…
阅读更多...
认识Django框架，使用Django 2024新手创建Django项目，使用编译工具：Pycharm

认识Django框架，使用Django 2024新手创建Django项目，使用编译工具：Pycharm

Django简单介绍 Django 是一个用 Python 编写的开源 web 应用框架&#xff0c;旨在促进快速开发、维护和部署高效、可扩展的 web 应用程序。它是遵循模型-模板-视图&#xff08;MTV&#xff09;设计模式的一个高级框架&#xff0c;尽管有时也被描述为遵循MVC&#xff08;模型-…
阅读更多...
Python数据分析与机器学习在医疗诊断中的应用

Python数据分析与机器学习在医疗诊断中的应用

文章目录 &#x1f4d1;引言一、数据收集与预处理1.1 数据收集1.2 数据预处理 二、特征选择与构建2.1 特征选择2.2 特征构建 三、模型选择与训练3.1 逻辑回归3.2 随机森林3.3 深度学习 四、模型评估与调优4.1 交叉验证4.2 超参数调优 五、模型部署与应用5.1 模型保存与加载5.2 …
阅读更多...
Ubuntu基础-vim编辑器

Ubuntu基础-vim编辑器

目录 前言: 一. 安装 二. 配置 三. 基本使用 1.使用 Vim 编辑文本文件 2.代码编辑 3.多窗口编辑 四. 总结 前言: Vim 是从 VI 发展出来的一个文本编辑器&#xff0c;具有代码补充、错误跳转等功能&#xff0c;在程序员中被广泛使用。它的设计理念是命令的组合&#xff…
阅读更多...
调用华为API实现车牌识别

调用华为API实现车牌识别

目录 1.作者介绍2.华为云车牌识别2.1车牌识别技术2.2华为云OCR 3.实验过程3.1获取API密钥3.2Python代码实现3.3实验结果 参考链接 1.作者介绍 袁明懿&#xff0c;男&#xff0c;西安工程大学电子信息学院&#xff0c;2023级研究生 研究方向&#xff1a;机器视觉与人工智能 电子…
阅读更多...
全方位·多层次·智能化，漫途水库大坝安全监测方案

全方位·多层次·智能化，漫途水库大坝安全监测方案

党的十九届五中全会提出&#xff0c;到2025年前&#xff0c;完成新出现病险水库的除险加固&#xff0c;配套完善重点小型水库雨水情和安全监测设施&#xff0c;实现水库安全鉴定和除险加固常态化。 加快推进小型水库除险加固。加快构建气象卫星和测雨雷达、雨量站、水文站组成…
阅读更多...
基于STM32和人工智能的智能家居监控系统

基于STM32和人工智能的智能家居监控系统

目录 引言环境准备智能家居监控系统基础代码实现&#xff1a;实现智能家居监控系统 4.1 数据采集模块4.2 数据处理与分析4.3 控制系统4.4 用户界面与数据可视化应用场景&#xff1a;智能家居环境监控与管理问题解决方案与优化收尾与总结 1. 引言 随着智能家居技术的发展&…
阅读更多...
【STM32】飞控设计

【STM32】飞控设计

【一些入门知识】 1.飞行原理 【垂直运动】 当 mg&#xff1e;F1F2F3F4&#xff0c;此时做下降加速飞行 当 mg&#xff1c;F1F2F3F4&#xff0c;此时做升高加速飞行 当 mgF1F2F3F4 &#xff0c;此时垂直上保持匀速飞行。 【偏航飞行】 ω 4 ω 2 ≠ ω 1 ω 3 就会产生水…
阅读更多...
maven学习小结

maven学习小结

目录结构 maven为项目提供一个标准目录结构 环境配置 下载maven包后解压&#xff0c;配置解压目录的bin到path变量&#xff0c;然后终端mvn -v&#xff0c;有回显则表明maven安装成功 pom POM&#xff0c;Project Object Model&#xff0c;项目对象模型&#xff0c;是一个xm…
阅读更多...
MySQL—多表查询—联合查询

MySQL—多表查询—联合查询

一、引言 之前学习了连接查询。现在学习联合查询。 union&#xff1a;联合、联盟 对于union查询&#xff0c;就是把多次查询的结果合并起来&#xff0c;形成一个新的查询结果集 涉及到两个关键字&#xff1a;union 和 union all 注意&#xff1a; union 会把上面两个SQL查询…
阅读更多...
人脸匹配——OpenCV

人脸匹配——OpenCV

人脸匹配 导入所需的库加载dlib的人脸识别模型和面部检测器读取图片并转换为灰度图比较两张人脸选择图片并显示结果比较图片创建GUI界面运行GUI主循环运行显示全部代码 导入所需的库 cv2&#xff1a;OpenCV库&#xff0c;用于图像处理。 dlib&#xff1a;一个机器学习库&#x…
阅读更多...
Python第二语言（十四、高阶基础）

Python第二语言（十四、高阶基础）

目录 1. 闭包 1.1 使用闭包注意事项 1.2 小结 2. 装饰器&#xff1a;实际上也是一种闭包&#xff1b; 2.1 装饰器的写法&#xff08;闭包写法&#xff09; &#xff1a;基础写法&#xff0c;只是解释装饰器是怎么写的&#xff1b; 2.2 装饰器的语法糖写法&#xff1a;函数…
阅读更多...
自动化数据驱动？最全接口自动化测试yaml数据驱动实战

自动化数据驱动？最全接口自动化测试yaml数据驱动实战

前言 我们在做自动化测试的时候&#xff0c;通常会把配置信息和测试数据存储到特定的文件中&#xff0c;以实现数据和脚本的分离&#xff0c;从而提高代码的易读性和可维护性&#xff0c;便于后期优化。 而配置文件的形式更是多种多样&#xff0c;比如&#xff1a;ini、yaml、…
阅读更多...
Vue项目实践：使用滚动下拉分页优化大数据展示页面【通过防抖加标志位进行方案优化】

Vue项目实践：使用滚动下拉分页优化大数据展示页面【通过防抖加标志位进行方案优化】

Vue项目实践&#xff1a;使用滚动下拉分页优化大数据展示页面 前言 传统的分页机制通过点击页码来加载更多内容&#xff0c;虽然直观&#xff0c;但在处理大量数据时可能会导致用户体验不佳。相比之下&#xff0c;滚动下拉分页能够在用户滚动到页面底部时自动加载更多内容&…
阅读更多...
使用difflib实现文件差异比较用html显示

使用difflib实现文件差异比较用html显示

1.默认方式&#xff0c;其中加入文本过长&#xff0c;需要换行&#xff0c;因此做 contenthtml_output.replace(</style>,table.diff td {word-wrap: break-word;white-space: pre-wrap;max-width: 100%;}</style>)&#xff0c;添加换行操作 ps&#xff1a;当前te…
阅读更多...
人工智能和机器学习这两个概念有什么区别？

人工智能和机器学习这两个概念有什么区别？

什么是人工智能&#xff1f; 先来说下人工智能&#xff0c;人工智能&#xff08;Artificial Intelligence&#xff09;&#xff0c;英文缩写为AI&#xff0c;通俗来讲就是用机器去做在过去只有人能做的事。 人工智能最早是由图灵提出的&#xff0c;在1950年&#xff0c;计算机…
阅读更多...
Syncovery：跨平台高效文件备份与同步的得力助手

Syncovery：跨平台高效文件备份与同步的得力助手

在数字化时代&#xff0c;数据安全与文件同步已成为个人及企业不可或缺的需求。Syncovery作为一款专为Mac和Windows用户设计的文件备份和同步工具&#xff0c;凭借其高效、安全和易用的特点&#xff0c;赢得了广泛赞誉。 一、强大备份功能 Syncovery支持多种备份方案和数据格…
阅读更多...
AI宣传文案软件有哪些？5款AI软件推荐

AI宣传文案软件有哪些？5款AI软件推荐

AI宣传文案软件有哪些&#xff1f;AI宣传文案软件在现代营销和创意产业中扮演着越来越重要的角色&#xff0c;它们凭借先进的自然语言处理、机器学习和深度学习技术&#xff0c;不仅解放了创作者的双手&#xff0c;还大大提升了文案的生成效率和质量。这些软件能够精准捕捉用户…
阅读更多...
防火墙安全管理

防火墙安全管理

大多数企业通过互联网传输关键数据&#xff0c;因此部署适当的网络安全措施是必要的&#xff0c;拥有足够的网络安全措施可以为网络基础设施提供大量的保护&#xff0c;防止黑客、恶意用户、病毒攻击和数据盗窃。 网络安全结合了多层保护来限制恶意用户&#xff0c;并仅允许授…
阅读更多...
分布式事务的八种方案解析(1)

分布式事务的八种方案解析(1)

针对不同的分布式场景业界常见的解决方案有2PC、TCC、可靠消息最终一致性、最大努力通知等方案&#xff0c;以下总结8 种常见的解决方案&#xff0c;帮助大家在实际的分布式系统中更好地运用事务。 1.2PC 二阶段提交协议&#xff08;Two-phase commit protocol&#xff09;&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023