https://leetcode-cn.com/problems/plus-one
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以零开头。 示例 1: 输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。 示例 2: 输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。 lucifer 提示： 不要加直接数组转化为数字做加法再转回来。
- 数组的遍历(正向遍历和反向遍历)
这道题其实我们可以把它想象成小学生练习加法，只不过现在是固定的“加一”那么我们只需要考虑如何通过遍历来实现这个加法的过程就好了。
加法我们知道要从低位到高位进行运算，那么只需要对数组进行一次反向遍历即可。
伪代码：
for(inti = n - 1; i > - 1; i --) { 内部逻辑 }内部逻辑的话，其实有三种情况：
1. 个位上的数字小于9 17 + 1 = 18 2. 个位数上等于9，其他位数可以是0-9的任何数，但是首位不等于9 199 + 1 = 200 109 + 1 = 110 3. 所有位数都为9 99 + 1 = 100 999 + 1 = 1000 第一种情况是最简单的，我们只需将数组的最后一位进行+1 操作就好了
第二种情况稍微多了一个步骤：我们需要把个位的 carry 向前进一位并在计算是否有更多的进位
第三种其实和第二种是一样的操作，只是由于我们知道数组的长度是固定的，所以当我们遇到情况三的时候需要扩大数组的长度。我们只需要在结果数组前多加上一位就好了。
// 首先我们要从数组的最后一位开始我们的计算得出我们新的sumsum=arr[arr.length-1]+1// 接下来我们需要判断这个新的sum是否超过9sum>9 ? // 假如大于 9, 那么我们会更新这一位为 0 并且将carry值更改为1carry=1arr[i]=0// 假如不大于 9，更新最后一位为sum并直接返回数组arr[arr.length-1]=sumreturnarr// 接着我们要继续向数组的倒数第二位重复进行我们上一步的操作...// 当我们完成以后，如果数组第一位时的sum大于0，那么我们就要给数组的首位增添一个1result=newarraywithsizeofarr.length+1result[0]=1result[1]......result[result.length-1]=0代码支持：Python3，JS, CPP, Go, PHP，Java
Python3 Code：
classSolution: defplusOne(self, digits: List[int]) ->List[int]: carry=1foriinrange(len(digits) -1, -1, -1): digits[i], carry= (carry+digits[i]) %10, (carry+digits[i]) //10return [carry] +digitsifcarryelsedigitsJS Code：
varplusOne=function(digits){varcarry=1;// 我们将初始的 +1 也当做是一个在个位的 carryfor(vari=digits.length-1;i>-1;i--){if(carry){varsum=carry+digits[i];digits[i]=sum%10;carry=sum>9 ? 1 : 0;// 每次计算都会更新下一步需要用到的 carry}}if(carry===1){digits.unshift(1);// 如果carry最后停留在1，说明有需要额外的一个长度 所以我们就在首位增添一个 1}returndigits;};CPP Code:
classSolution { 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; } };Go code:
funcplusOne(digits []int) []int { fori:=len(digits) -1; i>=0; i-- { digits[i]++ifdigits[i] !=10 { // 不产生进位, 直接返回returndigits } digits[i] =0// 产生进位, 继续计算下一位 } // 全部产生进位digits[0] =1digits=append(digits, 0) returndigits }PHP code:
class Solution { /** * @param Integer[] $digits * @return Integer[] */functionplusOne($digits) { $len = count($digits); for ($i = $len - 1; $i >= 0; $i--) { $digits[$i]++; if ($digits[$i] != 10) { // 不产生进位, 直接返回return$digits; } $digits[$i] = 0; // 产生进位, 继续计算下一位 } // 全部产生进位$digits[0] = 1; $digits[$len] = 0; return$digits; } }Java code:
classSolution { publicint[] plusOne(int[] digits) { for (inti = digits.length - 1; i >= 0; i--) { digits[i]++; digits[i] = digits[i] % 10; if (digits[i] != 0) returndigits; } //遇每个数位均为9时手动进位digits = newint[digits.length + 1]; digits[0] = 1; returndigits; } }复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
