1 前言

今天來寫一道leetcode的中等難度的題目，聲明一下：這不是最優(yōu)解，就是常規(guī)思路。

之所以寫出來，是因為我覺得：如果你的想法比較復(fù)雜或者比較冗長，那也沒關(guān)系，寫出來ac了它，能繞過層層關(guān)卡做出來同樣值得。

就好像我們新接手了同事的代碼，第一反應(yīng)可能是這么復(fù)雜，但是竟然還能跑，所以盡管很繞，但是沒有把他繞暈，那么我覺得他也挺厲害的了。

工作中我就遇到過這樣的代碼，同事的開發(fā)能力比較強，但是代碼風格跟我差別很大，期間接過他一點代碼，可能是過設(shè)計了，但是運行得很好。

在我們沒有做那么多題目的前提下，第一想法很重要，面試的時候往往很緊張，把握住你的第一想法去實現(xiàn)它，最終做出來足夠讓面試官覺得你還不錯，在此基礎(chǔ)上優(yōu)化就是加分。

有些題目的最優(yōu)解或者優(yōu)化解并不好想，如果不是acm打手或者天資異稟的高手還是有難度的。

所以不要嫌棄這不是最優(yōu)解，最起碼這是最容易想到的解法，當然你們也可以覺得不是最優(yōu)解沒有意義，非要嫌棄鄙視一下，那也么得辦法，啊哈哈。

廢話不說，開車開車！

2.題目描述

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

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

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

說明：
num1 和 num2 的長度小于110。
num1 和 num2 只包含數(shù)字 0-9。
num1 和 num2 均不以零開頭，除非是數(shù)字 0 本身。
不能使用任何標準庫的大數(shù)類型（比如 BigInteger）或直接將輸入轉(zhuǎn)換為整數(shù)來處理。

3.題目分析

這個題目描述也比較清晰了，就是給了兩個字符串格式的數(shù)字，讓返回兩個數(shù)的乘積字符串。

題目限定了不要使用bigint和輸入轉(zhuǎn)整數(shù)這種系統(tǒng)的機制，并且給定了num1和num2的長度小于110，這也說明了長度可能是100那么長，110位就已經(jīng)非常大了，所以不要考慮轉(zhuǎn)換整數(shù)的想法了。

其實這個問題很熟悉，這就是個計算器嘛，我們要把很長的兩個字符串相乘。

第一想法就是那模擬一下兩個數(shù)相乘的具體過程，再轉(zhuǎn)換為代碼，是的，這個想法就足夠了。

4.手動模擬

來吧，有了第一想法，那就開始在紙上劃拉劃拉。

在紙上大致模擬了一下之后，基本上就能把握幾個點了：

• 乘數(shù)和被乘數(shù)的兩個循環(huán)
  在計算循環(huán)過程中，涉及到一個默認補0的過程，因為數(shù)字所在的位不一樣，這樣是要注意的，這樣我們得到三個字符串，這三個字符串本質(zhì)上是逆序的，因為我們是先從低位開始計算的。

• 各個臨時結(jié)果的累加
  也就是圖中的第二部分，這里是把多個臨時結(jié)果累加就可以了，最開始我把第一部分的結(jié)果做了reverse,但是在第二部分累加時發(fā)現(xiàn)沒有必要，最后把結(jié)果reverse一下即可。

• 細節(jié)問題
  在基本了解流程之后，肯定會有一些需要注意的致錯細節(jié)，這個很多時候是debug時發(fā)現(xiàn)的，這道題我代碼寫完之后debug出兩個錯誤的點，反過來想是細節(jié)考慮不周全。

4.我的糙代碼

代碼提交了幾次才通過，看下時間和空間：

無奈同行們太優(yōu)秀，被80%的同行大敗了，不過就算反面教材也可以看看吧：

class Solution {public: //將string指定位置的字符轉(zhuǎn)換為數(shù)字 int getvalue (string &num, int index){ return num[index]-'0'; }
 //遍歷子結(jié)果字符串 累加 void calthem(vector<string> &resvec, int maxlen, string &resstr){ //按照最大長度開始從低位向高位遍歷 int veclen = resvec.size(); int jinwei = 0;
 for(int i=0;i<maxlen;i++){ //開始遍歷每一次的結(jié)果 int this_sum = 0; this_sum += jinwei; for(int j=0;j<veclen;j++){ if(i<resvec[j].length()){ this_sum+=getvalue(resvec[j],i); } } jinwei = this_sum/10; int remain = this_sum%10; resstr+=to_string(remain); } if(jinwei!=0) resstr+=to_string(jinwei); reverse(resstr.begin(),resstr.end()); }
 string multiply(string num1, string num2) { //特殊情況 string res(""); if(num1=="0"||num2=="0") return "0"; //其他情況 /* 1.完全模擬乘法的計算過程 2.使用兩個循環(huán) 增加每次計算的結(jié)果 以及進位 3.由于要求不可直接將輸入轉(zhuǎn)換為整數(shù) 可以使用ascii來確定單個字符的數(shù)值 */ int len1 = num1.length(); int len2 = num2.length(); //存儲每次循環(huán)的結(jié)果 后續(xù)的累加 要從其中進行遍歷 vector<string> resvec; int maxlen=0; //我們從乘數(shù) nums2開始作為外層循環(huán) 即456 并且從個位開始循環(huán) //為了對齊將結(jié)果后默認補齊0 for(int i=len2-1;i>=0;i--){ int jinwei = 0; //從低位到高位循環(huán)被乘數(shù) 并初始化進位 int outer = getvalue(num2,i); int zero_cnt = len2-1-i; string this_round_res=""; this_round_res.append(zero_cnt,'0'); for(int j=len1-1;j>=0;j--){ int inner = getvalue(num1,j); //計算兩個位的乘積 并取保留值和進位 //eg 8*9=72 上一次進位0 綜合得：保留位2 進位7 int calres = inner*outer+jinwei; jinwei = calres/10; int remain = calres%10; //這里注意 乘積是從低位開始運算的 因此需要注意方向問題 //為了方便解決 將低位放在字符串首位 高位依次追加 最后反轉(zhuǎn)即可 this_round_res+=to_string(remain); } if(jinwei!=0) this_round_res+=to_string(jinwei); maxlen = maxlen>=this_round_res.length()?maxlen:this_round_res.length(); resvec.push_back(this_round_res); } //累加vector中的數(shù)據(jù) calthem(resvec,maxlen,res); return res; }};

代碼好像還是比較長，不過本質(zhì)上就兩個部分，第一個是利用兩個循環(huán)獲得臨時結(jié)果字符串，把字符串存儲在vector中，第二部分就是把vector中的臨時字符串累加返回。

其中盡量不用api,能自己造的輪子就自己寫了，權(quán)當一題多練了。

5.優(yōu)化解

我的糙代碼ac之后，慣例打開題解看看同行有什么妙招，其中有一個講的比較好，是對算數(shù)過程的優(yōu)化，說實話我的算數(shù)并不好，所以這個是第一次看到，現(xiàn)場我是想不到， 不過很有用一起看下：

這個優(yōu)化法是把計算過程中的值的坐標都提前知道了，所以就相當于一步到位，不過我還沒來得及實驗可以快多少，等下試試。

最后依然是，感謝各位的觀摩！