加兩個數字，扭曲的是數字的長度可以非常大

今天我有一個採訪和麪試官要求做一個程序增加兩個數字，我感到震驚，他怎麼能給一個簡單的問題，但問題是不同的加兩個數字，扭曲的是數字的長度可以非常大

兩個數的長度可以是任何東西（10,20,30甚至1000等）

，如果你將其轉換爲int，雙，長雙若數量大於他們的範圍比答案可能是錯誤的。

請幫我解決這個問題。

2017-06-14 JeeVan TiWari

比請提供鏈接。 –

您可以在標籤中找到大量重複項[tag：bigint] –

無限長度數字？根據[Knuth]（https://en.wikipedia.org/wiki/Algorithm_characterizations#1968.2C_1973_Knuth.27s_characterization）「一個算法必須總是在有限步數後終止」，所以不可能有這樣的算法。什麼樣的傻人會要求你編寫一個沒有有效算法的程序？你確定他們沒有要求如何添加任意數量的有限長度嗎？ – pjs

你總是可以把數組中的兩個數字（即數組有數字的數字作爲元素）並添加它們，因爲我們手動添加，即從一個數字開始並存儲進位，如果它存在，那麼執行十位數，然後是百位數等等。

說你要添加123和329

X = 123, X[] = [1,2,3] 
Y = 329, Y[] = [3,2,9]

你開始與一個人的數字（最右邊或最後一個元素），並添加X和Y數組的元素，並添加進到它（初始設置到0）。如果加數大於10，則設置爲carry = sum/10（因爲我們正在添加每個元素，所以這個進位應始終爲0或1）並且加上add [i] = sum % 10。重複，直到所有更小陣列的元素結束。然後將進位添加到更大數組的其餘元素，繼續上述邏輯。

carry = 0 
Step 1 : 3 + 9 + carry (0) = 5, carry => 12/10 = 1, add => 12 % 10 = 2 
Step 2 : 2 + 2 + carry (2) = 6, carry => 6/10 = 0, add => 6 % 10 = 6 
Step 3 : 3 + 1 + carry (0) = 4, carry => 4/10 = 0, add => 4 % 10 = 4

ANS = 462

顯然，陣列中存儲總和可以具有一個額外的位，以便照顧這一點。

來源

2017-06-14 16:36:57

但是，如果我們存儲進位，我們如何識別這個進位是哪個索引。 –

您只需要一個進位，並在添加每個相應的數字後將其設置爲零或一。 –

@JeeVanTiWari在答案中增加了一個例子。應該很容易轉換成代碼。 –

加兩個數字，扭曲的是數字的長度可以非常大

回答

相關問題