LeetCode—string练习

415.字符串相加

. - 力扣（LeetCode）

错误示范：

遇到这种我们第一想法就是将字符串转化成整数，但这种解法无法提交通过，只能支持将小数字互相转化，遇到较长的字符串就没法通过。

class Solution {
public:string addStrings(string num1, string num2) {long long x = stoll(num1);//stoll将字符串转化成long long类型long long y = stoll(num2); long long z = x + y; return to_string(z);//将器转化成字符串类型}
};

思路：

解法：对两个大整数模拟「竖式加法」的过程。

我们定义两个指针 end1 和 end2 分别指向 num 1和 num 2 的末尾，即最低位，同时定义一个变量 pcur 维护当前是否有进位，然后从末尾到开头逐位相加即可。当两个数字位数不同时，这里我们在指针当前下标处于负数的时候返回 0，等价于对位数较短的数字进行了补零操作，这样就可以除去两个数字位数不同情况的处理！

代码参考：

class Solution {
public:string addStrings(string num1, string num2) {string str;int pcur = 0;int end1 = num1.size()-1,end2 = num2.size()-1;while(end1 >= 0 || end2 >= 0){ // 位数不同时用0补位// 从右向左取数int val1 = end1 < 0 ? 0 : num1[end1--] - '0';int val2 = end2 < 0 ? 0 : num2[end2--] - '0';int sum = val1 + val2 + pcur;pcur = sum / 10;//进位sum %= 10;str += (sum + '0');//加上'0'才是字符串}if(pcur == 1)//最后多出的进位{str += '1';}reverse(str.begin(),str.end());//逆置return str;}
};

HJ1 字符串最后一个单词的长度

字符串最后一个单词的长度_牛客题霸_牛客网

思路：

调用流插入cin时，流提取遇到' '空格会被自动跳过，直到遇到下一个非空白字符，遇到'\0'结束读取，所以用到 get()函数，get() 函数是 istream 类的一个成员函数，用于从输入流中读取字符，get() 函数不会自动跳过任何空白字符，包括空格和制表符。

while循环提取字符串，直到输入流读取到字符串结束符

代码：

#include <iostream>
using namespace std;int main() {string str;while(cin >> str){if(cin.get() == '\0')break;}cout << str.size() << endl;
}

125. 验证回文串

思路：

使用双指针。初始时，左右指针分别指向 s 的两侧，随后我们不断地将这两个指针相向移动，每次移动一步，并判断这两个指针指向的字符是否相同。当这两个指针相遇时，就说明 s 是回文串。

代码：

class Solution {
public:bool isLetterOrNumber(char ch){return (ch >= '0' && ch <= '9')|| (ch >= 'a' && ch <= 'z')|| (ch >= 'A' && ch <= 'Z');}bool isPalindrome(string s) {int begin = 0,end = s.size() - 1;for(auto& ch : s)//加&，在原字符串上修改,现将所有大写转化成小写{if(ch >= 'A' && ch <= 'Z'){ch += 32;}}while(begin <= end){while(begin < end && !isLetterOrNumber(s[begin])){++begin;}while(begin < end && !isLetterOrNumber(s[end])){--end;}if(s[begin++] != s[end--]){return false;}}return true;}
};

541. 反转字符串 II

思路：

我们直接按题意进行模拟：反转每个下标从 2k 的倍数开始的，长度为 k 的子串。若该子串长度不足 k，则反转整个子串。

len < i + k 时，就是剩余子串不足k；

len > i + k 时，是子串个数大于k

—> 剩余字符小于 2k 但大于或等于 k 个 / 在原字符上，字符等于2k；

代码：

class Solution {
public:string reverseStr(string s, int k) {int len = s.size();for(int i = 0; i < len ;i += 2 * k){//反转每个下标从 2k 的倍数开始的，长度为 k 的子串reverse(s.begin() + i,s.begin() + min(i + k ,len));//len < i + k 时，就是剩余子串不足k//len > i + k 时，是子串个数大于k //——> 剩余字符小于 2k 但大于或等于 k 个 / 在原字符上，字符等于2k }return s;}
};

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

思路：

开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。

代码：

class Solution {
public:string reverseWords(string s) {string tmp;//开一个新空间int len = s.length();int i = 0;while(i < len){int start = i;//刷新单词起始位置while(i < len && s[i] != ' '){//记录一个单词的长度i++;}for(int c = i - 1; c >= start ;c--){//倒序尾插tmp.push_back(s[c]);}while(i < len && s[i] == ' '){i++;tmp.push_back(' ');}}return tmp;}
};

LLCR 192. 把字符串转换成整数 (atoi)

思路1 (用long存储）:

1. 首部空格：删除之即可；
2. 符号位：三种情况，即 ''+'' , ''−'' , ''无符号" ；新建一个变量 sign 保存符号位，返回前判断正负即可；
3. 非数字字符：遇到首个非数字的字符时，应立即返回；
4. 数字字符：
（1）字符转数字： “此数字的 ASCII 码” 与 “ 0 的 ASCII 码” 相减，得到当前数字x；
（2）数字拼接：若从左向右遍历数字，设当前位字符为 c ，当前位数字为 x ，数字结果为 res ，则数字拼接公式为： res = 10 * res + x

5.考虑数据是否溢出：因为res是long类型的整形，所以在每轮数字拼接后，判断 res 在此轮拼接后是否超过 2147483647 ，若超过则加上符号位直接返回。

代码1：

class Solution {
public:int myAtoi(string str) {int i = 0,sign = 1;//默认符号是+long res = 0;while(i < str.size() && str[i] == ' ')//1.丢弃无用的前导空格{++i;}//2.考虑正负数if(str[i] == '-'){sign = -1;//更新符号++i;}else if (str[i] == '+') {i ++;}if(str[i] < '0' || str[i] > '9') // 正常数字第一位不能是0，必须为1~9之间的数字，否则就是非法数字return 0;  //3.考虑数据是否溢出for(;i < str.size() ; i++){//注意这句话要放在字符转换前if(str[i] < '0' || str[i] > '9')break;res = res * 10 + (str[i] - '0');//INT_MAX = 2^32 - 1 = 2147483647//大于等于最大值直接返回最大值if(res >= INT_MAX && sign == 1){return INT_MAX;}//INT_MIN = -2^32 = -2147483648//符号是-，且大于最大值时才能直接返回最小值(不看符号，MIN比MAX大1)if(res > INT_MAX && sign == -1){return INT_MIN;}}return sign * res;}
};

思路2 (不用long)：

该思路只有第5点与思路1不同，res此时是int类型的数据，要避免超出int范围，我们用低于int型数据长度一位的数据 border 判断是否超过int型数据的长度。在每轮数字拼接前，判断 res 在此轮拼接后是否超过 2147483647 / 10 ，若超过则加上符号位直接返回 INT_MAX或 INT_MIN 。

代码2：

class Solution {
public:int myAtoi(string str) {int i = 0,sign = 1;//默认符号是+while(i < str.size() && str[i] == ' ')//1.丢弃无用的前导空格{++i;}//2.考虑正负数if(str[i] == '-'){sign = -1;//更新符号++i;}else if (str[i] == '+') {i ++;}if(str[i] < '0' || str[i] > '9') // 正常数字第一位不能是0，必须为1~9之间的数字，否则就是非法数字return 0;  int res = 0;//此时res是int类型，要考虑数据溢出int border = INT_MAX/10;//用来验证数据是否超出int的范围//3.考虑数据是否溢出for(;i < str.size() ; i++){//注意这句话要放在字符转换前，//因为需要验证的位数比实际值的位数要少一位if(str[i] < '0' || str[i] > '9')break;//将超过最大值和低于最小值的情况都包括了if(res > border || res == border && str[i] - '0' > 7){//还没*10就大于INT_MAX/10 或//等于INT_MAX/10 并且 当前位数字大于7(INT_MAX最后一位数是7)return sign == 1 ? INT_MAX : INT_MIN;}res = res * 10 + (str[i] - '0');}return sign * res;}
};

43. 字符串相乘

思路：

如果 num 1和 num2 之一是 0，则直接将 0 作为结果返回即可。

如果 num 1和 num2 都不是 0，则可以通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。这道题中，被乘数是 num1 乘数是 num2 需要注意的是，num2 除了最低位以外，其余的每一位的运算结果都需要补0（牛逼）。

代码1：

class Solution {
public://字符串相加string addStrings(string num1, string num2) {string str;int pcur = 0;int end1 = num1.size()-1,end2 = num2.size()-1;while(end1 >= 0 || end2 >= 0){int val1 = end1 < 0 ? 0 : num1[end1--] - '0';int val2 = end2 < 0 ? 0 : num2[end2--] - '0';int sum = val1 + val2 + pcur;pcur = sum / 10;//进位sum %= 10;str += (sum + '0');}if(pcur == 1){str += '1';}reverse(str.begin(),str.end());return str;}//字符串相乘string multiply(string num1, string num2) {if(num1 == "0" || num2 == "0")//任意一个是"0"返回结果就是"0"return "0";string str1;int sign = 0;for(int i = num1.size() - 1;i >=0 ; i--){string str2;int add = 0;//对每一位的运算结果补0(除最低位外)，太吊了，但有风险性for (int j = num2.size() - 1;j > i;j--){str2.push_back('0');}int val2 = num2[i] - '0';//拆分num2从右向左乘num1for(int k = num1.size()-1;k >= 0;k--){int val1 = num1[k] - '0';//获取当前位数字int mul = val1 * val2 + add;add = mul / 10;//进位mul %= 10;//余数尾插str2 += ( mul + '0');}if(add != 0)//处理剩余的余数{str2 += (add % 10 + '0');add /= 10;}//先逆置str2，再进行错位相加reverse(str2.begin(),str2.end());str1 = addStrings(str1,str2);}return str1;}
};

代码2：（封装函数）

1. 下翻转数据

2. 按位相乘

3. 将乘得的结果进行错位相加，模拟乘法的笔算过程

class Solution
{
public:void MulItem(string& tmp, string& num1, char a){int i = 0, sign = 0;int mul = 0;while (i < num1.size()){mul = (num1[i] - '0') * (a - '0') + sign;if (mul >= 10){sign = mul / 10;mul %= 10;}elsesign = 0;tmp.push_back(mul + '0');i++;}if (sign > 0)tmp.push_back(sign + '0');}//对应为相加，sign进位采用引用传递int AddItem(int a, int b, int& sign){int add = a + b + sign;if (add >= 10){sign = 1;add -= 10;}elsesign = 0;return add;}//错位相加void MoveAdd(string& result, string& tmp, int k){int i, j;i = k;j = 0;int sign = 0;while (i < result.size() && j < tmp.size()){result[i] = AddItem(result[i] - '0', tmp[j] - '0', sign) + '0';i++;j++;}while (i < result.size() && sign){result[i] = AddItem(result[i] - '0', 0, sign) + '0';i++;}while (j < tmp.size()){int v = AddItem(0, tmp[j] - '0', sign);result.push_back(v + '0');j++;}if (sign)result.push_back(sign + '0');}string multiply(string num1, string num2){//先翻转数据，方便进位处理reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());string tmp, result;for (int i = 0; i < num2.size(); ++i){//使用num2的每一个数据乘以num1MulItem(tmp, num1, num2[i]);//将乘得的结果进行错位相加MoveAdd(result, tmp, i);tmp.clear();}while (result.size() != 1 && result.back() == '0')result.pop_back();//翻转数据，恢复数据reverse(result.begin(), result.end());return result;}
};