前言
本篇博客主要记录string类的相关oj题,后续会持续更新,题目为入门基础题,目的是帮助初学string类的友友们熟悉使用string类.
题目包含:字符串最后一个单词的长度、 2.反转字符串 II、字符串相加
一、字符串最后一个单词的长度
题目来源于:牛客
题目链接:传送门
1.1 题目介绍
计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）
输入描述：
输入一行，代表要计算的字符串，非空，长度小于5000。
输出描述：
输出一个整数，表示输入字符串最后一个单词的长度。
示例1:
输入：
hello nowcoder
输出：
8
说明：
最后一个单词为nowcoder，长度为8
1.2 解题思路:
1.创建一个string类对象input.
2.通过getline函数获取带有空格的字符串.
3.通过遍历这个字符串,进行计数,途中遇到空格就将num清零.(因为表示不是最后一个单词)
4.最后返回num即可.
1.3 题目代码
#include <iostream> using namespace std; int main() { string input; getline(cin, input);//获取一行字符串 int num=0;//记录单词的长度 for(int i=0;i<input.size();i++) { if(input[i]==' ')num=0;//每次遇到空格都清零 else num++; } cout<<num<<endl; return 0; }
方法二:
1.从后往前遍历,遇到第一个空格,则表示最后一个单词结束,即返回长度.
#include <iostream> using namespace std; int main() { string input; getline(cin, input);//获取行 int num=0; for(int i=input.size()-1;i>=0;i--) { if(input[i]==' ')break; num++; } cout<<num<<endl; return 0; }
知识点:
1.getline函数可以获取带有空格的字符串.
2.string对象的长度通过调用对象的size()函数获得.
二、反转字符串 II
题目来源于:力扣
题目链接:传送门
2.1 题目介绍
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
● 如果剩余字符少于 k 个，则将剩余字符全部反转。
● 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例1:
输入：s = “abcdefg”, k = 2 输出：“bacdfeg”
示例2:
输入：s = “abcd”, k = 2 输出：“bacd”
2.2 解题思路
1.遍历string类对象,每次走到2k的倍数时,反转前k个字符.
2.当剩下的字符串不足k个的时候,反转剩下的所有字符.
2.3 题目代码:
class Solution { public: string reverseStr(string s, int k) { int n = s.size(); for (int i = 0; i < n; i += 2 * k) { if(i+k>n)//剩余字符串不足k { reverse(s.begin() + i ,s.begin()+n);//反转剩下的所有字符 } else reverse(s.begin() + i, s.begin() +i+k);反转前k个字符 } return s; } };
知识点:
1.begin()用于返回string对象的起始位置.
2.reverse函数可以用于实现反转,reverse(开始位置,结束位置);
三、字符串相加
题目来源于:力扣
题目链接:传送门
3.1 题目介绍
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：
输入：num1 = “11”, num2 = “123” 输出：“134”
示例 2：
输入：num1 = “456”, num2 = “77” 输出：“533”
示例 3：
输入：num1 = “0”, num2 = “0” 输出：“0”
3.2 解题思路:
1.从后往前同时遍历这两个string类对象.
2.计算两个对象的和,用carry 记录是否需要进位.
3.将和的结果尾插入sum对象(用于保存最后的和的输出结果).
4.(1)如果对象1没有走完,对象2已经走完,则对象1剩余部分+进位继续处理尾插入sum对象.
(2)如果对象2没有走完,对象1已经走完,则对象2剩余部分+进位继续处理尾插入sum对象.
5.细节处理:最后一个数也可能进位,例如99+1=100.
6.将计算结果反转.
为何要反转?
因为计算结果是尾插进入sum对象的,那为啥非要尾插呢?头插不行吗?
学过顺序表的友友们应该知道:
1.尾插:顺序表的尾插的效率极高,时间复杂度是O(1);
2.头插,顺序表的头插效率极低,时间复杂度是O(n);.
进位数说明:
题目要求一个结点只能存个位数,所以需要保留进位数到下一个结点.
算进位数:
这是很基本的数学问题,两数相加,大于10的部分需要进位.
3.3 题目代码:
class Solution { public: string addStrings(string num1, string num2) { int carry = 0; string sum; //分别获取两个对象最后一个字符的小标位置 int end1 = num1.size() - 1; int end2 = num2.size() - 1; while (end1>=0 && end2>=0) { int num = num1[end1--] - '0' + num2[end2--] - '0' + carry; //处理进制 carry = num / 10; //只保留个位数 num %= 10; //将和的结果尾插入sum对象 sum.push_back(num + '0'); } //如果对象1没有走完 while (end1>=0) { int num = num1[end1--] - '0' + carry; //处理进制 carry = num / 10; //只保留个位数 num %= 10; sum.push_back(num + '0'); } //如果对象2没有走完 while (end2>=0) { int num = num2[end2--] - '0' + carry; //处理进制 carry = num / 10; //只保留个位数 num %= 10; sum.push_back(num + '0'); } //最后一个位是否需要进位 if(carry==1) { sum.push_back('1'); } //将最终结果反转 reverse(sum.begin(), sum.end()); return sum; } };
优化版本(推荐写法)
建议画图分析:
class Solution { public: string addStrings(string num1, string num2) { int carry = 0; string sum; //计算最后一个字符的下标 int end1 = num1.size() - 1; int end2 = num2.size() - 1; while (end1 >= 0 || end2 >= 0) { //谁短,谁就为'0' char s1 = end1 >= 0 ? num1[end1] : '0'; char s2 = end2 >= 0 ? num2[end2] : '0'; int num = s1-'0' + s2-'0' + carry; //处理进制 carry = num / 10; //只保留个位数 num %= 10; sum.push_back(num + '0'); end1--; end2--; } //防止最后一个字符的进位问题 if (carry == 1) { sum.push_back('1'); } //最后反转字符串 reverse(sum.begin(), sum.end()); return sum; } };
好的,初次接触string类的友友们注意多加练习,刷完这些题目以后,对string类的使用是不是更加熟悉了呢?
