Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/66.html
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.
You may assume the integer does not contain any leading zero, except the number 0 itself.
Example 1:
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
@tag-array
Algorithm
If the number at the end is 9, then there will be a carry problem, and if the number in the previous digit is still 9, you need to continue to advance. The specific algorithm is as follows:
- first judge whether the last digit is 9, if not, add one directly to return,
- if it is, then assign 0 to the digit, and then continue to check the previous digit, the same method, until the first digit is checked.
- If the first digit was originally 9, a new digit will be generated after adding one, then the last thing to do is to check whether the first digit after the calculation is 0, if it is, add a 1 to the top.
Code
Java
-
public class Plus_One { public class Solution_clean { public int[] plusOne(int[] digits) { int n = digits.length; for (int i = digits.length - 1; i >= 0; --i) { if (digits[i] < 9) { ++digits[i]; return digits; } digits[i] = 0; // digits[i] is 9 } int[] res = new int[n + 1]; // only reaching here when input is straigh 9s, like [9,9,9,9,9] res[0] = 1; return res; } } public class Solution { public int[] plusOne(int[] digits) { if (digits == null || digits.length == 0) { return digits; } // just note overflow, and when carray array size +1 int carry = 1; // initate as 1, as to the "plus one" for (int i = digits.length - 1; i >= 0; i--) { int add = carry + digits[i]; if (add >= 10) { carry = add / 10; add = add % 10; } else { carry = 0; } digits[i] = add; } // final check if (carry > 0) { // increase int[] size int[] sizePlusOne = new int[digits.length + 1]; sizePlusOne[0] = carry; // fill the rest for (int i = 1; i < sizePlusOne.length; i++) { sizePlusOne[i] = digits[i - 1]; } digits = sizePlusOne; } // System.out.println(Arrays.toString(digits)); return digits; } } }
-
// OJ: https://leetcode.com/problems/plus-one/ // Time: O(N) // Space: O(1) class Solution { public: vector<int> plusOne(vector<int>& A) { int i = A.size() - 1, carry = 1; for (; i >= 0 && carry; --i) { carry += A[i]; A[i] = carry % 10; carry /= 10; } if (carry) A.insert(begin(A), carry); return A; } };
-
class Solution: def plusOne(self, digits: List[int]) -> List[int]: n = len(digits) for i in range(n - 1, -1, -1): digits[i] += 1 digits[i] %= 10 if digits[i] != 0: return digits return [1] + digits ############ class Solution(object): def plusOne(self, digits): """ :type digits: List[int] :rtype: List[int] """ carry = 1 for i in reversed(range(0, len(digits))): digit = (digits[i] + carry) % 10 carry = 1 if digit < digits[i] else 0 digits[i] = digit if carry == 1: return [1] + digits return digits