3697. 计算小数表示

题目描述

给你一个正整数 n。

如果一个正整数是 1 到 9 中的一个数字与 10 的一个非负次幂的乘积，那么它就是一个十进制分量。例如，500、30 和 7 是十进制分量，而 537、102 和 11 不是。

将 n 表示为仅由十进制分量组成的和，并使用最少的十进制分量。

返回一个包含这些十进制分量的数组，按降序排列。

解题思路

这是一个直接的实现问题。关键的洞察是，任何正整数都可以唯一地表示为其各位数字乘以 10 的幂的和。例如，$123 = 1 \cdot 10^2 + 2 \cdot 10^1 + 3 \cdot 10^0$。这个展开式中的每一项都是一个十进制分量。这种分解也使用了最少数量的分量。

算法从右到左（从最低有效位到最高有效位）遍历数字 n 的各位。在每一步中，我们提取最后一位数字，将其乘以相应的 10 的幂，如果结果非零，则将其添加到我们的分量列表中。然后我们通过整除从 n 中移除最后一位数字，并增加 10 的幂。

由于我们从右到左处理数字，得到的分量将是升序的。问题要求分量按降序排列，所以我们只需在返回之前反转列表。

class Solution {
public:
    vector<int> decimalRepresentation(int n) {
        vector<int> ans;
        long long pow = 1;
        while (n > 0) {
            int digit = n % 10;
            if (digit > 0) {
                ans.push_back(digit * pow);
            }
            n /= 10;
            pow *= 10;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

复杂度分析

• 时间复杂度: $O(\log_{10} n)$，因为我们对数字的每一位只处理一次。
• 空间复杂度: $O(\log_{10} n)$，用于存储结果的十进制分量。