字符串相乘

題面

力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長(zhǎng)平臺(tái)

給定兩個(gè)以字符串形式表示的非負(fù)整數(shù) num1 和 num2，返回 num1 和 num2 的乘積，它們的乘積也表示為字符串形式。

注意：不能使用任何內(nèi)置的 BigInteger 庫(kù)或直接將輸入轉(zhuǎn)換為整數(shù)。

示例 1:

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

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

錯(cuò)誤記錄

我一開始的思路是：先把倆字符串轉(zhuǎn)化成整數(shù)，然后相乘，結(jié)果再轉(zhuǎn)化成字符串返回回去。然后掙扎了很久，每次測(cè)試都沒問(wèn)題，一提交就報(bào)錯(cuò)。后來(lái)我仔細(xì)看了下題面，發(fā)現(xiàn)人家早就說(shuō)明了：“不能使用任何內(nèi)置的 BigInteger 庫(kù)或直接將輸入轉(zhuǎn)換為整數(shù)?！?/p>

所以這道題要的就是你去模擬乘法的計(jì)算過(guò)程，并且計(jì)算過(guò)程的數(shù)字要以字符的形式存進(jìn)string中。

Way1 拆分成“先乘后加”

思路

現(xiàn)在目的明確，完成兩個(gè)Part：

1.遍歷兩個(gè)字符串，將整個(gè)的乘法拆分成一部分一部分的乘積。

2.將這些乘積相加，即寫一個(gè)字符串相加的函數(shù)。

實(shí)現(xiàn)

class Solution {
public:string multiply(string num1, string num2) {if(num1=="0"||num2=="0"){ ? //如果有一個(gè)被乘數(shù)是0，那結(jié)果直接返回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; ?  //用于保存進(jìn)位for(int j=n2-1;j>=0;j--){int tmp=(num1[i]-'0')*(num2[j]-'0')+add_num;int present_num=tmp%10; ? ? //當(dāng)前位ret.insert(ret.begin(),present_num+'0');add_num=tmp/10;}if(add_num){ ? ?  //如果還有剩余的add_num，別忘了進(jìn)位 ?ret.insert(ret.begin(),add_num+'0');}int add_num_of_zero=n1-1-i; ? //補(bǔ)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){ ? //這里字符串相加 采用的是補(bǔ)0的思路，很實(shí)用int n1=s1.size(),n2=s2.size();string StrRet;//通過(guò)在前面補(bǔ)0的方法，讓n1和n2位數(shù)對(duì)齊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，別忘了進(jìn)位StrRet.insert(StrRet.begin(),add_num+'0');}return StrRet;}
};

時(shí)空復(fù)雜度分析

時(shí)間復(fù)雜度為O(n1*n2)，其中n1、n2分別是num1、num2的長(zhǎng)度。

空間復(fù)雜度O(1)

反思

1.每次循環(huán)開始前 ，別忘了刷新變量！要再設(shè)回初始值。

2.字符串相加，用補(bǔ)0的思路，很好用。先將倆字符串的位數(shù) 用0補(bǔ)得整齊，后面就很好計(jì)算了。

3.最常犯的錯(cuò)誤是：沒把數(shù)字轉(zhuǎn)化成askii碼存進(jìn)字符串

for(int i=n1-1;i>=0;i--){int tmp=AddNum+(s1[i]-'0')+(s2[i]-'0');ret.insert(ret.begin(),tmp%10); ? //應(yīng)為tmp%10+'0'AddNum=tmp/10;}

4.這個(gè)思路的亮點(diǎn)在于 拆分成先乘后加 和 補(bǔ)0。

Way2 用數(shù)組

思路

1.開大小為n1+n2的數(shù)組（記得初始化為0）。

因?yàn)閮蓴?shù)相乘，乘積的位數(shù) 是不會(huì)超過(guò) 被乘數(shù)的位數(shù)之和的，所以這個(gè)大小一定夠用了。

2.從右往左遍歷被乘數(shù)的每個(gè)位數(shù)，結(jié)果挨個(gè)放進(jìn)數(shù)組里。

3.把數(shù)組的數(shù)存進(jìn)字符串，同時(shí)要考慮進(jìn)位。

實(shí)現(xiàn)

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;}
?//把數(shù)組內(nèi)容存進(jìn)字符串string ret;int AddNum=0;for(int i=NumArr-1;i>=0;i--){//進(jìn)位AddNum=arr[i]/10;if(i>0){arr[i-1]+=AddNum; ?  //這里要小心，i-1是很容易越界的！所以要加個(gè)條件判斷 }
?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;}
};

時(shí)空復(fù)雜度分析

時(shí)間復(fù)雜度為O(n1*n2+n1+n2)，n1、n2分別為num1、num2的大小

空間復(fù)雜度為O(n1+n2)

翻轉(zhuǎn)字符串III：翻轉(zhuǎn)字符串中的單詞

題面

力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長(zhǎng)平臺(tái)

給定一個(gè)字符串 s ，你需要反轉(zhuǎn)字符串中每個(gè)單詞的字符順序，同時(shí)仍保留空格和單詞的初始順序。

示例 1：

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

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

錯(cuò)誤記錄

第一次寫的時(shí)候，報(bào)執(zhí)行出錯(cuò)，修改了好久，也沒發(fā)現(xiàn)錯(cuò)誤：

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;}
};

報(bào)錯(cuò)：

后來(lái)終于揪出來(lái)BUG了，在這里：

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

當(dāng)string的大小是偶數(shù)個(gè)時(shí)，!= 會(huì)導(dǎo)致left和right剛好錯(cuò)過(guò)。

果然是細(xì)節(jié)決定成敗！！

思路1 遍歷找單詞

這題的思路蠻簡(jiǎn)單的：遍歷一遍字符串，遇到單詞，就把整個(gè)單詞swap一下。

至于怎么找到單詞？

可以通過(guò)空格的位置來(lái)劃分單詞。也可以遍歷的時(shí)候記錄下單詞的起始位置。這兩種找單詞的方法都來(lái)實(shí)現(xiàn)一下。

實(shí)現(xiàn)

這種思路下的兩種實(shí)現(xiàn)方式：

第一種：

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; ?}}//處理下最后一個(gè)詞if(front_i!=0){front_i+=1;}swap(s,front_i,num-1);return s;}
};

第二種：這種方法我第一次沒寫出來(lái)，那個(gè)循環(huán)給我繞暈了。這種方法挺好的，得多寫幾遍！！！

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]!=' '){ ? //注意看這個(gè)循環(huán)條件！！要加上i<num，保證安全i++;} ?//當(dāng)出了循環(huán)，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;}
};

反思：

第二種思路我當(dāng)時(shí)沒寫出來(lái)，問(wèn)題就出在那個(gè)大循環(huán)while(i<num){}里，我當(dāng)時(shí)一上來(lái)就把框架搭好了：

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

這個(gè)框架太經(jīng)典了，結(jié)果限制住了我的思路。實(shí)際上，我不應(yīng)該先把i++;寫上的，后面得把這個(gè)循環(huán)多寫幾遍，多體會(huì)一下。

然后就是要注意，大while()里包小while()，小while()加上大while()的判斷條件，會(huì)更安全，不容易越界。

思路2 暴力解法

思路1里，我們是手動(dòng)翻轉(zhuǎn)字符串的，但實(shí)際上可以直接用庫(kù)里的reverse、find函數(shù)。

思路2則不用遍歷字符串的每一個(gè)字符，而是用find找到空格，，然后從空格的后一個(gè) 接著去找 下一個(gè)空格。

當(dāng)沒有空格時(shí)，說(shuō)明是最后一個(gè)單詞，翻轉(zhuǎn)，然后break跳出循壞。

注意，這種寫法，循環(huán)里也沒有經(jīng)典的"i++;"，所以不要一寫循環(huán)就把i++;給添上，不要 被習(xí)慣限制住思路！

實(shí)現(xiàn)

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);  //因?yàn)槭菑膇開始找的，所以要加ii=pos+1; ? ? ? ? ? ? ? ? ? ? ? ? ? //現(xiàn)在要從空格的下一位開始找} ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //注意reverse是左閉右開，右邊是開區(qū)間else{reverse(s.begin()+i,s.end()); ? //沒有空格了，說(shuō)明這已經(jīng)是最后一個(gè)單詞了break;}}return s;}
};