LeetCode43題-字符串相乘[C++實(shí)現(xiàn)]

時(shí)間：2020-07-07 14:34:46

關(guān)鍵字：字符串

手機(jī)看文章

掃描二維碼
隨時(shí)隨地手機(jī)看文章

[導(dǎo)讀]1 前言今天來寫一道leetcode的中等難度的題目，聲明一下：這不是最優(yōu)解，就是常規(guī)思路。之所以寫出來，是因?yàn)槲矣X得：如果你的想法比較復(fù)雜或者比較冗長，那也沒關(guān)系，寫出來ac了它，能繞過層層關(guān)卡做出來同樣值得。就好像我們新接手了同事的代碼，第一反

1 前言

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

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

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

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

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

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

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

廢話不說，開車開車！

2.題目描述

給定兩個(gè)以字符串形式表示的非負(fù)整數(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 本身。
不能使用任何標(biāo)準(zhǔn)庫的大數(shù)類型（比如 BigInteger）或直接將輸入轉(zhuǎn)換為整數(shù)來處理。

3.題目分析

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

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

其實(shí)這個(gè)問題很熟悉，這就是個(gè)計(jì)算器嘛，我們要把很長的兩個(gè)字符串相乘。

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

4.手動(dòng)模擬

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

在紙上大致模擬了一下之后，基本上就能把握幾個(gè)點(diǎn)了：

乘數(shù)和被乘數(shù)的兩個(gè)循環(huán)
在計(jì)算循環(huán)過程中，涉及到一個(gè)默認(rèn)補(bǔ)0的過程，因?yàn)閿?shù)字所在的位不一樣，這樣是要注意的，這樣我們得到三個(gè)字符串，這三個(gè)字符串本質(zhì)上是逆序的，因?yàn)槲覀兪窍葟牡臀婚_始計(jì)算的。
各個(gè)臨時(shí)結(jié)果的累加
也就是圖中的第二部分，這里是把多個(gè)臨時(shí)結(jié)果累加就可以了，最開始我把第一部分的結(jié)果做了reverse,但是在第二部分累加時(shí)發(fā)現(xiàn)沒有必要，最后把結(jié)果reverse一下即可。
細(xì)節(jié)問題
在基本了解流程之后，肯定會(huì)有一些需要注意的致錯(cuò)細(xì)節(jié)，這個(gè)很多時(shí)候是debug時(shí)發(fā)現(xiàn)的，這道題我代碼寫完之后debug出兩個(gè)錯(cuò)誤的點(diǎn)，反過來想是細(xì)節(jié)考慮不周全。

4.我的糙代碼

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

無奈同行們太優(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.完全模擬乘法的計(jì)算過程 2.使用兩個(gè)循環(huán) 增加每次計(jì)算的結(jié)果 以及進(jìn)位 3.由于要求不可直接將輸入轉(zhuǎn)換為整數(shù) 可以使用ascii來確定單個(gè)字符的數(shù)值 */ int len1 = num1.length(); int len2 = num2.length(); //存儲(chǔ)每次循環(huán)的結(jié)果 后續(xù)的累加 要從其中進(jìn)行遍歷 vector<string> resvec; int maxlen=0; //我們從乘數(shù) nums2開始作為外層循環(huán) 即456 并且從個(gè)位開始循環(huán) //為了對齊將結(jié)果后默認(rèn)補(bǔ)齊0 for(int i=len2-1;i>=0;i--){ int jinwei = 0; //從低位到高位循環(huán)被乘數(shù) 并初始化進(jìn)位 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); //計(jì)算兩個(gè)位的乘積 并取保留值和進(jìn)位 //eg 8*9=72 上一次進(jìn)位0 綜合得：保留位2 進(jìn)位7 int calres = inner*outer+jinwei; jinwei = calres/10; int remain = calres%10; //這里注意 乘積是從低位開始運(yùn)算的 因此需要注意方向問題 //為了方便解決 將低位放在字符串首位 高位依次追加 最后反轉(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; }};