Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.
_*Example_8
Given [1,2,3] which represents 123, return [1,2,4].
Given [9,9,9] which represents 999, return [1,0,0,0].
Tags
Array Google
Related Problems
Medium Divide Two Integers 15 %
Easy Add Binary
Analysis
比较巧的方法是将 +1 当做末位digit的进位carries；每次进位 carries = sum / 10;，留下的数字为 digits[i] = sum % 10;
如果最终进位 ！= 0，说明要新增加一位，则新建数组把计算结果填进去。
Solution
public class Solution {
/**
* @param digits a number represented as an array of digits
* @return the result
*/
public int[] plusOne(int[] digits) {
int carries = 1;
for (int i = digits.length - 1; i >= 0 && carries > 0; i--) {
int sum = digits[i] + carries;
digits[i] = sum % 10;
carries = sum / 10;
}
if (carries == 0) {
return digits;
}
int[] result = new int[digits.length + 1];
result[0] = 1;
for (int i = 1; i < result.length; i++) {
result[i] = digits[i - 1];
}
return result;
}
}
好久不见，写了一个特啰嗦的...：(0 ms beats 100% AC)
class Solution {
public int[] plusOne(int[] digits) {
int carry = 0;
int i = digits.length - 1;
while (carry >= 0 && i >= 0) {
int tmp = 0;
if (i == digits.length - 1) {
tmp = 1 + digits[i] + carry;
} else {
tmp = digits[i] + carry;
}
if (tmp > 9) {
digits[i] = tmp % 10;
carry = 1;
} else {
digits[i] = tmp;
carry = 0;
}
i--;
}
int[] ans;
if (carry > 0) {
ans = new int[digits.length + 1];
ans[0] = carry;
for (int k = 1; k < ans.length; k++) {
ans[k] = digits[k - 1];
}
} else {
ans = digits;
}
return ans;
}
}