力扣66、加一（简单）

1?题目描述

2?题目解读

????????使用非空数组表示的整数，要求将这个整数加一，返回加一后的非空数组。

3?解法一：找出最长的后缀9

????????对于加一这道题，可以通过找出非空数组中最长的后缀9，进而能够将这个非空数组表示的整数加一。

3.1?解题思路

????????在这个非空数组中，找出最长的后缀9，然后将这些9全部置为0，再将这个9后缀的上一位加一，就能够将这个由非空数组表示的整数加一。

????????如果这个非空数组中的每一位都是9，则返回由非空数组表示的n+1位整数。

3.2?设计代码

#include <iostream>
#include <vector>
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];
                for (int j = i + 1; j < n; ++j) {
                    digits[j] = 0;
                }
                return digits;
            }
        }
        // digits 中所有的元素均为 9
        vector<int> ans(n + 1);
        ans[0] = 1;
        return ans;
    }
};
int main() {
    int x[] = { 1, 2, 3 };
    vector<int> digits;
    for (int i = 0; i < 3; i++)
    {
        digits.push_back(x[i]);
    }
    Solution S;
    vector<int> ans = S.plusOne(digits);
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i];
    }
    cout << endl;
    return 0;
}

3.3?复杂度分析

• 时间复杂度：。for循环遍历了一遍非空数组元素。
• 空间复杂度：。没有使用额外的数组空间。

3.4?提交结果

4?解法二：累计9的个数

????????这一题可以先累计9的个数，然后分情况处理。

4.1?解题思路

? ? ? ? 对于累计的9的个数，如果累计的9的个数是n，那么返回的数组长度应为n+1，否则返回的数组长度应为n。

????????如果返回的数组长度是n，则从整数的个位开始，使用变量c保存各位加一后的进位情况，依次处理非空数组的每一位。

4.2?设计代码

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        int cnt = 0;  //累计为9的元素的个数
        for (int i = 0; i < n; i++)
        {
            if (digits[i] == 9) {
                cnt++;
            }
        }
        if (cnt == n) { //全部元素均为9
            vector<int> ans(n + 1);
            ans[0] = 1;
            return ans;
        }
        else {
            vector<int> ans(n);
            int c = 0;                     //表示进位
            for (int i = n - 1; i >= 0; i--)
            {
                if (i == n - 1) {          //处理最低位
                    ans[i] = digits[i] + 1;//最低位加1
                    c = ans[i] / 10;
                    ans[i] = ans[i] % 10;
                }
                else {
                    ans[i] = digits[i] + c;
                    c = ans[i] / 10;
                    ans[i] = ans[i] % 10;
                }
            }
            return ans;
        }
    }
};
int main() {
    int x[] = { 8, 9, 9, 9 };
    vector<int> digits;
    for (int i = 0; i < 4; i++)
    {
        digits.push_back(x[i]);
    }
    Solution S;
    vector<int> ans = S.plusOne(digits);
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i];
    }
    cout << endl;
    return 0;
}

4.3?复杂度分析

• 时间复杂度：。对题目给定的非空数组进行了遍历操作。
• 空间复杂度：。返回的结果使用了新的向量。

4.4?提交结果

5?解题心得

• 对于题目给定的非空数组，可以只遍历一次。
• 向量这一数据结构可以很好地处理数据。
• 对于算法题，一些解对应题目的独特方法，要比模拟法更好。