01.plus-one.md

66.加一

https://leetcode-cn.com/problems/plus-one

• 66.加一
  • 题目描述
  • 方法 1
    • 思路
    • 复杂度
    • 代码 (JS/C++)

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/plus-one
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1

思路

在数组上做竖式加法，用 carry 来表示进位，反向遍历数组即可。

遍历结束条件：

1. 数组所有元素都遍历过了
2. 当 carry 为 0 的时候

需要注意的点：

如果遍历结束后 carry 大于 0，还需要在数组前面补一位。

复杂度

• 时间复杂度：$O(N)$, N 为数组长度。
• 空间复杂度：$O(1)$。

代码 (JS/C++)

JavaScript Code

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
  let carry = 1,
    sum = 0,
    index = digits.length - 1;

  while (carry > 0 && index > -1) {
    sum = digits[index] + 1;
    carry = Math.floor(sum / 10);
    digits[index] = sum % 10;
    index--;
  }

  carry && digits.unshift(carry);

  return digits;
};

C++ Code

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        vector<int> res(digits.size());

        int carry = 1;
        for (int i = digits.size() - 1; i >= 0; i--) {
            res[i] = (digits[i] + carry) % 10;
            carry = ((digits[i] + carry) / 10) >> 0;
        }
        if (carry > 0) {
            res.insert(res.begin(), carry);
        }

        return res;
    }
};