【代码随想录day22】【C++复健】77. 组合;216.组合总和III; 17.电话号码的字母组合

77. 组合

这题做完之后还是有一种稀里糊涂的感觉。思考了半天什么范围合理,并且怎么设置才能让这个范围合理,然而一看答案,发现答案完全没考虑这些因素,直接暴力全遍历了。只能说确实这样能够放弃思考,比较省心一些...

class Solution {
public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> result;vector<int> path;int startindex = 1;select(n, k, startindex, result, path);return result;}void select(int n, int k, int startindex, vector<vector<int>>& result, vector<int>& path){for(int i=startindex; i<=n; i++){path.push_back(i);if(path.size() == k){result.push_back(path);}else{select(n, k, i+1, result, path);}path.pop_back();}}
};

重新看了下剪枝操作的视频部分,其实当时就是没想清楚到底是多少,看完之后才知道是n-(k-patch.size())+1,这里面patch.size()表示已经添加的元素,k-patch.size()代表还需要添加的元素,那么,n-(k-patch.size())+1就表示要从这里开始的索引。

关于为什么要+1其实有一个比较好想的点,就是从a到(a+k)一共有k+1个元素,所以当我们需要k个元素的时候,最晚要从a+1开始。

 216.组合总和III

在看完上题的解析后,本题我也是放弃了思考,但还是出现了两个小问题,都是因为没读题:

1 没看到要是k个数的和,以为是任意的

2 没看到只能是1-9,以为是任意的

class Solution {
public:vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> result;vector<int> path;int startindex = 1;comb(k, n, startindex, result, path);return result;}void comb(int k, int n, int startindex, vector<vector<int>>& result, vector<int>& path) {if(n == 0 && path.size() == k){result.push_back(path);return ;}else if(n <0){return;}for(int i = startindex; i<=9; i++){path.push_back(i);n -= i;comb(k, n, i + 1, result, path);n += i;path.pop_back();}}
};
看完这个题的剪枝操作之后,发现有时候其实也需要把握一个度,比如卡哥写的剪枝逻辑是,如果当前的sum已经大于targetSum的话就可以返回,其实和我这个n<0是差不多一个意思的,都是比较好实现的剪枝逻辑。
但实际上,如果要进行最大程度的剪枝的话,比如说当前取i,还要取k个数,那么我的i+1一直到i+k如果已经大于sum了,就没必要继续了,这样其实是最效率最大程度的剪枝,但是有的时候代码实现的复杂程度也是要考虑的成本之一,尤其是像我这种懒人。

17.电话号码的字母组合

自己写了一段很蠢但是能执行的代码。

本来想的是用3*(电话按键-2)作为每段起点的,但是后来发现7和9还要做特殊处理,直接放弃了思考写出了如下代码。

class Solution {
public:vector<string> letterCombinations(string digits) {vector<string> s;string path;int i = 0;comb(digits, i, s, path);return s;}void comb(string digits, int curindex, vector<string>& s, string& path) {if(curindex == digits.size()){if(path != ""){s.push_back(path);}return ;}int now = digits[curindex]- '0';cout << now << endl;if(now == 2){for(int i = 0; i<3; i++){path += char('a' + i);comb(digits, curindex + 1, s, path);path.pop_back();}}else if(now == 3){for(int i = 0; i<3; i++){path += char('d' + i);comb(digits, curindex + 1, s, path);path.pop_back();}}else if(now == 4){for(int i = 0; i<3; i++){path += char('g' + i);comb(digits, curindex + 1, s, path);path.pop_back();}}else if(now == 5){for(int i = 0; i<3; i++){path += char('j' + i);comb(digits, curindex + 1, s, path);path.pop_back();}}else if(now == 6){for(int i = 0; i<3; i++){path += char('m' + i);comb(digits, curindex + 1, s, path);path.pop_back();}}else if(now == 7){for(int i = 0; i<4; i++){path += char('p' + i);comb(digits, curindex + 1, s, path);path.pop_back();}}else if(now == 8){for(int i = 0; i<3; i++){path += char('t' + i);comb(digits, curindex + 1, s, path);path.pop_back();}}else{for(int i = 0; i<4; i++){path += char('w' + i);comb(digits, curindex + 1, s, path);path.pop_back();}}}
};

在看完了卡哥的解析之后发现,二维数组确实是一个很好的存储方式,学到了。

用二维数组的话,就能避免像我的代码里一样不停地加加减减,只要正常用for循环遍历就行,更简单一点。

除此之外,还遇到了几个问题:
1 一开始判断条件写成了if(curindex == digits.size() - 1),然后报了一个栈溢出。这个为什么会导致栈溢出呢?当size是0的时候,等式右边是-1,但这个条件永远也达不到,因为curindex是永远不可能变成-1的,这就使得程序无线递归,直到发生栈溢出。

2 int now = digits[curindex] - '0';最开始没写后面的- '0';,导致实际上now的范围是从50开始的。实际上这里相当于是ascii码,需要减掉'0'对应的ascii码才是对的。

不过还有一个需要注意的一点,我修改的时候尝试了int(digits[curindex]),也不行,也输出的是ascii码。为什么不行呢?请看GPT:

也就是说实际上这个函数返回的也是ascii码。

3 不知道string怎么移除队尾元素,所以写了path -= char('j' + i);,但实际上string只重载了加号没有重载减号,所以这么写是会导致报错的。或者直接按照卡哥的写法,传参的时候这么传:

self.getCombinations(digits, index + 1, s + letter, result)

 这样子的话,就不用考虑怎么减去了,因为本来就没加进去。

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

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

相关文章

solidworks默认模板无效/打开step文件为空白 不显示模型

①打开step文件时如下提示&#xff1a; 是由于sw模版没有设置好 解决方法&#xff1a; 把零件和装配体模版选一下&#xff0c;gb_part和gb_assembly 再打开文件就不会有提示了。 ②打开step文件为空白 不显示模型 文件未损坏且sw版本正确情况下&#xff0c; 首先尝试按F&…

easyexcel实现自定义的策略类, 最后追加错误提示列, 自适应列宽,自动合并重复单元格, 美化表头

easyexcel实现自定义的策略类, 最后追加错误提示列, 自适应列宽,自动合并重复单元格, 美化表头 原版表头和表体字体美化自动拼接错误提示列自适应宽度自动合并单元格使用Easyexcel使用poi导出 在后台管理开发的工作中,离不开的就是导出excel了. 如果是简单的导出, 直接easyexce…

微深节能 煤码头自动化翻堆及取料集控系统 格雷母线

一、系统概述 微深节能在煤码头自动化翻堆及取料集控系统中引入了格雷母线高精度位移测量系统&#xff0c;该系统是一项重要的技术创新&#xff0c;显著提升了煤码头作业的自动化水平和精确性。它主要用于实现对斗轮堆取料机等大型机械设备的精准定位和自动化控制&#xff0c;从…

LeetCode 热题100 之 栈

1.有效的括号 思路分析&#xff1a;我们可以使用栈&#xff08;stack&#xff09;来解决这个问题。栈是一种先进后出的数据结构&#xff0c;这与括号匹配的需求非常契合。 unordered_map<char, char> bracket_map&#xff1a;这个哈希表用来存储右括号与左括号的对应关系…

yolov11-seg数据集制作训练推理流程:

文章目录 前言一、数据集制作二、模型训练推理&#xff1a; 前言 随着深度学习技术的不断发展&#xff0c;目标检测与分割技术在计算机视觉领域扮演着越来越重要的角色。YOLO&#xff08;You Only Look Once&#xff09;作为一种高效、实时的目标检测算法&#xff0c;自提出以…

基于Spring Boot的乡政府管理系统设计与实现,LW+源码+讲解

摘 要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff0c;在计算机上安装乡政府管理系统软件来发挥其高效地信息处理的作用&#xf…

python的学习

0.tips 1.变量命名规则 2.变量的赋值 3.变量的类型 int&#xff0c;float&#xff0c;str&#xff08;双引号、单引号、三引号包含都可以&#xff09; 类型带来的意义 动态类型的基本特性 4.注释 5.控制台 格式化字符串f-string 输入/输出input 6.运算符 算术运算符 //&…

信息安全工程师(79)网络安全测评概况

一、定义与目的 网络安全测评是指参照一定的标准规范要求&#xff0c;通过一系列的技术、管理方法&#xff0c;获取评估对象的网络安全状况信息&#xff0c;并对其给出相应的网络安全情况综合判定。其对象主要为信息系统的组成要素或信息系统自身。网络安全测评的目的是为了提高…

【GoWeb示例】通过示例学习 Go 的 Web 编程

文章目录 你好世界HTTP 服务器路由&#xff08;使用 gorilla/mux&#xff09;连接到 MySQL 数据库MySQL 数据库简单操作模板静态资源和文件操作表单处理中间件&#xff08;基础&#xff09;中间件&#xff08;高级&#xff09;会话JSONWebsockets密码哈希 你好世界 Go语言创建…

UnixBench和Geekbench进行服务器跑分

1 概述 服务器的基准测试&#xff0c;常见的测试工具有UnixBench、Geekbench、sysbench等。本文主要介绍UnixBench和Geekbench。 1.1 UnixBench UnixBench是一款开源的测试UNIX系统基本性能的工具&#xff08;https://github.com/kdlucas/byte-unixbench&#xff09;&#x…

打造个性化时钟应用:结合视觉与听觉的创新实践

​ 在数字时代&#xff0c;虽然手机、电脑等设备已经能够非常方便地显示时间&#xff0c;但一款融合了视觉艺术和声音效果的桌面时钟仍能给我们的日常生活带来不一样的体验。本文将引导读者通过Python语言及其强大的库支持来创建一个具有整点及半点报时功能的美观时钟界面。该项…

ASMR助眠声音视频素材去哪找 吃播助眠素材网站分享

在快节奏的现代生活中&#xff0c;越来越多的人感到压力山大&#xff0c;许多人开始寻求助眠和放松的方式。而ASMR&#xff08;自发性知觉经络反应&#xff09;助眠声音视频&#xff0c;凭借其独特的声音刺激和放松效果&#xff0c;成为了睡前的“神器”。如果你是一位内容创作…

Ente: 我们的 Monorepo 经验

原文&#xff1a;manav - 2024.10.29 九个月前&#xff0c;我们切换到了 monorepo。在此&#xff0c;我将介绍我们迄今为止的切换经验。 这并不是一份规范性的建议&#xff0c;而是一个经验的分享&#xff0c;目的是希望能够帮助其他团队做出明智的决策。 与大多数岔路不同&…

css:还是语法

emmet的使用 emmet是一个插件&#xff0c;Emmet 是 Zen Coding 的升级版&#xff0c;由 Zen Coding 的原作者进行开发&#xff0c;可以快速的编写 HTML、CSS 以及实现其他的功能。很多文本编辑器都支持&#xff0c;我们只是学会使用它&#xff1a; 生成html结构 <!-- emme…

常见计算机网络知识整理(未完,整理中。。。)

TCP和UDP区别 TCP是面向连接的协议&#xff0c;发送数据前要先建立连接&#xff1b;UDP是无连接的协议&#xff0c;发送数据前不需要建立连接&#xff0c;是没有可靠性&#xff1b; TCP只支持点对点通信&#xff0c;UDP支持一对一、一对多、多对一、多对多&#xff1b; TCP是…

javascript实现国密sm4算法(支持微信小程序)

概述&#xff1a; 本人前端需要实现sm4计算的功能&#xff0c;最好是能做到分多次计算。 本文所写的代码在现有sm4的C代码&#xff0c;反复测试对比计算过程参数&#xff0c;成功改造成sm4的javascript代码&#xff0c;并成功验证好分多次计算sm4数据 测试平台&#xff1a; …

深度解读AI在数字档案馆中的创新应用:高效识别与智能档案管理

一、项目背景介绍 在信息化浪潮推动下&#xff0c;基于OCR技术的纸质档案电子化方案成为解决档案管理难题的有效途径。该方案通过先进的OCR技术&#xff0c;能够统一采集各类档案数据&#xff0c;无论是手写文件、打印文件、复古文档还是照片或扫描的历史资料&#xff0c;都能实…

C++ | Leetcode C++题解之第554题砖墙

题目&#xff1a; 题解&#xff1a; class Solution { public:int leastBricks(vector<vector<int>>& wall) {unordered_map<int, int> cnt;for (auto& widths : wall) {int n widths.size();int sum 0;for (int i 0; i < n - 1; i) {sum wi…

【机器学习】强化学习(1)——强化学习原理浅析(区分强化学习、监督学习和启发式算法)

文章目录 强化学习介绍强化学习和监督学习比较监督学习强化学习 强化学习的数学和过程表达动作空间序列决策策略&#xff08;policy&#xff09;价值函数&#xff08;value function&#xff09;模型&#xff08;model&#xff09; 强化学习和启发式算法比较强化学习步骤代码走…

模糊搜索:在不确定性中寻找精确结果

目录 模糊搜索&#xff1a;在不确定性中寻找精确结果 一、引言 二、模糊搜索的背景 三、模糊搜索的原理 1、编辑距离&#xff08;Levenshtein Distance&#xff09;&#xff1a; 2、Jaccard 相似系数&#xff1a; 3、Soundex 算法&#xff1a; 4、TF-IDF&#xff08;词…