66.Plus One

August 19, 2016

66.Plus One

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,然后将结果以数组的形式返回。这道题看似简单,但实际处理的时候还是会有很多问题,首先,要维护一个进位,难点在于要处理好如果出现了连续进位的情况。我的思路请见代码:

/*solution1*/
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int i=0,size=digits.size(),carry=1;
        for(i=size-1;i>=0;i--){
            int digit=(digits[i]+carry)%10;
            carry=(digits[i]+carry)/10;
            digits[i]=digit;
            if(carry==0)
                return digits;
        }
        vector<int> res(size+1,0);
        res[0]=1;
        return res;
    }
};

第一版代码很重要,可以说是这类问题的一个通解,carry的初始值随题目所需要加上的值相等,在这道题中当然就是1了。进入循环之后,首先要计算的是末位+1之后对10取模的值,这是加法计算的原则,之后carry的值被更新为’'’carry=(digits[i]+carry)/10;’’‘,如果其大于0,则说明需要进位,因为int类型是向下取整的,需要进位,则向左移动一位,将进位值加到这一位上,以相同的方法继续判断是否需要进位;如果不需要进位则carry==0,直接返回即可。还有一种情况,就是循环结束后发现还是需要进位,例如999这种情况,那么就需要申请一个长度比原来大1 的vector,因为是+1,所以只有可能得到以1开头之后全为0的值,所以很好处理,看代码就好了。

之后看了一下讨论区,发现这道题还有一种钻空子的解法,只适用于plus one的情况,如果不是plus one而是plus two之类的情况就不能用这种方法了。

思路是从最后一位开始判断,如果这一位是9,将其赋值为0,如果不是9,则将其+1并返回;循环结束后如果还没有返回(也就是全为9的情况),那么将其首位赋值为1,调用push_back方法追加一个0即可,代码也十分优雅,请看代码:

/*solution2*/
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int i=0,size=digits.size();
        for(i=size-1;i>=0;i--){
            if(digits[i]==9)
                digits[i]=0;
            else{
                digits[i]++;
                return digits;
            }
        }
        digits[0]=1;
        digits.push_back(0);
        return digits;
    }
};

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017