Tecker Yu

1 minute read

题目描述

For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1]

Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.

// Author: Tecker
// date: 2019.2.14
// 132ms, 13.3MB beat 99.19%, 100.00%
// time: O(N), space: O(1) or O(len(K))
class Solution {
public:
    vector<int> addToArrayForm(vector<int>& A, int K) {
        // 如果 A 代表的数字比 K 小(K 最大10000)
        if (A.size()<5) {
            int t=1;
            int sum=0;
            for(int i=A.size()-1;i>=0;--i) {
                sum+=A[i]*t;
                t*=10;
            }
            // 直接转换相加,然后对 A 原地修改返回
            sum+=K;
            if (sum==0) return vector<int>{0};

            // 先向后插入低到高位再反转
            int pos=0;
            while(sum!=0) {
                if (pos>=A.size())
                    A.push_back(sum%10);
                else
                    A[pos]=sum%10;
                sum/=10;
                ++pos;
            }

            reverse(A.begin(), A.end());
            return A;
        }

        // 直接将 K 加到最低位,然后向最高位不断推进
        bool needMore = false;
        for(int i=A.size()-1;i>=0;--i) {
            A[i]+=K;
            if (A[i] < 10) break;
            if (i==0) needMore=true;
            K=A[i]/10;
            A[i]%=10;
        }

        if (!needMore) return A;

        // 前面要补1
        reverse(A.begin(), A.end());
        A.push_back(1);
        reverse(A.begin(), A.end());
        return A;
    }
};

收获

向 vector 头原地插入元素可以先反转从尾部添加再反转

reward-code
comments powered by Disqus