NO IMAGE

題目:

給定一個非負整數組成的非空陣列,在該數的基礎上加一,返回一個新的陣列。

最高位數字存放在陣列的首位, 陣列中每個元素只儲存一個數字。

你可以假設除了整數 0 之外,這個整數不會以零開頭。

示例 1:

輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入陣列表示數字 123。

示例 2:

輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入陣列表示數字 4321。

 

演算法過程:其實就是高精度加法,這裡題目已經非常友好了,因為只需要加1,也就是說進位我們只用考慮個位為9的情況。

如果個位為9,我們進一併且去看十位是否為9,直到找到一位不為9。如果個位不為9,則只需把各位加1即可。

 

Python程式碼:

class Solution:
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
#先舔一位在前面作備用,可能用也用不到
digits = [0]   digits
m = len(digits) - 1
digits[m] = digits[m]   1
while  m - 1 >= 0 and digits[m]> 9:
#進位
digits[m] = digits[m] - 10
digits[m-1]  = 1
m -= 1
#如果第一位沒用上,就別傳第一位
if digits[0] == 0:
return digits[1:]
else:
return digits

 

C

class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int j = digits.size() - 1;
//先把個位加1
digits[j]  = 1;
while (j >= 0 and digits[j] > 9){
//進位
digits[j] = 0;
if (j >= 1) digits[j-1]  = 1;
//如果是原數字的最高項,則在前面添個1
else digits.insert(digits.begin(),1);
//把j向更高位推動
j -= 1;
}
return digits;
}
};

 

總的來說還是比較簡單的題目,但用C 寫一遍還是能學到點東西。比如如何向vector最前面新增元素,應該使用insert(vector.begin(), ele) 的方法來實現。