Leetcode基礎(chǔ)篇30天30題系列之?dāng)?shù)組：模擬計算法

作者：丁宋濤

數(shù)組：加一
題干：
給定一個由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。
最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個元素只存儲一個數(shù)字。
你可以假設(shè)除了整數(shù) 0 之外，這個整數(shù)不會以零開頭。
參考樣例：
示例?1:
輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數(shù)組表示數(shù)字 123。
示例?2:
輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入數(shù)組表示數(shù)字 4321。
這道題是一道數(shù)組的基礎(chǔ)題，其本質(zhì)是一道模擬計算題。
這道題有一定的工程應(yīng)用意義，大家都知道，計算機(jī)的浮點數(shù)運(yùn)算有誤差，究其細(xì)節(jié)有相當(dāng)數(shù)量的開發(fā)者卻往往不求甚解。請看：
做開發(fā)的朋友都知道計算機(jī)在程序處理中，都是將十進(jìn)制數(shù)轉(zhuǎn)成二進(jìn)制數(shù)進(jìn)行運(yùn)算的。對于這種轉(zhuǎn)化，其方法就是除2逆向取余法，例如：
十進(jìn)制數(shù)13轉(zhuǎn)成二進(jìn)制的方法就是

轉(zhuǎn)化成數(shù)學(xué)表達(dá)式就是（13）??=（1101） ?
對于十進(jìn)制小數(shù)轉(zhuǎn)化成二進(jìn)制小數(shù)使用的方法是乘2正向取整法，比如十進(jìn)制的0.75
即（0.75）??=（0.11） ?

如果，我們考慮下將十進(jìn)制的0.6轉(zhuǎn)化成二進(jìn)制呢？如果依然使用乘二正向取整法會發(fā)生什么呢？

如果從數(shù)學(xué)上講，（0.75）??=（0.1001） ?
為什么會出現(xiàn)這種循環(huán)表示呢？因為數(shù)學(xué)上有證明，十進(jìn)制表示法與二進(jìn)制表示法，僅僅在整數(shù)范圍內(nèi)才有明確的對應(yīng)的關(guān)系，而小數(shù)部分是做不到的。因此，在采用二進(jìn)制運(yùn)算上，計算機(jī)的數(shù)值求解是有缺陷的。
意識到這一點，我們就會問那么是不是我們現(xiàn)在和小數(shù)點相關(guān)的運(yùn)行都是不可靠的呢？顯然不可能，最常見的就是我們的金融活動。大凡和交易有關(guān)的數(shù)據(jù)，那是一個數(shù)字都不能出錯的，那么他們背后的計算過程又是如何保證的呢？
答案就是模擬計算。
在小學(xué)數(shù)學(xué)課本上就教過這樣的案例：123.4+5.67，我們來看，加數(shù)與被加數(shù)的位數(shù)并不相同，小學(xué)老師在教學(xué)中一定會強(qiáng)調(diào)對齊小數(shù)點，其過程如下：

這個在計算機(jī)中有一個術(shù)語叫做對階。所謂階就是進(jìn)制，十進(jìn)制的階就是10，二進(jìn)制的階就是2，具體的數(shù)學(xué)表達(dá)就是
123.4 = 1×102+2×101+3×100+4×10-1
5.67=5×100+6×10-1+7×10-2
我們知道計算機(jī)的整數(shù)運(yùn)算是沒有缺陷的，如果我們這樣做，是不是就可以達(dá)到精確求解的目的了？
123.4+5.67=（12340+567）×102=12907×10-2=129.07
這就是精度計算中的常用的計算思想，這也是為什么在以Java為核心語言中做交易系統(tǒng)中，金額通常不用float，double而用decimal類型的原因。
明白了這個知識，我們就知道了這個看似普通的題目，其實是企業(yè)開發(fā)商用軟件中的一個現(xiàn)實問題。那么，在現(xiàn)實計算中，人們又是如何來處理上述的對階、運(yùn)算的過程呢？答案就是數(shù)組。我們用數(shù)組來模擬每一位，然后用小學(xué)數(shù)學(xué)課本教授的方法，手工計算出就可以了。
下面回到這個題目：題目的函數(shù)簽名是這樣的：vector<int> plusOne(vector<int>& digits)
傳入的參數(shù)是digits，是一個整型的向量，其位數(shù)按照角標(biāo)升序排列，即角標(biāo)0對應(yīng)的是數(shù)字的最高位，最后一位表示的數(shù)字的最低位，比如參考樣例：[1,2,3],他表示的是十進(jìn)制123，角標(biāo)0對應(yīng)的是百位1，角標(biāo)2對應(yīng)的是個位3.模擬十進(jìn)制計算的過程，就是逢10進(jìn)位，這道題我們首先要找到最低位，如果最低位不是9，直接取出角標(biāo)對應(yīng)的數(shù)值加1即可，如果是數(shù)字的9的話，那么直接將其改為0，并向其上一位角標(biāo)對應(yīng)的數(shù)字加1.需要注意的細(xì)節(jié)是，如果這個數(shù)字恰好是[9,9,9],那么返回值應(yīng)當(dāng)增加1位得到[1,0,0,0]。為了方便編程，我們從最后一位開始。代碼如下：
1 vector<int> plusOne(vector<int>& digits) {
2 int n = digits.size();
3 for(int i=n-1;i>=0;i--){
4 if(digits[i] == 9)
5 digits[i] =0;
6 else {
7 digits[i]++;
8 return digits;
9 }
10 }
11 digits[0] =1;
12 digits.push_back(0);
13 return digits;
14 }
第2行，首先獲得當(dāng)前向量digits的長度，并將其復(fù)制給n，然后從角標(biāo)n-1開始，逆向遍歷整個數(shù)組，由于i是從n-1開始，我們先判斷當(dāng)前位置是否是9，如果是9，那么就把把當(dāng)前位置置0，并向前遍歷到前一個位置，只要前一個位置不是9，那么就把此時的位置加1，然后返回。如果全體循環(huán)結(jié)束都沒有返回，那么說明傳入的必然是999這種類型的。那么出了循環(huán)之后，先把角標(biāo)0改為1，并再增加一個0，就完成了全部的計算過程。

課程鏈接：https://edu.51cto.com/course/18440.html