This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

I. Title Description:

Leetcode 66 plus one

Given a non-negative integer represented by a non-empty array of integers, add one to that number.

The highest digit is stored at the beginning of an array, where each element stores only a single digit.

You can assume that this integer does not start with zero, except for the integer 0.

Example 1:

Input: digits = [1,2,3] output: [1,2,4] explanation: input array represents the number 123.Copy the code

Example 2:

Input: digits = [4,3,2,1] output: [4,3,2,2] explanation: input array represents the number 4321.Copy the code

Example 3:

Input: digits = [0] output: [1]Copy the code

Tip:

1 <= digits.length <= 100
0 <= digits[i] <= 9
Copy the code

Ii. Analysis of Ideas:

  • Convert the array toNumberType after the addition of one calculation, calculation and then converted to an array

AC code

var plusOne = function(digits) {
    let num = Number(digits.join('')) + 1;
    return String(num).split('');
};
Copy the code

The execution result

Input:,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,3 [6] output:,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,0,0,0 [6] expected results: ,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,4 [6]Copy the code

Failed, abnormal cause: Exceeded the maximum JS value limit;

  • Add one to the last digit
  1. If the last bit is less than 9, there is no carry after the increment and the result is returned directly;
  2. If the last digit is equal to 9, then you add 1 and then you put 0, carry 1;
  3. If there is only one digit in the array and there is a carry, the first and last digits are added.
  4. If there are more than one digits in the array, the loop is carried forward until the first digit is determined. The same process is done with 3.

AC code

var plusOne = function(digits) { let len = digits.length; let last = digits[len - 1]; if(last < 9) { digits[len - 1] = last + 1; return digits; } else { digits[len - 1] = 0; if(digits[len - 2]) { digits[len - 2] = digits[len - 2] + 1; } else { digits.unshift(1); } for(let i = len - 2; i >= 0; i --) { let last = digits[i]; if(last <= 9) { return digits; } else { digits[i] = 0; if(digits[i - 1]) { digits[i - 1] = digits[i - 1] + 1; } else { digits.unshift(1); } } } return digits; }};Copy the code

The execution result

Results: Beat 45.36% of users memory consumption in all JavaScript commits: 37.7 MB and beat 88.91% of users in all JavaScript commits with execution time: 88 msCopy the code
  • Loop code simplification

The judgment of the last digit and the second to last digit is the same as the logic of circular judgment, so there is no need to deal with it separately.

  1. The reverse loop judges whether the current number is greater than 9 after adding one, and returns if it is less than 9.
  2. Greater than 9, carry, that is, continue the cycle to the next digit;
  3. If the first digit of the array is not returned, then the first digit is still greater than 9, and the array starts with a carry 1.

AC code

var plusOne = function(digits) {
    let len = digits.length;
    for(let i = len - 1; i >= 0; i --) {
        let last = digits[i] + 1;
        if(last <= 9) {
            digits[i] = last;
            return digits;
        } else {
            digits[i] = 0;
        }
    }
    digits.unshift(1);
    return digits;
};
Copy the code

The execution result

Results: Beat 27.81% of users in all JavaScript commits with execution time: 92 ms memory consumption: 37.9 MB and beat 51.86% of users in all JavaScript commitsCopy the code
  • Loop code optimization
  1. Loop array numberEach element in an array stores only a single number, if the value is greater than 9 after adding one, it should be 10. Mod 10 can get the value after adding one;
  2. If mod 10 is not equal to 0 you get the result and you don’t carry;
  3. If the first digit of the array is not returned, then the first digit is still greater than 9, and the array starts with a carry 1.

AC code

var plusOne = function(digits) {
    let len = digits.length;
    for(let i = len - 1; i >= 0; i --) {
        digits[i] ++;
        if(digits[i] % 10) {
            return digits;
        } else {
            digits[i] = 0;
        }
    }
    digits.unshift(1);
    return digits;
};
Copy the code

The execution result

Results: Beat 45.36% of users memory consumption in all JavaScript commits: 37.9 MB and beat 41.96% of users in all JavaScript commits with execution time: 88 msCopy the code

Iii. Summary:

  • JavaScriptIn theNumberThere is a maximum safe integer (253-1) Restriction;
  • All the numbers in the array add one to judge the consistency of processing logic, which can simplify the code;
  • If it is less than 10, no carry, end; If equal to 10, the current position is 1, carry 1, can optimize the code;