【C++】string典型oj题

本文主要是介绍【C++】string典型oj题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

上一节我们已经仔细讲解了关于string的各种重要接口的使用：【C++】string的使用。下面我们来使用这些接口写几道OJ题。

字符串相加

415.字符串相加-力扣
在这里插入图片描述
这道题目的意思也很简单，就是想让我们模拟实现加法的过程。我们要搞清楚字符串如何相加，如何进位等一些问题即可。
我们做加法都是从个位开始依次相加，因此我们可以通过下标+[]的形式取出每个字符数，再减去’0’，既是对应的数字。

如"123"，想要取出个位数就是num[2]-‘0’，即可得到数字3。

然后就可以开始计算了。

首先定义一个串，我们知道加法的结果最多只会比位数多的再多一位，因此我们就知道需要开多少空间。
结束标志：只有当两个串的所有数字都加完后才结束
进位计算。
得到数字后进行头插（效率较低）

class Solution {
public:string addStrings(string num1, string num2) {string str;//开空间str.reserve(max(num1.size(), num2.size()) + 1);//知道两个串分别有多少位数int end1 = num1.size() - 1;int end2 = num2.size() - 1;int next = 0;//进位while(end1 >= 0 || end2 >= 0)//只有当两个串的所有数字都加完后才结束{//如果end1或者end2不大于0，证明它已经加完了，此时用0来填充int x1 = end1 >= 0 ? num1[end1--] - '0' : 0;int x2 = end2 >= 0 ? num2[end2--] - '0' : 0;int x = x1 + x2 + next;next = x/10;x = x%10;str.insert(str.begin(), x +'0');//头插，要加上'0'才是字符才能插入}
//例如9+1，它的x是0，已经插入了，但是进位next还没有加上，因此还要判断是否有多的进位没加上，如果有直接头插'1'即可。if(next == 1){str.insert(str.begin(), '1');}return str;}
};

我们知道头插的效率很低，上面代码的时间复杂度是O(n²)，因此我们建议尾插，然后逆置即可。

	{//前面代码不变//...x = x%10;str += (x + '0');}if(next == 1){str += '1';}reverse(str.begin(), str.end());//库里面已经提供好了的，在平时使用时要加上头文件#include<algorithm>return str;

字符串相乘

43.字符串相乘-力扣
在这里插入图片描述
这道题和上一道字符串相加有着异曲同工之处。

如果 num1和num2之一是 0，则直接将 0 作为结果返回即可。
如果 num1和num 2都不是 0，则可以通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。这道题中，被乘数是 num 1，乘数是num2 。

需要注意的是，num2除了最低位以外，其余的每一位的运算结果都需要补 0。
在这里插入图片描述
然后对每次得到的结果（串）进行累加，就可以使用上一题字符串相加的方法。

class Solution {
public:string addStrings(string num1, string num2) {string str;str.reserve(max(num1.size(), num2.size()) + 1);int end1 = num1.size() - 1;int end2 = num2.size() - 1;int next = 0;while(end1 >= 0 || end2 >= 0){int x1 = end1 >= 0 ? num1[end1--] - '0' : 0;int x2 = end2 >= 0 ? num2[end2--] - '0' : 0;int x = x1 + x2 + next;next = x/10;x = x%10;//str.insert(str.begin(), x +'0');str += (x + '0');}if(next == 1){//str.insert(str.begin(), '1');str += '1';}reverse(str.begin(), str.end());return str;}string multiply(string num1, string num2) {if(num1 == "0" || num2 == "0")return "0";string ans = "0";int m = num1.size();int n = num2.size();for(int i = n - 1; i >= 0; i--){string cur;for(int j = n-1; j > i; j--)cur += '0';int next = 0;//进位int y = num2.at(i) - '0';for(int j = m-1; j >= 0; j--){int x = num1[j]-'0';int product = x *y + next;next = product / 10;product = product % 10;cur += (product + '0');}if(next != 0){cur += (next + '0');}reverse(cur.begin(), cur.end());ans = addStrings(ans,cur);}return ans;}
};

字符串转换整数

8.字符串转换整数(atoi)-力扣
在这里插入图片描述

函数 myAtoi(string s) 的算法如下：
空格：读入字符串并丢弃无用的前导空格（" "）
符号：检查下一个字符（假设还未到字符末尾）为 ‘-’ 还是 ‘+’。如果两者都不存在，则假定结果为正。
转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
舍入：如果整数数超过 32 位有符号整数范围 [−2³¹, 2³¹ − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被舍入为 −2³¹ ，大于 2³¹ − 1 的整数应该被舍入为 2³¹ − 1 。
返回整数作为最终结果。

我们对题目要求依次求解即可：

对于空格，只需要用while条件判断删除即可。
对于符号，给定一个变量flag，初始化为1，判断如果有'-'，就将其置为-1，有’+‘或者没有就还是为1，有’+‘或’-'加加跳过即可。
判断是否为数字字符，如果是才能进入循环，不是则直接退出。
数字字符 - ‘0’ = 数字，数字拼接：res = res *10 +flag*(c - '0');即可得到最终数字。
数字越界处理：在每轮数字拼接前，判断res在此轮拼接后是否超过/小于 INT_MAX/INT_MIN ，若超过则直接返回INT_MAX/INT_MIN。

在这里插入图片描述

class Solution {
public:bool isdigital(char c){//判断是否是数字字符if(c >= '0' && c <= '9')return true;return false;}int myAtoi(string s) {int i = 0;int flag = 1;int res = 0;while(s[i]==' '){//去掉空格++i;}if(s[i]=='-')flag = -1;//记录负号if(s[i] == '-' || s[i] == '+')i++;int j = i;while(isdigital(s[j]) && j < s.size())//是数字字符再进循环{char c = s[j];//取出当前字符//判断越界if(res > INT_MAX /10 || (res == INT_MAX / 10 && (c-'0') > INT_MAX % 10))return INT_MAX;if(res < INT_MIN /10 || (res == INT_MIN / 10 && (c-'0') > -(INT_MIN % 10)))return INT_MIN;res = res *10 +flag*(c - '0');//拼接数字j++;}return res;}
};