c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III)

本文主要是介绍c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1. 415. 字符串相加
    • 题目详情
    • 代码1
    • 思路1
    • 代码2
    • 思路2
  • 2. 125. 验证回文串
    • 题目详情
    • 代码1(按照要求修改后放到新string里)
    • 思路1
    • 代码2(利用双指针/索引)
    • 思路2
  • 3. 541. 反转字符串 II
    • 题目详情
    • 代码1
    • 思路1
  • 4. 557. 反转字符串中的单词 III
    • 题目详情
    • 代码1(利用find)
    • 思路1
    • 代码2(利用双指针)
    • 思路2

1. 415. 字符串相加

传送门

题目详情

在这里插入图片描述

代码1

class Solution {
public:string addStrings(string num1, string num2) {int index1=num1.size()-1,index2=num2.size()-1;//找到最后一位int next=0;//进位string retStr;while(index1>=0||index2>=0)//还有一个没完就要进来:有可能一直进位{int val1=0,val2=0; if(index1>=0){val1=num1[index1--]-'0';}if(index2>=0){val2=num2[index2--]-'0';}int ret=next+val1+val2;//两者相加后加上进位数next=ret/10;//需要进位就是1了,不需要就是0ret%=10;retStr.insert(0,1,'0'+ret);//头插到新string}//最后有可能有1+9的情况,现在只会有0if(next==1){retStr.insert(0,1,'1');}return retStr;}
};

思路1

  1. 首先,定义两个指针 index1 和 index2 分别指向两个输入字符串的最后一位,用来从后往前遍历字符串。
  2. 然后定义一个变量 next 用来表示进位,初始化为 0。
  3. 接下来使用一个循环来遍历两个字符串,直到 index1 和 index2 都小于 0。在循环中,每次取出 index1 和 index2 对应位置的数字,并将它们与进位相加,得到一个临时的结果 ret。
  4. 然后更新进位 next 为 ret/10,并将 ret%10 插入到需要返回的字符串 retStr 的开头。
  5. 循环结束后,还需要检查最后是否有进位,如果有,需要将进位插入到结果字符串的开头。

但此时还是有一个问题的,那就是效率低(因为头插时间复杂度O(N^2));

代码2

class Solution {
public:string addStrings(string num1, string num2) {int index1=num1.size()-1,index2=num2.size()-1;//找到最后一位int next=0;//进位string retStr;while(index1>=0||index2>=0)//还有一个没完就要进来:有可能一直进位{int val1=0,val2=0; if(index1>=0){val1=num1[index1--]-'0';}if(index2>=0){val2=num2[index2--]-'0';}int ret=next+val1+val2;//两者相加后加上进位数next=ret/10;//需要进位就是1了,不需要就是0ret%=10;//使用尾插效率更好,尾插有append,这里我们使用+=retStr+='0'+ret;}//最后有可能有1+9的情况,现在只会有0if(next==1){retStr+='1';}reverse(retStr.begin(),retStr.end());//尾插后,最后翻转一下return retStr;}
};

思路2

整体思路都是一样的,只不过有头插换成了尾插+翻转

2. 125. 验证回文串

传送门

题目详情

在这里插入图片描述

代码1(按照要求修改后放到新string里)

class Solution {
public:bool isPalindrome(string s) {string re;for(auto e:s)//按照要求修改好{if((e>='A'&&e<='Z')||(e>='a'&&e<='z')||(e>='0'&&e<='9')){if(e>='A'&&e<='Z'){re+=(e+32);}else{re+=e;}}}string modified(re);reverse(re.begin(),re.end());       //看看是否相同for(int i=0;i<modified.size();i++){if(re[i]!=modified[i]){return false;}}return true;}

思路1

  1. 遍历输入字符串 s 中的每个字符 e。
    如果字符 e 是字母或数字,则根据题目要求将大写字母转换为小写字母,并将其添加到新的字符串 re 中。

  2. 创建一个新的字符串 modified,它是字符串 re 的一个副本。

  3. 反转字符串 re。

  4. 比较反转后的字符串 re 和副本字符串 modified,如果它们不相等,则返回 false,表示不是回文字符串;如果它们相等,则返回 true,表示是回文字符串

代码2(利用双指针/索引)

bool isLetterOrNumber(char ch)
{return (ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')||(ch>='0'&&ch<='9');
}class Solution {
public:bool isPalindrome(string s) {for(auto& e:s)//大的变小的{if(e>='A'&&e<='Z'){e+=32;}}int begin=0;int end=s.size()-1;while(begin<end){while(begin<end&&!isLetterOrNumber(s[begin])){begin++;}while(begin<end&&!isLetterOrNumber(s[end])){--end;}if(s[begin]!=s[end]){return false;}else{++begin;--end;}}return true;}
};

思路2

  1. 创建一个辅助函数 isLetterOrNumber,用于判断一个字符是否是字母或数字。
  2. 遍历输入字符串 s 中的每个字符 e,将大写字母转换为小写字母。
  3. 初始化两个指针 begin 和 end,分别指向字符串的开头和结尾。
  4. 在一个 while 循环中,不断移动指针 begin 和 end,直到两个指针相遇。
    在移动指针的过程中,跳过非字母和数字的字符。
  5. 在二者都是数字或者字母后,比较指针指向的字符,如果不相等,则返回 false,表示不是回文字符串;如果相等,则继续移动指针。
  6. 如果循环结束后都没有返回 false,则说明是回文字符串,返回 true。

3. 541. 反转字符串 II

传送门

题目详情

在这里插入图片描述

代码1

class Solution {
public:string reverseStr(string s, int k) {int len=s.size();for(int i=0;i<len;i+=2*k){if(i+k<=len)//剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符//同时前面的2k区域不用管,直接满足,只有最后那个不够2k的区间才讨论{reverse(s.begin()+i,s.begin()+i+k);}else{reverse(s.begin()+i,s.begin()+len);}}return s;}
};

思路1

利用每次要跳2k来处理:就直接i+=2k,这样每次直接跳到下一个区间,前面够2k的不用管,直接满足i+k<=len,只有那最后一个不够2k的需要讨论(毕竟s.begin()+len是最后元素的下个位置)

4. 557. 反转字符串中的单词 III

传送门

题目详情

在这里插入图片描述

代码1(利用find)

class Solution {
public:string reverseWords(string s) {size_t pos=0;int i=0;while(i<s.size()){pos=s.find(' ',i);if(pos==string::npos)//只有一个单词了{reverse(s.begin()+i,s.end());break;}reverse(s.begin()+i,s.begin()+pos);i=(pos+1);}return s;}
};

思路1

总体思路是找到单词的左和右索引,在这个区间内进行翻转

  1. 利用一个i 对字符串进行遍历,pos来储存找到的' '的下标
  2. 那么从i到pos就是一个单词加上’ ',正好满足reserve()函数左闭右开的性质
  3. 然后i=pos+1(跳到空格后)
  4. 如果没找到空格,就说明只剩下一个,或者只有一个单词。 就直接iend()进行翻转了

代码2(利用双指针)

class Solution {
public:string reverseWords(string s) {int i=0;while(i<s.size())//直接进循环{int left=i;//存一下起始位置while(i<s.size()&&s[i]!=' ')//找空格{i++;}//现在要么找到了,要么到size处了int right=i-1;while(left<right)//开始换{swap(s[left],s[right]);left++;right--;}if(s[i]==' '){i++;}}return s;}
};

思路2

总体思路是一样的,不过自己找,没有利用find


今天就到这里啦!

这篇关于c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/637684

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

sqlite3 相关知识

WAL 模式 VS 回滚模式 特性WAL 模式回滚模式(Rollback Journal)定义使用写前日志来记录变更。使用回滚日志来记录事务的所有修改。特点更高的并发性和性能;支持多读者和单写者。支持安全的事务回滚,但并发性较低。性能写入性能更好,尤其是读多写少的场景。写操作会造成较大的性能开销,尤其是在事务开始时。写入流程数据首先写入 WAL 文件,然后才从 WAL 刷新到主数据库。数据在开始

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)