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了,不需要就是0
ret%=10;
retStr.insert(0,1,'0'+ret);//头插到新string
}
//最后有可能有1+9的情况,现在只会有0
if(next==1)
{
retStr.insert(0,1,'1');
}
return retStr;
}
};
思路1
- 首先,定义两个指针 index1 和 index2 分别指向两个输入字符串的最后一位,用来从后往前遍历字符串。
- 然后定义一个变量 next 用来表示进位,初始化为 0。
- 接下来使用一个循环来遍历两个字符串,直到 index1 和 index2 都小于 0。在循环中,每次取出 index1 和 index2 对应位置的数字,并将它们与进位相加,得到一个临时的结果 ret。
- 然后更新进位 next 为 ret/10,并将 ret%10 插入到需要返回的字符串 retStr 的开头。
- 循环结束后,还需要检查最后是否有进位,如果有,需要将进位插入到结果字符串的开头。
但此时还是有一个问题的,那就是效率低(因为头插时间复杂度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了,不需要就是0
ret%=10;
//使用尾插效率更好,尾插有append,这里我们使用+=
retStr+='0'+ret;
}
//最后有可能有1+9的情况,现在只会有0
if(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
-
遍历输入字符串 s 中的每个字符 e。
如果字符 e 是字母或数字,则根据题目要求将大写字母转换为小写字母,并将其添加到新的字符串 re 中。 -
创建一个新的字符串 modified,它是字符串 re 的一个副本。
-
反转字符串 re。
-
比较反转后的字符串 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
- 创建一个辅助函数 isLetterOrNumber,用于判断一个字符是否是字母或数字。
- 遍历输入字符串 s 中的每个字符 e,将大写字母转换为小写字母。
- 初始化两个指针 begin 和 end,分别指向字符串的开头和结尾。
- 在一个 while 循环中,不断移动指针 begin 和 end,直到两个指针相遇。
在移动指针的过程中,跳过非字母和数字的字符。 - 在二者都是数字或者字母后,比较指针指向的字符,如果不相等,则返回 false,表示不是回文字符串;如果相等,则继续移动指针。
- 如果循环结束后都没有返回 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
总体思路是找到单词的左和右索引,在这个区间内进行翻转
- 利用一个
i
对字符串进行遍历,pos来储存找到的' '
的下标 - 那么从i到pos就是一个单词加上’ ',正好满足
reserve()函数
左闭右开的性质 - 然后
i=pos+1
(跳到空格后) - 如果没找到空格,就说明只剩下一个,或者只有一个单词。 就直接
i
到end()
进行翻转了
代码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文章来源:https://www.toymoban.com/news/detail-819175.html
今天就到这里啦!文章来源地址https://www.toymoban.com/news/detail-819175.html
到了这里,关于c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!