LeetCode初级算法之数组：加一

题目描述
题目描述：
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

思路一： 大整数类的加法思想简化

这个题我的初步思路是想起了大整数类的加法，就是给定两个大整数相加求和，可能是想的太复杂了，加一而已。 具体实现就是，由于加一可能导致最后在前面进位，所以先把数组逆序，然后从第一位加一，进行求和运算，如果大于9，改0进位。这样最后一位单独判断，如果大于9，改0， 数组加进一个1，最后再逆回来。 虽然这个想法能A掉，但是有点大材小用了。

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {

        int len = digits.size();
        int jinwei=0;
        int temp = 1;
        reverse(digits.begin(), digits.end());
        digits[0] += 1;
        for (int i=0; i<len-1; i++)
        {
            int temp =  (digits[i]+jinwei) / 10;
            digits[i] = (digits[i] + jinwei) %10;
            jinwei = temp;
        }
        digits[len-1] = digits[len-1]+jinwei;
        if (digits[len-1]>=10)
        {
            digits[len-1] = digits[len-1] % 10;
            digits.push_back(1);
        }
        reverse(digits.begin(), digits.end());

        return digits;

    }
};

如果碰到两个很大的整数相加求和（普通的整型会溢出的情况），这个思路可以拿过来直接用，在这里，会有点麻烦。可以考虑思路二

思路二：遍历一次，

这个题只是末尾加一。

从后往前遍历：
由于只是末尾的数字加一，无非两种情况，末尾的数字不等于9和等于9

• 如果不等于9， 那么直接加一即可，其他位置不用动，返回即可
• 如果等于9， 就需要把它变成0， 前一位加一
  • 而前一位又是两种情况，不等于9直接加一，等于9，再把它变成0，这一个的前一位又有两种，不等于9直接加一，等于9，变0

看出循环了吗？

即从后往前，遍历数组，如果数字不等于9， 那么加一返回，否则，把该位数字置为0，跳出循环之后， 如果还没返回，说明这些数都是0了，需要在第一位插入1.

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {

        int len = digits.size();
        for (int i=len-1; i>=0; --i)
        {
            if (digits[i] != 9)
            {
                digits[i]++;
                return digits;
            }
            else
            {
                digits[i]  = 0;
            }
        }

        digits.insert(digits.begin(), 1);
        return digits;

    }
};

对于这个题，这个是比较好的一种方式。