1. 題目

1.1 英文題目

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

1.2 中文題目

給定兩個排序整數陣列nums1和nums2，將nums2合并為一個排序陣列nums1，

nums1和nums2中初始化的元素數量分別為m和n，假設nums1有足夠的空間(大小大于或等于m + n)來容納nums2中的其他元素，

1.3輸入輸出

1.4 約束條件

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

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

標籤：C++

上一篇：Leetcode No.66 Plus One(c++實作）

下一篇：Acwing Arithmetic Learning：資料結構（3）