1. 題目

1.1 英文題目

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

1.2 中文題目

給定一個由整陣列成的非空陣列所表示的非負整數，在該數的基礎上加一，

最高位數字存放在陣列的首位， 陣列中每個元素只存盤單個數字，

你可以假設除了整數 0 之外，這個整數不會以零開頭，

1.3輸入輸出

1.4 約束條件

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

2. 實驗平臺

IDE：VS2019
IDE版本：16.10.1
語言：c++11

3. 程式

3.1 測驗程式

#include "Solution.h"
#include <vector>	// std::vector
#include<iostream>	// std::cout
using namespace std;

// 主程式
void main()
{
	// 輸入
	vector<int> digits = { 9,9,9 };

	Solution solution; // 實體化Solution
	vector<int> output = solution.plusOne(digits); // 主功能

	// 輸出
	for (auto i : output)
		cout << i;
}

3.2 功能程式

3.2.1 最優演算法

（1）代碼

#pragma once
#include<vector>    // std::vector
//#include<limits.h>  // INT_MIN整型最小值
#include<algorithm> // std::max
using namespace std;

//主功能
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) 
    {
        int carry = 1; // 存放進位數字
        int length = digits.size(); 
        for (int i = length - 1; i >= 0; --i) 
        {
            // 若某一位沒有上一位的進位，則再高位都不會再有進位，也就是說高位都保持不變，可以直接回傳結果
            if (carry == 0) return digits; 

            // 若有進位，則需要計算進位值及其當前位數字，也就是需要進行回圈
            int sum = digits[i] + carry;
            digits[i] = sum % 10;
            carry = sum / 10;
        }

        // 若是最高位還需要進位，則需要在最高位插入"1"
        if (carry == 1) digits.insert(digits.begin(), 1);
        return digits;
    }
};

參考：https://www.cnblogs.com/grandyang/p/4079357.html

（2）解讀

參考：
https://blog.csdn.net/linhuanmars/article/details/22365957
https://blog.csdn.net/Tianc666/article/details/105769411

3.2.2 直觀求解法

（1）代碼1

#pragma once
#include<vector>    // std::vector
//#include<limits.h>  // INT_MIN整型最小值
#include<algorithm> // std::max
using namespace std;

//主功能
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        vector<int> digitsNew(digits.size() + 1);//新數字(逆序）
        int count = 1;//進位（0/1)
        for (int i = 0; i < digits.size(); i++)
        {
            int tempOrder = digits.size() - 1 - i;
            int sumTemp = digits[tempOrder] + count;
            count = sumTemp / 10;
            digitsNew[i] = sumTemp % 10;+
            if (i == digits.size() - 1)
                digitsNew[i + 1] = count;
        }

        // 逆序轉正序
        int length = digits.size() + digitsNew.back();
        vector<int> digitsFinal(length);
        for (int i = length - 1; i >= 0; i--)
            digitsFinal[i] = digitsNew[length - 1 - i];
        return digitsFinal;
    }
};

（2）思路

先逆轉求值，再逆轉過來，但是我的代碼寫法不太簡潔，可以參考代碼2

（3）代碼2

#pragma once
#include<vector>    // std::vector
//#include<limits.h>  // INT_MIN整型最小值
#include<algorithm> // std::max
using namespace std;

//主功能
class Solution 
{
public:
    vector<int> plusOne(vector<int> &digits) 
    {
        vector<int> ret(digits);
        reverse(ret.begin(), ret.end());

        int flag = 1;
        for(int i = 0; i < ret.size(); i++)
        {
            ret[i] += flag;
            //這里的flag的結果要么是0，要么是1
            flag = ret[i] / 10;
            ret[i] %= 10; 
        }

        if (flag == 1)
            ret.push_back(1);

        reverse(ret.begin(), ret.end());

        return ret;
    }
};

參考：https://theonegis.blog.csdn.net/article/details/44258329

3.2.3 其他演算法

（1）代碼

#pragma once
#include<vector>    // std::vector
//#include<limits.h>  // INT_MIN整型最小值
#include<algorithm> // std::max
using namespace std;

//主功能
class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        int n = digits.size();
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] == 9) digits[i] = 0;
            else {
                digits[i] += 1;
                return digits;
            }
        }
        if (digits.front() == 0) digits.insert(digits.begin(), 1);
        return digits;
    }
};

參考：https://www.cnblogs.com/grandyang/p/4079357.html

（2）解讀

將一個數字的每個位上的數字分別存到一個一維向量中，最高位在最開頭，我們需要給這個數字加一，即在末尾數字加一，如果末尾數字是9，那么則會有進位問題，而如果前面位上的數字仍為9，則需要繼續向前進位，具體演算法如下：首先判斷最后一位是否為9，若不是，直接加一回傳，若是，則該位賦0，再繼續查前一位，同樣的方法，知道查完第一位，如果第一位原本為9，加一后會產生新的一位，那么最后要做的是，查運算完的第一位是否為0，如果是，則在最前頭加一個1，
參考：https://www.cnblogs.com/grandyang/p/4079357.html

標籤：其他

上一篇：精盡Spring Boot原始碼分析 - 序言

下一篇：Spring Boot動態權限變更實作的整體方案