原题地址：加一
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
按位相加
模拟加法的计算过程，从低位往高位依次计算。注意如果中间某一位没有产生进位，由于只加了1，更高位将不可能产生进位，可以直接结束计算。
具体的实现代码如下：
/**
* @param {number[]} digits
* @return {number[]}
*/
const plusOne1 = function(digits) {
// 初始进位为1，相当于加了1
let cache = 1;
// 按位相加
for (let i = digits.length - 1; i >= 0; i --) {
cache += digits[i];
digits[i] = cache % 10;
cache = Math.floor(cache / 10);
// 因为只加了1，所以如果中间某一步没有进位，更高位也不会再有进位产生，可以直接结束
if (cache === 0) {
break;
}
}
// 处理最后的进位
if (cache > 0) {
digits.unshift(cache);
}
return digits;
};
测试：
let start = new Date();
const test = plusOne1;
console.log(test([1,2,3])); // [ 1, 2, 4 ]
console.log(test([4,3,2,1])); // [ 4, 3, 2, 2 ]
console.log(new Date().getTime() - start.getTime()); // 8
时间复杂度： 一次遍历，时间复杂度为$O(N)$
空间复杂度： 原地处理，空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 19,2019