目錄
字符串相乘
題面
錯(cuò)誤記錄
Way1 拆分成“先乘后加”
思路
實(shí)現(xiàn)
時(shí)空復(fù)雜度分析
反思
Way2 用數(shù)組
思路
實(shí)現(xiàn)
時(shí)空復(fù)雜度分析
翻轉(zhuǎn)字符串III：翻轉(zhuǎn)字符串中的單詞
題面
錯(cuò)誤記錄
思路1 遍歷找單詞
實(shí)現(xiàn)
思路2 暴力解法
實(shí)現(xiàn)
字符串相乘
題面
力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長平臺(tái)
難度：中等（實(shí)際上我覺得這道題難死了。。。）
給定兩個(gè)以字符串形式表示的非負(fù)整數(shù) num1 和 num2，返回 num1 和 num2 的乘積，它們的乘積也表示為字符串形式。
注意：不能使用任何內(nèi)置的 BigInteger 庫或直接將輸入轉(zhuǎn)換為整數(shù)。
示例 1:
輸入: num1 = "2", num2 = "3"
輸出: "6"示例 2:
輸入: num1 = "123", num2 = "456"
輸出: "56088"錯(cuò)誤記錄
我一開始的思路是：先把倆字符串轉(zhuǎn)化成整數(shù)，然后相乘，結(jié)果再轉(zhuǎn)化成字符串返回回去。然后掙扎了很久，每次測試都沒問題，一提交就報(bào)錯(cuò)。后來我仔細(xì)看了下題面，發(fā)現(xiàn)人家早就說明了：“不能使用任何內(nèi)置的 BigInteger 庫或直接將輸入轉(zhuǎn)換為整數(shù)?！?/p>
所以這道題要的就是你去模擬乘法的計(jì)算過程，并且計(jì)算過程的數(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é)果直接返回0
? ? ? ? ? return "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ǔ)0
? ? ? ? ? while(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;
? ? ? //通過在前面補(bǔ)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，別忘了進(jìn)位
? ? ? ? ? StrRet.insert(StrRet.begin(),add_num+'0');
? ? ? }
? ? ? return StrRet;
? }
};時(shí)空復(fù)雜度分析
時(shí)間復(fù)雜度為O(n1*n2)，其中n1、n2分別是num1、num2的長度。
空間復(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ì)超過 被乘數(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ù)成長平臺(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ò)：
后來終于揪出來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ò)過。
果然是細(xì)節(jié)決定成?。?！
思路1 遍歷找單詞
這題的思路蠻簡單的：遍歷一遍字符串，遇到單詞，就把整個(gè)單詞swap一下。
至于怎么找到單詞？
可以通過空格的位置來劃分單詞。也可以遍歷的時(shí)候記錄下單詞的起始位置。這兩種找單詞的方法都來實(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;
? }
};第二種：這種方法我第一次沒寫出來，那個(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í)沒寫出來，問題就出在那個(gè)大循環(huán)while(i<num){}里，我當(dāng)時(shí)一上來就把框架搭好了：
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í)際上可以直接用庫里的reverse、find函數(shù)。
思路2則不用遍歷字符串的每一個(gè)字符，而是用find找到空格，，然后從空格的后一個(gè) 接著去找 下一個(gè)空格。
當(dāng)沒有空格時(shí)，說明是最后一個(gè)單詞，翻轉(zhuǎn)，然后break跳出循壞。文章來源：http://www.zghlxwxcb.cn/news/detail-725553.html
注意，這種寫法，循環(huán)里也沒有經(jīng)典的"i++;"，所以不要一寫循環(huán)就把i++;給添上，不要 被習(xí)慣限制住思路！文章來源地址http://www.zghlxwxcb.cn/news/detail-725553.html
實(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_t
? ? ? ? ? if(pos!=string::npos){
? ? ? ? ? ? ? reverse(s.begin()+i,s.begin()+pos); //因?yàn)槭菑膇開始找的，所以要加i
? ? ? ? ? ? ? i=pos+1; ? ? ? ? ? ? ? ? ? ? ? ? ? //現(xiàn)在要從空格的下一位開始找
? ? ? ? ? } ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //注意reverse是左閉右開，右邊是開區(qū)間
? ? ? ? ? else{
? ? ? ? ? ? ? reverse(s.begin()+i,s.end()); ? //沒有空格了，說明這已經(jīng)是最后一個(gè)單詞了
? ? ? ? ? ? ? break;
? ? ? ? ? }
? ? ? }
? ? ? return s;
? }
};到了這里，關(guān)于【string題解 C++】字符串相乘 | 翻轉(zhuǎn)字符串III：翻轉(zhuǎn)單詞的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
