代码随想录算法训练营DAY25|C++回溯算法Part.2|216. 组合总和III、17.电话号码的字母组合

文章目录

  • 216. 组合总和III
    • 题意理解
    • 树形结构
    • 伪代码实现
    • 剪枝操作
    • CPP代码实现
  • 17.电话号码的字母组合
    • 解题思路
    • 树形结构
    • 伪代码实现
    • 隐藏回溯
    • CPP代码

216. 组合总和III

力扣题目链接

文章讲解:216. 组合总和III

视频讲解:和组合问题有啥区别?回溯算法如何剪枝?| LeetCode:216.组合总和III

状态:根据题目可知,k是决定树形结构的深度,那么要求组合为n的这个限制条件,我们如何写代码呢?

题意理解

题目其实就是给定一个[1, 9]的集合,求组合,要求组合和为n,个数为k

本质上就是在组合问题的基础上加了一个和的限制。

树形结构

树的宽度由我们的集合长度决定 [ 1 , 9 ] [1, 9] [1,9],树的深度由k来决定。

伪代码实现

定义全局变量path和result

  • 确定参数和返回值:
    • 参数——targetSum也就是我们的限定条件,组合的和为n
    • 组合大小k
    • 当前路径之和sum。
    • 最后我们会拿sumtarget Sum比较。还有一个重要参数startIndex.
void backtracking(targetSum, k, Sum, startIndex)
  • ⭐️递归的终止条件:本题的递归终止条件我的错误写法需要注意
//本段代码会导致错误:runtime error: signed integer overflow
if (path.size() == k && targetSum == sum){result.push_back(path);return
}
if (path.size() == k){if (targetSum == Sum) result.push_back(path);return}
  • 单层递归逻辑:求和和路径都必须进行回溯。
for (int i = startIndex; i <= 9; i++){sum += i;path.push_back(i);backtracking(targetSum, k, Sum, i + 1);sum -= i;path.pop_back();
}

剪枝操作

这里的剪枝操作就是:已选元素总和已经大于n了,那么往后遍历是没有意义的,直接剪掉

剪枝操作可以放到递归函数开始的地方。

if (sum > targeetSum){return; 
}

这里写return其实也是回溯的一种体现,因为从目前的i开始,一直往后所有的i都不需要了

for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i ++){sum += i; // 处理path.push_back(i); // 处理if (sum > targetSum) { // 剪枝操作sum -= i; // 剪枝之前先把回溯做了path.pop_back(); // 剪枝之前先把回溯做了return;}backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndexsum -= i; // 回溯path.pop_back(); // 回溯
}

CPP代码实现

class Solution {
private:vector<vector<int>> result; // 存放结果集vector<int> path; // 符合条件的结果void backtracking(int targetSum, int k, int sum, int startIndex) {if (sum > targetSum) { // 剪枝操作return; }if (path.size() == k) {if (sum == targetSum) result.push_back(path);return; // 如果path.size() == k 但sum != targetSum 直接返回}for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝sum += i; // 处理path.push_back(i); // 处理backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndexsum -= i; // 回溯path.pop_back(); // 回溯}}public:vector<vector<int>> combinationSum3(int k, int n) {result.clear(); // 可以不加path.clear();   // 可以不加backtracking(n, k, 0, 1);return result;}
};

17.电话号码的字母组合

力扣题目链接

文章讲解:17.电话号码的字母组合

视频讲解:还得用回溯算法!| LeetCode:17.电话号码的字母组合

状态:这个映射好难,甚至树形结构都画不出来有点难受。主要是问题:

  1. 待选元素的集合怪怪的,感觉是一个二维数组,也就是说我们要用两层循环控制回溯了吗?
  2. 树形结构怎么画?

解题思路

解决三个问题:

  1. 数字和字母的映射
  2. 两个字母就两个for循环,三个字符三个for循环,以此类推,然后发现代码根本写不出来
  3. 处理输入的异常情况

数字到字母的映射可以用map,也可以用二维数组来做映射。

本题中使用二维数组来做映射,这里也回答了状态1中提出的问题

树形结构

这里的树形结构应该是什么样的呢?真的很难画,这里给出了状态2中提出问题的答案

树的深度是由我们输入的数字个数来定,树的宽度就是数字所对应的字母的长度来控制

伪代码实现

定义全集变量string来收获单个结果;然后用result数组来收集全部结果

string S;
vector<string> result;
  • 递归的返回值和参数:传入数字组合digits(要注意digits是字符串类型); index来表示递归中它告诉我我传入的字符串遍历到哪一个数字了。

从树形结构可以看出,我们需要知道目前递归遍历到了哪一个数字

void backtracking(string digits, index){}
  • 终止条件:由于index是来告诉我们遍历的当前数字,所以等index遍历完最后一个数字后,递归结束。所以终止代码应该是index == digits.size()而不是index == digits.size()-1
if (index == digits.size()){result.push_back(s);return;
}
  • 单层遍历/递归逻辑:

    • const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9
      };
      
int digit = digits[index] - '0'; //这样字母就变成了一个数字
string letter = letterMap[digit];
for (int i = 0; i < letter.size; i++){s.push_back(letter[i]);backtracking(digits, index + 1);s.pop_back;
}

隐藏回溯

将回溯过程隐藏在参数中:

backtracking(digits, index+1, s+letter[i]);

CPP代码

总体C++代码如下:

// 版本一
class Solution {
private:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};
public:vector<string> result;string s;void backtracking(const string& digits, int index) {if (index == digits.size()) {result.push_back(s);return;}int digit = digits[index] - '0';        // 将index指向的数字转为intstring letters = letterMap[digit];      // 取数字对应的字符集for (int i = 0; i < letters.size(); i++) {s.push_back(letters[i]);            // 处理backtracking(digits, index + 1);  // 递归,注意index+1,一下层要处理下一个数字了s.pop_back();                       // 回溯//三段代码可以写成backtracking(digits, index+1, s+letter[i])}}vector<string> letterCombinations(string digits) {s.clear();result.clear();if (digits.size() == 0) {return result;}backtracking(digits, 0);return result;}
};

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

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

相关文章

数据库(2)

目录 6.buffer pool,redo log buffer和undo logo&#xff0c;redo logo,bin log概念以及关系&#xff1f; 7.从准备更新一条数据到事务的提交的流程描述&#xff1f; 8.能说下myisam和innodb的区别吗&#xff1f; 9.说下MySQL的索引有哪些吧&#xff1f; 10.什么是B树&…

C语言-详解内存函数

文章目录 1.memcpy使用和模拟实现1.1 memcpy函数的使用规则1.2 memcpy函数的使用1.2 模拟实现memcpy函数 2.memmove 函数的使用和模拟实现2.1 memmove 函数使用规则2.2 memmove函数的使用2.3 模拟实现memmove函数2.3.1 从后往前移2.3.2 从前往后移 2.4 算法实现2.4.1 从前往后移…

使用docker制作Android镜像(实操可用)

一、安装包准备 1、准备jdk 下载地址&#xff1a;Java Downloads | Oracle 注意版本&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 参考下面的 对照表&#xff0c;不然后面构建镜像报错&#xff0c;就是版本不对。 我就是因为下载的jdk17&…

边缘计算平台原理、关键功能以及技术优势

1、什么是边缘计算及其工作原理&#xff1f; 边缘计算是一种分布式计算模型&#xff0c;它将数据处理和存储靠近数据源头和最终用户的边缘设备上&#xff0c;从而减少了数据传输和延迟。边缘计算旨在解决云计算模型所面临的问题&#xff0c;例如延迟高、带宽瓶颈和安全性等问题…

虚幻引擎架构自动化及蓝图编辑器高级开发进修班

课程名称&#xff1a;虚幻引擎架构自动化及蓝图编辑器高级开发进修班 课程介绍 大家好 我们即将推出一套课程 自动化系统开发。 自动化技术在项目开发的前中后期都大量运用。如何您是一家游戏公司&#xff0c;做的是网络游戏&#xff0c;是不是经常会遇到程序员打包加部署需…

Energia学习案例

案例一&#xff1a;编写程序&#xff0c;实现每次按下按键&#xff0c;红色LED灯改变状态&#xff08;初始点亮&#xff09;&#xff0c;在窗口监视窗中显示按击次数。[要求用计时器实现按键消抖] #include"Timer.h" //包含计时器头文件volatile int stateHIGH; //灯…

防止邮箱发信泄露服务器IP教程

使用QQ邮箱,网易邮箱,189邮箱,新浪邮箱,139邮箱可能会泄露自己的服务器IP。 泄露原理&#xff1a;服务器通过请求登录SMTP邮箱服务器接口&#xff0c;对指定的收件人发送信息。 建议大家使用商业版的邮箱&#xff0c;比如阿里云邮箱发信等 防止邮件发信漏源主要关注的是确保邮件…

蓝桥杯练习系统(算法训练)ALGO-954 逗志芃的暴走

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 逗志芃是有妹子的现充&#xff0c;但是有时候妹子就是烦恼。因为逗志芃太逗了&#xff0c;所以这段时间妹子对逗志芃发动了…

【Vue + keep-alive】路由缓存

一. 需求 列表页&#xff0c;n 条数据项可打开 n 个标签页&#xff0c;同时1条数据项的查看和编辑共用一个标签页。如下所示&#xff1a; 参考 // 主页面 // 解决因 路由缓存&#xff0c;导致 编辑后跳转到该页面 不能实时更新数据 onActivated(() > {getList() })二. 实现…

JAVA 4

这次我学习了第四次Java课程 Math #include<math.h> 数学运算 Math.main 随机数 double aMath.random(); System.out.println(a);对小数处理 double a 3.6415; System.out.println("Math.floor: " Math.floor(a));//向下最近的整数 System.out.println(&…

wpf下如何实现超低延迟的RTMP或RTSP播放

技术背景 我们在做Windows平台RTMP和RTSP播放模块对接的时候&#xff0c;有开发者需要在wpf下调用&#xff0c;如果要在wpf下使用&#xff0c;只需要参考C#的对接demo即可&#xff0c;唯一不同的是&#xff0c;视频流数据显示的话&#xff0c;要么通过控件模式&#xff0c;要么…

【黑马头条】-day09用户行为-精度丢失-点赞收藏关注

文章目录 1 long类型精度丢失问题1.1 解决1.2 导入jackson序列化工具1.3 自定义注解1.4 原理1.5 测试 2 用户行为要求3 创建微服务behavior3.1 微服务创建3.2 添加启动类3.3 创建bootstrap.yml3.4 在nacos中配置redis3.5 引入redis依赖3.6 更新minio 4 跳过 1 long类型精度丢失…

小红的白色字符串

题目描述 小红拿到了一个字符串&#xff0c;她准备将一些字母变成白色&#xff0c;变成白色的字母看上去就和空格一样&#xff0c;这样字符串就变成了一些单词。 现在小红希望&#xff0c;每个单词都满足以下两种情况中的一种&#xff1a; 1.开头第一个大写&#xff0c;其余为…

01、ArcGIS For JavaScript 4.29对3DTiles数据的支持

综述 Cesium从1.99版本开始支持I3S服务的加载&#xff0c;到目前位置&#xff0c;已经支持I3S的倾斜模型、3D Object模型以及属性查询的支持。Cesium1.115又对I3S标准的Building数据实现了加载支持。而ArcGIS之前一直没有跨越对3DTiles数据的支持&#xff0c;所以在一些开发过…

抖音滑块验证码加密的盐的位置

最近更新后之前很容易找到盐的位置的方法变了&#xff0c;抖音特意把盐隐藏起来了 {"reply": "RJC","models": "yAd8rl","in_modal": "DTn0nD2","in_slide": "ou7H0Ngda","move": …

Vue2(十五):replace属性、编程式路由导航、缓存路由组件、路由组件独有钩子、路由守卫、history与hash

一、router-link的replace属性 1、作用&#xff1a;控制路由跳转时操作浏览器历史记录的模式 2、浏览器的历史记录有两种写入方式&#xff1a;分别为push和replace&#xff0c;push是追加历史记录&#xff0c;replace是替换当前记录。路由跳转时候默认为push 3、如何开启repla…

环信 IM 客户端将适配鸿蒙 HarmonyOS

自华为推出了自主研发操作系统鸿蒙 HarmonyOS 后&#xff0c;国内许多应用软件开始陆续全面兼容和接入鸿蒙操作系统。环信 IM 客户端计划将全面适配统鸿蒙 HarmonyOS &#xff0c;助力开发者快速实现社交娱乐、语聊房、在线教育、智能硬件、社交电商、在线金融、线上医疗等广泛…

基于java+springboot+vue实现的网上购物系统(文末源码+Lw+ppt)23-42

摘 要 随着我国经济的高速发展与人们生活水平的日益提高&#xff0c;人们对生活质量的追求也多种多样。尤其在人们生活节奏不断加快的当下&#xff0c;人们更趋向于足不出户解决生活上的问题&#xff0c;网上购物系统展现了其蓬勃生命力和广阔的前景。与此同时&#xff0c;为…

我与C++的爱恋:类与对象(二)

​ ​ &#x1f525;个人主页&#xff1a;guoguoqiang. &#x1f525;专栏&#xff1a;我与C的爱恋 ​ 本篇着重介绍构造函数和析构函数&#xff0c;剩余内容在下篇解答。 一、类的默认成员函数 如果一个类中什么成员都没有&#xff0c;简称为空类。 任何类在什么都不写时…

GFS部署实验

目录 1、部署环境 ​编辑 2、更改节点名称 3、准备环境 4、磁盘分区&#xff0c;并挂载 5. 做主机映射--/etc/hosts/ 6. 复制脚本文件 7. 执行脚本完成分区 8. 安装客户端软件 1. 安装解压源包 2. 创建gfs 3. 安装 gfs 4. 开启服务 9、 添加节点到存储信任池中 1…