lintcode：Plus One 加一

题目:

加一

给定一个非负数，表示一个数字数组，在该数的基础上+1，返回一个新的数组。

该数字按照大小进行排列，最大的数在列表的最前面。

样例

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

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

解题：

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

Java程序：

public class Solution {

    /**

     * @param digits a number represented as an array of digits

     * @return the result

     */

    public int[] plusOne(int[] digits) {

        // Write your code here

        int len = digits.length;

        int carray = 1;

        for(int i = len-1;i>=0;i--){

            carray +=digits[i];

            digits[i] = carray%10;

            carray = carray/10;

        }

        if(carray!=1)

            return digits;

        else {

            int nums[] = new int[len+1];

            nums[0] = 1;

            for(int i=1;i<len+1;i++)

                nums[i] =digits[i-1];

            return nums;

        }

    }

}

总耗时: 11253 ms

Python程序：

class Solution:

    # @param {int[]} digits a number represented as an array of digits

    # @return {int[]} the result

    def plusOne(self, digits):

        # Write your code here

        carray = 1

        for i in range(len(digits)-1,-1,-1):

            carray +=digits[i]

            digits[i] = carray%10

            carray = carray/10

        if carray!=1:

            return digits

        else:

            digits = [1] + digits

            return digits

总耗时: 413 ms

=================================更新===================================

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

abcde + 1

有下面的情况:

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

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

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

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

public class Solution {

    /**

     * @param digits a number represented as an array of digits

     * @return the result

     */

    public int[] plusOne(int[] digits) {

        // Write your code here

        int n = digits.length;

    for(int i=n-1; i>=0; i--) {

        if(digits[i] < 9) {

            digits[i]++;

            return digits;

        }

        digits[i] = 0;

    }

    int[] newNumber = new int [n+1];

    newNumber[0] = 1;

    return newNumber;

    }

}

巴特西

lintcode：Plus One 加一

最新文章

热门文章