Leetcode 加一

地址：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/27/

一、题目

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

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

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

示例 1:

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

示例 2:

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

二、我的解决方案

首先想到用一个int型整数来保存输入的这个数，因为整数+1很容易实现，把数组的各个数字合并成一个整数以及将一个整数拆分成单个数字都很容易实现，所以写出了这份代码，也理所当然的造成了太大的数溢出的问题：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        vector<int> plusone;
        int integer = digits[0];    //默认输入数组非空，最小为0

        if (digits.size() > 0) {    //计算出对应的数字integer
            for (int i = 1; i < digits.size(); i++) {
                integer = integer * 10 + digits[i];
            }
        }
        integer += 1;   //整数+1

        while (integer!=0) {    //将整数拆分成单个数字并逆序保存到plusone数组中
            plusone.insert(plusone.end(), integer % 10);
            integer /= 10;
        }

        for (int i = 0; i < plusone.size() / 2; i++) {   //逆序排列得出结果
            int temp = plusone[i];
            plusone[i] = plusone[plusone.size() - 1 - i];
            plusone[plusone.size() - 1 - i] = temp;
        }
        return plusone;
    }
};

例如当输入的数字为[9,8,7,6,5,4,3,2,1,0]时，将得到错误的结果[1,2,8,6,6,0,8,6,1,9]。

改进后的代码：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int car = 1;   //对最后一位+1以及判断当前项是否有进位

        for (int i = digits.size() - 1; i >= 0; i--) {  //从最后一项开始往前遍历
            if (car == 1) {
                if (digits[i] == 9) {   //如果当前项为9并且要+1，则当前项置0，进位标志置1
                    digits[i] = 0;
                    car = 1;
                    continue;
                }
                else {    //如果当前项非9并且要+1，当前项直接+1，并将进位标志置0
                    digits[i] += 1;
                    car = 0;
                    break;    //一旦进位标志置0表明往前不会再有进位，无需继续遍历
                }
            }
        }

        if (car == 1)  //如果上面循环结束后进位标志仍为1，则还需要在数组最前面补1
            digits.insert(digits.begin(), 1);

        return digits;
    }
};

很明显，改进后的代码相对更简洁一些，同时不再受限于整型溢出导致的错误结果。

前面的代码思路比较简单，也更切合我们日常生活中整数简单+1的操作；事实上改进后的代码思路也并不是很复杂，相对于前面的方法不是那么的抽象，逻辑上略微复杂一点点，因为要把+1的操作作用到单个数字上，要考虑进位的处理（也就是9+1=10的情况下，应该是当前位置0，进位导致前一位要+1）。

不管怎么说，应该可以说后者在各方面都是要优于前者的。