码疯窝

LeetCode 每日一题 — Plus One

2014/12/18 10:55:31    分类: 日志连载    0人评论 次浏览

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

算法分析: 题意思为 [1,2,3] + 1 = [1,2,4]; [9,9] + 1 = [1,0,0]
这道题目首先想到的就是在数组中做加法, 然后判断进位, 另外一种方法就是将数组转化为数字, 然后加1, 再转为数组. 开始使用第二种方法去编码, 在python 下工作正常, 但是在java中却回出现溢出的情况, 故而此题目中, C++ 和 Java 使用的是第一种算法, Python 使用的是第二种算法.

Java:

public class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        int i = len, pos = 0;
        boolean plus = true;
        
        while (--i >= 0 && plus) {
            if (digits[i] == 9) {
                digits[i] = 0;
                plus = true;
            } else {
                digits[i]++;
                plus = false;
                break;
            }
        }
        if (plus) {
            int rst[] = new int[len + 1];
            for (i = 0; i < len; i++) {
                rst[i + 1] = digits[i];
            }
            rst[0] = 1;
            return rst;
        } else 
            return digits;
        
    }
}

C++:

class Solution {
public:
    vector plusOne(vector &digits) {
        int len = digits.size();
        int i = len, pos = 0;
        bool plus = true;
        
        while (--i >= 0 && plus) {
            if (digits[i] == 9) {
                digits[i] = 0;
                plus = true;
            } else {
                digits[i]++;
                plus = false;
                break;
            }
        }
        if (plus) {
            vector rst;
            rst.push_back(1);
            for (i = 0; i < len; i++) {
                rst.push_back(digits[i]);
            }
            return rst;
        } else 
            return digits;
    }
};

Python:

class Solution:
    # @param digits, a list of integer digits
    # @return a list of integer digits
    def plusOne(self, digits):
        dig = 0
    	i = 0
    	l = len(digits)
    	for i in range(0, l):
    		dig = dig * 10 + digits[i]
      	dig += 1
    	if (dig % 10 == 0 and digits[0] == 9):
    		l += 1
    	rst = []
    	for i in range(0, l):
    		t = (10 ** (l - i - 1))
    		r = dig / t
    		rst.append(r)
    		dig -= r * t

        return rst
        
继续查看有关 日志连载的文章

0个访客评论