【C++】string OJ练习
文章目录
- 1. 仅仅反转字母
- 思路分析
- 代码实现
- 2. 字符串中的第一个唯一字符
- 题目分析
- 代码实现
- 3. 《剑指offer》——替换空格
- 解法一:寻找替换
- 思路分析
- 代码实现
- 优化
- 解法二:空间换时间
- 思路分析
- 代码实现
- 4.字符串最后一个单词的长度
- 思路分析
- 代码实现
- 5. 字符串相加
- 思路分析
- 代码实现
- 优化(提升效率)
我们来看几道string相关的OJ,来练习一下string的使用。
1. 仅仅反转字母
题目链接: link
我们一起来看一下题:
思路分析
我们来分析一下题目,这道题让我们干什么呢?
给我们一个字符串,该字符串中有英文字符也有非英文字符,要求我们去反转字符串中的所有英文字母,非英文字母的字符位置不动。
那是不是很简单啊,左右两个指针分别指向首尾,然后依次向中间移动寻找英文字母,找到后停下来,然后两个指针指向的英文字母进行交换,接着继续向中间移动,两者相遇结束。(是不是跟一趟快排的逻辑有点像啊)
代码实现
class Solution {
public:bool isletter(char x){if((x>='a'&&x<='z')||(x>='A'&&x<='Z'))return true;return false;}string reverseOnlyLetters(string s) {int begin=0;int end=s.size()-1;while(begin<end){while((begin<end)&&!isletter(s[begin]))begin++;while((begin<end)&&!isletter(s[end]))end--;swap(s[begin],s[end]);begin++; end--;}return s;}
};
代码呢也比较简单,相信大家都能看懂,就不过多解释了。
2. 字符串中的第一个唯一字符
链接: link
题目分析
题目让我们找出字符串中第一个不重复的字符,那我们最容易想到的就是暴力求解,从头到尾遍历字符串,依次拿每一个字符与其他字符进行比较,如果没有与之重复的则当前字符就是要找的字符,返回其下标,有重复的就不是,继续看下一个,最终一个也没找到就返回-1。
当然这样的时间复杂度就是O(N^2)
那有没有好一点的方法呢?
🆗,其实呢我们可以考虑用计数排序的思想去搞:
题目说了只包含小写字母
所以字符串中字符的范围就是【a,z】,那我们就可以创建一个大小为26的整型数组,然后用一个相对映射去统计每个字母的出现次数,a就映射到下标为0的位置,b就映射到下标为1的位置,依次类推。
那怎么让这些字母映射到对应的位置呢?
减去’a’得到的值是不是就是它们映射的位置啊,然后遍历字符串,每个字母映射的值是几,就让下标为几的元素++,初值全为0,这样遍历过后每个字母出现的次数就统计出来了。(下标0的元素的值就是a出现的次数,1位置就是b出现的次数…)
但是现在有一个问题,那就是出现一次的字母可能不止一个,我们怎么判断那个是第一个只出现一次的字母呢?
🆗,这里我们不要去遍历统计次数的数组,还是从前往后去遍历字符串,然后看哪个字母的次数是1,第一个是1的就是第一个只出现一次的字母。
代码实现
class Solution {
public:int firstUniqChar(string s) {int count[26]={0};for(auto e:s){count[e-'a']++;}for(int i=0;i<s.size();i++){if(count[s[i]-'a']==1)return i;}return -1;}
};
大家结合上面的分析再看一看代码,相信就能理解了。
3. 《剑指offer》——替换空格
接下来我们来看一道《剑指offer》于string相关的题目——替换空格
解法一:寻找替换
思路分析
大家思考一下这道题可以怎么解?
是不是可以考虑用find+replace搞啊。
用find找的字符串中的所有空格,然后用replace将其替换成%20
不就行了嘛。
代码实现
我们来实现一下代码:
class Solution {
public:string replaceSpace(string s) {size_t pos=s.find(' ');while(pos!=string::npos)//find找不到返回npos{s.replace(pos,1,"%20");pos=s.find(' ');}return s;}
};
🆗,就通过了。
优化
那大家看一下,我们刚才上面那样写好吗,或者说有没有可以优化的地方?
是可以做一些优化的。
来看find是不是可以指定开始查找的位置啊,如果我们不传pos的话它默认是从起始位置开始查找的,但是这里我们要查找所有的空格,并且对它们进行替换,那第一个空格被替换之后,我们往后查找第二个的时候,还有必要从头开始找吗,是不是就可以从替换之后的尾部开始往后找啊,这样效率是不是就高了一点会。
所以我们可以这样改进一下:
那大家再想,还可以再优化吗?
其实还有一个地方可以做一些优化,大家想,我们这里replace是把空格替换成
%20
,这样使用的空间是不是多了,那replace在替换的过程中是不是有可能空间不够进行扩容啊,那有没有什么办法可以避免replace的过程中可能会去频繁的扩容(扩容是有消耗的,特别是异地扩)。
🆗,我们是不是可以计算出需要多少空间,然后提前把空间开好啊。那大家说,这里应该用什么?
resize
还是reserve
,reserve
可以改变容量帮我们开空间,而resize
除了开空间还可以初始化,但是这里有必要对开好的空间进行初始化吗?
是不是没必要啊,所以我们用reserve就行了。
那需要多少空间呢,空格替换成%20
,所以每个空格多两个空间,那我们可以统计一下空格数,然后提前把空间开好
写一下代码:
class Solution {
public:string replaceSpace(string s) {int count=0;for(auto e:s){if(e==' ')count++;}s.reserve(s.size()+2*count);size_t pos=s.find(' ');while(pos!=string::npos){s.replace(pos,1,"%20");pos=s.find(' ',pos+3);}return s;}
};
解法二:空间换时间
那除了上面那种方法,其实还可以考虑另一种思路:
思路分析
我们可以创建一个新的string对象,然后遍历原串,不是空格,就直接+=到新串,是空格,就把
"%20"
+=到新串。
这样的好处是不需要像上面那样挪动数据了,只不过多开了一点空间。
代码实现
这个代码就非常简单:
class Solution {
public:string replaceSpace(string s) {string news;for(auto e:s){if(e!=' ')news+=e;elsenews+="%20";}return news;}
};
当然这种方法在+=的过程中也有可能会扩容,所以我们也可以把reserve那一步加上。
4.字符串最后一个单词的长度
链接: link
输入一个字符串,求它的最后一个单词的长度。
思路分析
那这是不是简单啊:
我们是不是可以用rfind去搞啊。
找到倒数第一个空格的位置pos是不是就能计算出长度了
用size - pos -1是不是就是最后一个单词长度。
注意:输入的字符串可能有空格,所以我们输入用getline。
代码实现
写一下代码:
#include <iostream>
using namespace std;int main() {string s;getline(cin,s);size_t pos=s.rfind(' ');if(pos!=string::npos){cout<<s.size()-pos-1<<endl;}
}
🆗,提交一下:
有一个测试用例没过:
我们看到这个测试用例只有一个单词,所以找不到空格,但我们刚才没考虑找不到空格的情况。
那怎么解决?
🆗,这种情况答案不就是这一个单词的长度嘛,很好处理:
#include <iostream>
using namespace std;int main() {string s;getline(cin,s);size_t pos=s.rfind(' ');if(pos!=string::npos){cout<<s.size()-pos-1<<endl;}else {cout<<s.size()<<endl;}
}
5. 字符串相加
链接: link
思路分析
我们来一起看一下:
这道题是给定两个字符串形式的非负整数 num1 和num2 ,让我们计算它们的和并同样以字符串形式返回。
我们来分析一下应该怎么做?
就拿这个例子来说:
这里我们是不是应该倒着走啊,从低位开始加,首先取到两个字符串的最后一个字符,相加,7+6是13,但是我们这里把3保存下来,1是不是要进到上一位啊,所以我们应该搞一个变量来保存进位;
那然后再去加它们对应的倒数第二位,依次往前走,所以这应该是一个循环的过程,那什么时候结束?
是不是两个字符串全都遍历完才结束啊,当然它们可能会有一个先走完,那另一个剩下的每次跟0相加就行了。
所以我们应该先获取一下它们最后一个元素的下标end,加一个数,两者的end就- -
一次,减到-1就是遍历完了。
然后里面我就去循环走我们的这个逻辑。
代码实现
那我们来写一下代码:
class Solution {
public:string addStrings(string num1, string num2) {int end1=num1.size()-1;int end2=num2.size()-1;while(end1>=0||end2>=0){}}
};
🆗,那在循环里面我们就依次去取对应的两个字符进行相加了。
但是这里我们能直接用字符相加吗?我们的字符取出来是啥,是不是取的是它们对应的ASCII码值啊,想拿到它对应的数字,怎么办?
是不是应该减去'0'
啊
int val1=num1[end1]-'0';
但是呢,这里还存在一个问题:我们这里是不是只要有一个字符串没走完循环就不结束啊,也就是即使在循环里面,也有可能有一个已经走完了,所以我们这里直接取这个end是不是可以越界啊,所以加个判断:
当然这个地方我们可以用三目运算符来简化一下:
然后就该相加了,但是相加是不是会产生进位啊,所以我们再定义一个变量表示进位,初值给个0。
那相加之后,如果和大于等于10,进位的值是不是就该变成1 了。当然如果小于10 那就还是0。
所以我们可以这样写:
next=sum/10;
那另外如果和大于10,我们是不是只留下各位的数就行了。
sum%=10;
然后呢,得出的结果我们是不是要存下来。
题目要求最后还是返回一个字符串,所以我们再创建一个string对象保存结果。
但是现在面临一个问题,我们先得到的是不是低位的数字啊,它们应该放在后面,所以这里我们每次保存得出的结果应该是头插到string对象中,那我们就可以用insert,每次插入到下标0的位置。
注意这里插入的时候要把字符0再加上。
那加完之后它们的end的位置是不是都要- -一下啊。
那这样循环结束,是不是就得到结果了。
class Solution {
public:string addStrings(string num1, string num2) {int end1=num1.size()-1;int end2=num2.size()-1;int next=0;//进位string ret;while(end1>=0||end2>=0){int val1=(end1>=0?num1[end1]-'0':0);int val2=(end2>=0?num2[end2]-'0':0);int sum=val1+val2+next;next=sum/10;sum%=10;ret.insert(0,1,sum+'0');end1--;end2--;}return ret;}
};
我们来提交一下:
🆗,有一些测试用例没过。我们来看一下:
看当前报错给的这个用例,1和9我们输出的是0,什么问题啊?
是不是循环结束之前最后一次得出的进位如果是0那就不用管了,但如果是1 ,我们是不是还得加上去啊。
🆗,我们刚才是不是忽略掉这个情况了:
class Solution {
public:string addStrings(string num1, string num2) {int end1=num1.size()-1;int end2=num2.size()-1;int next=0;//进位string ret;while(end1>=0||end2>=0){int val1=(end1>=0?num1[end1]-'0':0);int val2=(end2>=0?num2[end2]-'0':0);int sum=val1+val2+next;next=sum/10;sum%=10;ret.insert(0,1,sum+'0');end1--;end2--;}if(next==1)ret.insert(0,1,'1');return ret;}
};
🆗,这下就通过了。
但是大家看一下,我们刚才的这种搞法效率是不是比较低啊,我们这里每次都要调用insert头插挪动数据,那是不是O(N^2)啊。
我们上一篇文章也提到了,insert是不是能少用就少用啊。这里效率低主要就低在insert这里了。
所以,能不能想办法改进一下啊。
优化(提升效率)
那我们可以怎么改进一下呢?
🆗,insert头插需要挪动数据效率低,那我们就不用头插了呗,我们就依次放到后面,一个个尾插,最后我们再逆置一下不就行了嘛。
那逆置呢,我们可以自己写一个函数。
但是,其实不需要。因为C++的算法库里其实给我们提供了逆置的函数,我们可以直接用:
我们看到这里使用的时候去传迭代器区间就行了。
修改成这样。
class Solution {
public:string addStrings(string num1, string num2) {int end1=num1.size()-1;int end2=num2.size()-1;int next=0;//进位string ret;while(end1>=0||end2>=0){int val1=(end1>=0?num1[end1]-'0':0);int val2=(end2>=0?num2[end2]-'0':0);int sum=val1+val2+next;next=sum/10;sum%=10;//ret.insert(0,1,sum+'0');ret+=(sum+'0');end1--;end2--;}if(next==1)//ret.insert(0,1,'1');ret+='1';reverse(ret.begin(),ret.end());return ret;}
};
效率明显就提升了。
🆗,那还有没有可以优化的地方?
这里涉及到插入数据,我们就可以考虑干嘛?
是不是可以提前把空间开好以此来避免在插入数据的时候可能引发扩容。
那大家思考一下对于这道题我们应该提前开多少空间合适?
大家想,两个数相加,结果最多是不是会比长的那个数的位数多出一位啊。
比如,两个最大的两位数相加,99+99,也就3位嘛。
所以:
就可以这样搞一下。
class Solution {
public:string addStrings(string num1, string num2) {int end1=num1.size()-1;int end2=num2.size()-1;int next=0;//进位string ret;ret.reserve(num1.size()>num2.size()?num1.size()+1:num2.size()+1);while(end1>=0||end2>=0){int val1=(end1>=0?num1[end1]-'0':0);int val2=(end2>=0?num2[end2]-'0':0);int sum=val1+val2+next;next=sum/10;sum%=10;//ret.insert(0,1,sum+'0');ret+=(sum+'0');end1--;end2--;}if(next==1)//ret.insert(0,1,'1');ret+='1';reverse(ret.begin(),ret.end());return ret;}
};
🆗,这篇文章就到这里,欢迎大家指正!!!
相关文章:

【C++】string OJ练习
文章目录1. 仅仅反转字母思路分析代码实现2. 字符串中的第一个唯一字符题目分析代码实现3. 《剑指offer》——替换空格解法一:寻找替换思路分析代码实现优化解法二:空间换时间思路分析代码实现4.字符串最后一个单词的长度思路分析代码实现5. 字符串相加思…...

进程间通信IPC
进程间通信IPC (InterProcess Communication) 一、进程间通信的概念 每个进程各自有不同的用户地址空间,任何一个进程的全局变量在另一个进程中都看不到,所以进程之间要交换数据必须通过内核,在内核中开辟一块缓冲区,进程1把数据…...

操作系统-页面淘汰算法(下)-软件设计(二十六)
操作系统-PV操作(上)-软件设计(二十五)https://blog.csdn.net/ke1ying/article/details/129476031 存储管理-分区存储组织 问:计算机系统内存大小为128k,当前系统分配情况如图,那么作业4再次申…...
23种设计模式-责任链模式(Android开发实际应用场景介绍)
什么是责任链模式 责任链模式是一种行为型设计模式,它的核心思想是将请求从一系列处理者中传递,直到其中一个处理者能够处理它为止。在这个过程中,请求可以被任何一个处理者处理,也可以被拒绝,直到有一个处理者能够处…...
Socket+Select+Epoll笔记
讲到epoll,就必须了解Socket,上篇博客写了Socket的基本使用方法,步骤主要为创建一个socketsocket是进程之间通信的,那么进程通信如何找到这个socket呢?当然是端口号,所以socket就要和端口号进行绑定&#x…...
git查看最近修改的文件
git log --name-status 每次修改的文件列表, 显示状态 git log --name-only 每次修改的文件列表 git log --stat 每次修改的文件列表, 及文件修改的统计 git whatchanged 每次修改的文件列表 git whatchanged --stat 每次修改的文件列表, 及文件修改的统计 git show 显示最…...
【算法基础(四)】堆排序(二)
堆排序(二) 把数组从零开始连续的一段 完全二叉树 size i 左 son 2*11 i 右 son 2*12 父 (i-1) / 2 堆是完全二叉树,分为大根堆和小根堆 在完全二叉树里,每一棵子数最大的值是头节点的值,就是大根堆 同理&…...
C++类型转换
C语言的转换是在变量前加类型名进行转换的,比如double pi 3.14;int a (int) pi;对于指针也是如此double* dptr πint* iptr (int*)dptr;虽然c兼容了C语言的转型方式,但是也做了很多限制,比如向上类型转换,在c中建议使用…...

Keil MDK6要来了,将嵌入式软件开发水平带到新高度,支持跨平台(2023-03-11)
注:这个是MDK6,不是MDK5 AC6,属于下一代MDK视频版: https://www.bilibili.com/video/BV16s4y157WF Keil MDK6要来了,将嵌入式软件开发水平带到新高度,支持跨平台一年一度的全球顶级嵌入式会展Embedded Wor…...

蓝桥杯刷题第九天
题目描述本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。素数就是不能再进行等分的整数。比如7,11。而 9 不是素数,因为它可以平分为 3 等份。一般认为最小的素数是2,接着是 3,5&…...

a-tree-select 基本使用,下拉框高度和宽度设置、回显时滚动条定位解决。
目录一、基本使用1. 界面效果2. 代码实现3. 问题1:下拉框占满整个屏幕4. 问题4:菜单内容过长时,下拉菜单宽度无限变宽。二、数据回显、滚动条定位1. 界面效果2. 代码实现2.1 获取默认展开节点2.1.1 代码实现2.1.2 说明2.2 设置滚动条定位2.2.…...

【Linux】之nc命令(连接与扫描指定端口、监测服务端口的使用情况)解析、详解实例、邮件告警
🍁博主简介 🏅云计算领域优质创作者 🏅华为云开发者社区专家博主 🏅阿里云开发者社区专家博主 💊交流社区:运维交流社区 欢迎大家的加入! 文章目录nc命令简介nc命令的安装nc命令语法格式…...

cdn简单配置
cdn配置域名接入CDN编辑CDN配置本地修改hosts文件,绕过公网解析域名接入CDN 添加CDN域名以及回源配置 编辑CDN配置 默认后端端口是80,如果测试发现无法访问,则可能是443或其它 如果域名在CDN后端有https强制跳转,后端端口一定是44…...

前端安全(自留)
目录XSS——跨站脚本常见解决CSRF ——跨站请求伪造常见解决XSS——跨站脚本 当目标站点在渲染html的过程中,遇到陌生的脚本指令执行。 攻击者通过在网站注入恶意脚本,使之在用户的浏览器上运行,从而盗取用户的信息如 cookie 等。 常见 解…...

零基础转行云计算可行吗
目前处于云年代,云计算运维工程师的工作远景还是十分广泛的。像是阿里云计算,滴滴,抖音等等互联网大厂目前都在使用云核算技能。 云计算运维工程师的薪资水平也十分可观。 运维工程师(Operations),在国内又称为运维开发工程师(Dev…...

【AcWing】蓝桥杯备赛-深度优先搜索-dfs(1)
目录 写在前面: 题目:92. 递归实现指数型枚举 - AcWing题库 读题: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC &…...

孩子免费就读|私企经理自费赴美国东海岸高校访学
私企U经理无文章无课题,出国访学除了为考察市场、拓宽人脉、提升履资外,另一个主要目的是带孩子在美国接受当地免费的公立中小学教育,并把访学目标学校定位在东海岸。最终其采纳了板凳费相对较低的佐治亚大学邀请函,签证时居然全家…...

前端面试hr经常会问的问题
文章目录前言1.自我介绍2.为什么你要离职?3.工作经历4.职业规划5.优点、缺点6.还有什么要问的总结前言 这里记录了一些面试中hr或者项目负责人经常会问的一些问题,可以提前参考参考,想想该怎么回答,为之后的面试做好准备…...
C动态数组
在实际项目中,我们经常与各式各样的数据打交道。 例如:我们处理的是学生的数据。 struct student {int id; // 学号char name[20]; // 姓名int gender; // 性别int mark; // 成绩 };学生数据使用一个结构体表示,该结构体拥有4个成员。分别为…...

【STL一】STL组件(容器、迭代器、算法)
【STL一】STL组件(容器、迭代器、算法)一、STL二、STL组件(component)1、stl六大组件2、C STL的13个头文件3、stl所有头文件三、容器(container)1、序列容器(Sequence container)——顺序容器2、关联容器&a…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...

Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...

回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...