【C++】string OJ练习——字符串最后一个单词的长度+字符串相加
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;
}
};
🆗，这篇文章就到这里，欢迎大家指正！！！
- 点赞
- 收藏
- 关注作者
评论（0）