Leetcode 989. Add to Array-Form of Integer

// 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;
    }
};