lintcode：PlusOne加一

题目:

加一

给定一个非负数&＃xff0c;表示一个数字数组&＃xff0c;在该数的基础上&＃43;1&＃xff0c;返回一个新的数组。

该数字按照大小进行排列&＃xff0c;最大的数在列表的最前面。

样例

给定 [1,2,3] 表示 123, 返回 [1,2,4].

给定 [9,9,9] 表示 999, 返回 [1,0,0,0].

解题&＃xff1a;

好像只有这样搞&＃xff0c;对应进位的时候&＃xff0c;要新定义个数组

Java程序&＃xff1a;

public class Solution {/*** &＃64;param digits a number represented as an array of digits* &＃64;return the result*/public int[] plusOne(int[] digits) {// Write your code hereint len &＃61; digits.length;int carray &＃61; 1;for(int i &＃61; len-1;i>&＃61;0;i--){carray &＃43;&＃61;digits[i];digits[i] &＃61; carray%10;carray &＃61; carray/10;}if(carray!&＃61;1)return digits;else {int nums[] &＃61; new int[len&＃43;1];nums[0] &＃61; 1;for(int i&＃61;1;i)nums[i] &＃61;digits[i-1];return nums;}}
}

View Code

总耗时: 11253 ms

Python程序&＃xff1a;

class Solution:# &＃64;param {int[]} digits a number represented as an array of digits# &＃64;return {int[]} the resultdef plusOne(self, digits):# Write your code herecarray &＃61; 1 for i in range(len(digits)-1,-1,-1):carray &＃43;&＃61;digits[i]digits[i] &＃61; carray%10carray &＃61; carray/10if carray!&＃61;1:return digitselse:digits &＃61; [1] &＃43; digitsreturn digits

View Code

总耗时: 413 ms

&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;更新&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;

参考leetcode discuss 中一个很好的方法

abcde &＃43; 1

有下面的情况:

1.个位数小于9 &＃xff0c;加一后&＃xff0c;只是把个位数加一&＃xff0c;其他位数没有变&＃xff0c;可以直接返回加一后的数组就是答案

2.个位数等于9&＃xff0c;说明需要进位&＃xff0c;各位数变为0&＃xff0c;,十位数 可能小于9 或者等于9的情况&＃xff0c;转向 1、2进行讨论

3.最高位等于9&＃xff0c;加一后需要进位&＃xff0c;这个1一定是开始的1&＃xff0c;慢慢先前加进去的&＃xff0c;说明这个数全是9&＃xff0c;而最后的结果是1000000&＃xff0c;这样的形式

所以只需要新定义一个数组&＃xff0c;第一位数是1&＃xff0c;其余是0&＃xff0c;长度是原始数组长度加一。