题目大意:
加一
给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例 1:
输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。
如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=66
解题思路分析:
加法题目我们之前介绍过不少。解题时关键在于使用一个carry变量来代表进位。本题是一个数字(用数组表示)加1,因此,我们可以从数组最后一位(数字最低位)向前循环,carry默认为1。对于每一位上的数字,我们首先使用当前位上的数字加上进位carry得到一个和sum,sum与10的余数为当前位上相加计算后的数字,sum与10的商则是carry。
注意全部循环结束之后,如果carry仍为1,别忘了将这个1放到数字的最高位去(最终数字比原数字多一位)。
实现代码:
public int[] plusOne(int[] digits) { int carry=1; for(int i=digits.length-1;i>=0;i--){ int sum=carry+digits[i]; carry=sum/10; digits[i]=sum%10; // 之后不会再出现进位,高位上的数字都会保持不变 if(carry==0) return digits; } int[] res = new int[digits.length+1]; res[0]=1; for(int i=1;i<res.length;i++){ res[i]=digits[i-1]; } return res; }
本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Plus One.
Memory Usage: 37.8 MB, less than 5.64% of Java online submissions for Plus One.
本网站文章均为原创内容,并可随意转载,但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-66-plus-one-解题思路分析/