Leetcode066

LeetCode066：加一         给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以零开头。 ```cpp 示例 1:

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

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

#### 解法一：分情况讨论(执行用时 4ms，内存消耗6.6MB)

```cpp
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int Size = digits.size();
        digits[Size - 1] += 1; //先给末尾元素加1
        if (Size == 1 && digits[0] <10) //讨论digits只有一个元素，且该元素小于9这种情况
        {
            return digits;
        }
        else if (Size == 1 && digits[0] >9)  //讨论digits = [9] 这种情况
        {
            int first = digits[0] / 10;
            digits.push_back(first);
            digits[0] %= 10;
            swap(digits[0], digits[1]);
            return digits;
        }
        //一般情况
        for (int i = Size - 1; i>0; --i)
        {
            if (digits[i]>9)
            {
                digits[i] %= 10;
                digits[i - 1] += 1;
            }
            //讨论原数组中第一个元素等于9时的情况
            if ((i - 1) == 0 && digits[0]>9)
            {
                int second = digits[0] / 10;
                digits.push_back(second);
                digits[0] %= 10;
                for (int j = 0; j <= Size; j++)
                    swap(digits[j], digits[Size]);
            }
        }
        return digits;

    }
};

解法二：模拟十进制加法器 (执行用时 0ms，内存消耗6.6MB)

/******************************************************
模拟十进制加法器 (执行用时 0ms，内存消耗6.6MB)
思路：从末位向前逐位模拟十进制加法器，首位进行单独判断
***********************************************************/
class Solution2 {
public:
    vector<int> plusOne(vector<int>& digits) {
        int size = digits.size();
        for (int i = size - 1; i >= 0; --i) {
            if (digits[i] < 9) {
                ++digits[i];
                return digits;
            }
            if (i == 0) {  //全是9的时候的情况
                digits[i] = 1;
                digits.push_back(0);
            }
            else
                digits[i] = 0;
        }
        return digits;
    }
};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> nums;
    cout << "请输入数组的大小 Size：" << endl;
    int Size;
    cin >> Size;
    int Currval;
    cout << "请输入数组的元素：" << endl;
    for (int i = 0; i < Size; i++)
    {
        cin >> Currval;
        nums.push_back(Currval);
    }

    Solution2 answer;
    answer.plusOne(nums);

    //迭代器遍历输出加一后的数组
    vector<int>::iterator it;
    for (it = nums.begin(); it != nums.end(); ++it)
        cout << *it << " ";

    cout << endl;

    for (auto n : nums)
        cout << n << " ";


    system("pause");
    return 0;
}