字符串相乘

題面

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

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

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

示例 1:

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

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

錯誤記錄

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

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

Way1 拆分成“先乘后加”

思路

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

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

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

實現(xiàn)

class Solution {
public:string multiply(string num1, string num2) {if(num1=="0"||num2=="0"){ ? //如果有一個被乘數(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; ?  //用于保存進位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，別忘了進位 ?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位數(shù)對齊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;}
};

時空復(fù)雜度分析

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

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

反思

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

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

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

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.這個思路的亮點在于 拆分成先乘后加 和 補0。

Way2 用數(shù)組

思路

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

因為兩數(shù)相乘，乘積的位數(shù) 是不會超過 被乘數(shù)的位數(shù)之和的，所以這個大小一定夠用了。

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

3.把數(shù)組的數(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)容存進字符串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;}
};

時空復(fù)雜度分析

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

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

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

題面

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

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

示例 1：

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

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

錯誤記錄

第一次寫的時候，報執(zhí)行出錯，修改了好久，也沒發(fā)現(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; ?}}return s;}
};

報錯：

后來終于揪出來BUG了，在這里：

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

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

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

思路1 遍歷找單詞

這題的思路蠻簡單的：遍歷一遍字符串，遇到單詞，就把整個單詞swap一下。

至于怎么找到單詞？

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

實現(xiàn)

這種思路下的兩種實現(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; ?}}//處理下最后一個詞if(front_i!=0){front_i+=1;}swap(s,front_i,num-1);return s;}
};

第二種：這種方法我第一次沒寫出來，那個循環(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]!=' '){ ? //注意看這個循環(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)時沒寫出來，問題就出在那個大循環(huán)while(i<num){}里，我當(dāng)時一上來就把框架搭好了：

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

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

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

思路2 暴力解法

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

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

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

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

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