【string题解 C++】字符串相乘 | 翻转字符串III：翻转单词

字符串相乘

题面

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3" 输出: "6" 示例 2:

输入: num1 = "123", num2 = "456" 输出: "56088"

错误记录

我一开始的思路是：先把俩字符串转化成整数，然后相乘，结果再转化成字符串返回回去。然后挣扎了很久，每次测试都没问题，一提交就报错。后来我仔细看了下题面，发现人家早就说明了：“不能使用任何内置的 BigInteger 库或直接将输入转换为整数。”

所以这道题要的就是你去模拟乘法的计算过程，并且计算过程的数字要以字符的形式存进string中。

Way1 拆分成“先乘后加”

思路

现在目的明确，完成两个Part：

1.遍历两个字符串，将整个的乘法拆分成一部分一部分的乘积。

2.将这些乘积相加，即写一个字符串相加的函数。

实现

class Solution {
public:string multiply(string num1, string num2) {if(num1=="0"||num2=="0"){   //如果有一个被乘数是0，那结果直接返回0return "0";}int n1=num1.size(),n2=num2.size();   string ret,combine_ret;for(int i=n1-1;i>=0;i--){   //每次都要把上一次的更新一下ret.clear();int add_num=0;    //用于保存进位for(int j=n2-1;j>=0;j--){int tmp=(num1[i]-'0')*(num2[j]-'0')+add_num;int present_num=tmp%10;     //当前位ret.insert(ret.begin(),present_num+'0');add_num=tmp/10;}if(add_num){      //如果还有剩余的add_num，别忘了进位  ret.insert(ret.begin(),add_num+'0');}int add_num_of_zero=n1-1-i;   //补0while(add_num_of_zero){ret.push_back('0');add_num_of_zero--;}combine_ret=addString(combine_ret,ret);}return combine_ret;}string addString(string s1,string s2){   //这里字符串相加 采用的是补0的思路，很实用int n1=s1.size(),n2=s2.size();string StrRet;//通过在前面补0的方法，让n1和n2位数对齐while(n1>n2){s2.insert(s2.begin(),'0');n2++;}while(n2>n1){s1.insert(s1.begin(),'0');n1++;}
​int add_num=0;for(int i=n1-1;i>=0;i--){int tmp=(s1[i]-'0')+(s2[i]-'0')+add_num;add_num=tmp/10;StrRet.insert(StrRet.begin(),tmp%10+'0');}if(add_num){       //如果还有剩余的add_num，别忘了进位StrRet.insert(StrRet.begin(),add_num+'0');}return StrRet;}
};

时空复杂度分析

时间复杂度为O(n1*n2)，其中n1、n2分别是num1、num2的长度。

空间复杂度O(1)

反思

1.每次循环开始前 ，别忘了刷新变量！要再设回初始值。

2.字符串相加，用补0的思路，很好用。先将俩字符串的位数 用0补得整齐，后面就很好计算了。

3.最常犯的错误是：没把数字转化成askii码存进字符串

for(int i=n1-1;i>=0;i--){int tmp=AddNum+(s1[i]-'0')+(s2[i]-'0');ret.insert(ret.begin(),tmp%10);   //应为tmp%10+'0'AddNum=tmp/10;}

4.这个思路的亮点在于 拆分成先乘后加 和 补0。

Way2 用数组

思路

1.开大小为n1+n2的数组（记得初始化为0）。

因为两数相乘，乘积的位数 是不会超过 被乘数的位数之和的，所以这个大小一定够用了。

2.从右往左遍历被乘数的每个位数，结果挨个放进数组里。

3.把数组的数存进字符串，同时要考虑进位。

实现

class Solution {
public:string multiply(string num1, string num2) {if(num1=="0"||num2=="0"){return "0";}int n1=num1.size(),n2=num2.size();int NumArr=n1+n2;int*arr=new int[NumArr]();  //注意这种写法 可以初始化为0
​int k=NumArr-1;for(int i=n1-1;i>=0;i--){int CopyK=k;     for(int j=n2-1;j>=0;j--){int tmp=(num1[i]-'0')*(num2[j]-'0');arr[k--]+=tmp;}k=CopyK-1;}
​//把数组内容存进字符串string ret;int AddNum=0;for(int i=NumArr-1;i>=0;i--){//进位AddNum=arr[i]/10;if(i>0){arr[i-1]+=AddNum;    //这里要小心，i-1是很容易越界的！所以要加个条件判断 }
​ret.insert(ret.begin(),arr[i]%10+'0');}if(AddNum){ret.insert(ret.begin(),AddNum+'0');}delete[] arr;for(int i=0;i<NumArr;i++){if(ret[i]!='0'){return ret.substr(i);}}return ret;}
};

时空复杂度分析

时间复杂度为O(n1*n2+n1+n2)，n1、n2分别为num1、num2的大小

空间复杂度为O(n1+n2)

翻转字符串III：翻转字符串中的单词

题面

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1：

输入：s = "Let's take LeetCode contest" 输出："s'teL ekat edoCteeL tsetnoc" 示例 2:

输入： s = "God Ding" 输出："doG gniD"

错误记录

第一次写的时候，报执行出错，修改了好久，也没发现错误：

class Solution {
public:void swap(string& s,int left,int right){while(left!=right){std::swap(s[left],s[right]);left++;right--;}}string reverseWords(string s) {int num=s.size();int front_i=0;for(int i=0;i<num;i++){if(s[i]==' '){if(front_i!=0){front_i+=1;}swap(s,front_i,i-1);front_i=i;  }}return s;}
};

报错：

后来终于揪出来BUG了，在这里：

void swap(string& s,int left,int right){while(left!=right){       //这里不能用!=，得用<std::swap(s[left],s[right]);left++;right--;}}

当string的大小是偶数个时，!= 会导致left和right刚好错过。

果然是细节决定成败！！

思路1 遍历找单词

这题的思路蛮简单的：遍历一遍字符串，遇到单词，就把整个单词swap一下。

至于怎么找到单词？

可以通过空格的位置来划分单词。也可以遍历的时候记录下单词的起始位置。这两种找单词的方法都来实现一下。

实现

这种思路下的两种实现方式：

第一种：

class Solution {
public:void swap(string& s,int left,int right){while(left<right){std::swap(s[left],s[right]);left++;right--;}}string reverseWords(string s) {int num=s.size();int front_i=0;for(int i=0;i<num;i++){if(s[i]==' '){      //找到空格的位置if(front_i!=0){front_i+=1;}swap(s,front_i,i-1);front_i=i;  }}//处理下最后一个词if(front_i!=0){front_i+=1;}swap(s,front_i,num-1);return s;}
};

第二种：这种方法我第一次没写出来，那个循环给我绕晕了。这种方法挺好的，得多写几遍！！！

class Solution {
public:string reverseWords(string s) {int num=s.size();int i=0;while(i<num){int start=i;while(i<num&&s[i]!=' '){   //注意看这个循环条件！！要加上i<num，保证安全i++;}  //当出了循环，str[i]就是空格int left=start;int right=i-1;while(left<right){swap(s[left],s[right]);left++;right--;}
​while(i<num&&s[i]==' '){  i++;}}return s;}
};

反思：

第二种思路我当时没写出来，问题就出在那个大循环while(i<num){}里，我当时一上来就把框架搭好了：

while(i<num)
{i++;
}

这个框架太经典了，结果限制住了我的思路。实际上，我不应该先把i++;写上的，后面得把这个循环多写几遍，多体会一下。

然后就是要注意，大while()里包小while()，小while()加上大while()的判断条件，会更安全，不容易越界。

思路2 暴力解法

思路1里，我们是手动翻转字符串的，但实际上可以直接用库里的reverse、find函数。

思路2则不用遍历字符串的每一个字符，而是用find找到空格，，然后从空格的后一个 接着去找 下一个空格。

当没有空格时，说明是最后一个单词，翻转，然后break跳出循坏。

注意，这种写法，循环里也没有经典的"i++;"，所以不要一写循环就把i++;给添上，不要 被习惯限制住思路！

实现

class Solution {
public:string reverseWords(string s) {int num=s.size();int i=0;while(i<num){size_t pos=s.find(' ',i);   //注意这里用size_tif(pos!=string::npos){reverse(s.begin()+i,s.begin()+pos);  //因为是从i开始找的，所以要加ii=pos+1;                           //现在要从空格的下一位开始找}                                     //注意reverse是左闭右开，右边是开区间else{reverse(s.begin()+i,s.end());   //没有空格了，说明这已经是最后一个单词了break;}}return s;}
};