Easy

题目描述

给你一个正整数 n。

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

将 n 表示为仅使用十进制组件的和，并使用尽可能少的十进制组件。

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

示例 1：

输入：n = 537
输出：[500,30,7]
解释：我们可以将 537 表示为 500 + 30 + 7。无法用少于 3 个十进制组件来表示 537。

示例 2：

输入：n = 102
输出：[100,2]
解释：我们可以将 102 表示为 100 + 2。102 不是十进制组件，这意味着需要 2 个十进制组件。

示例 3：

输入：n = 6
输出：[6]
解释：6 是一个十进制组件。

约束条件：

  • 1 <= n <= 10^9

提示：

  • 从个位开始逐位分解数字。
  • 每个非零数字贡献一个十进制组件。
  • 收集所有组件并按降序返回。

解题思路

这道题的核心思路是将一个数字分解为其各个位数上的值乘以相应的 10 的幂。

解法分析： 十进制组件的定义是单个数字（1-9）与 10 的非负次幂的乘积。实际上，任何正整数都可以按位分解：

  • 个位数字 × 10^0
  • 十位数字 × 10^1
  • 百位数字 × 10^2
  • 以此类推…

例如 537 = 5×100 + 3×10 + 7×1 = 500 + 30 + 7

算法步骤：

  1. 从右到左（个位开始）逐位提取数字
  2. 对于每个非零位，计算该位数字乘以对应的 10 的幂
  3. 将结果添加到答案数组中
  4. 由于我们是从低位开始处理，最后需要反转数组得到降序结果

时间复杂度： O(log n)，其中 log n 是数字的位数 空间复杂度： O(log n)，用于存储结果数组

这种方法直观且高效，是最优解法。

代码实现

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

class Solution:
    def decimalRepresentation(self, n: int) -> List[int]:
        result = []
        power = 1
        
        while n > 0:
            digit = n % 10
            if digit != 0:
                result.append(digit * power)
            n //= 10
            power *= 10
        
        return result[::-1]

public class Solution {
    public int[] DecimalRepresentation(int n) {
        List<int> result = new List<int>();
        int power = 1;
        
        while (n > 0) {
            int digit = n % 10;
            if (digit != 0) {
                result.Add(digit * power);
            }
            n /= 10;
            power *= 10;
        }
        
        result.Reverse();
        return result.ToArray();
    }
}

var decimalRepresentation = function(n) {
    const result = [];
    let power = 1;
    
    while (n > 0) {
        const digit = n % 10;
        if (digit !== 0) {
            result.push(digit * power);
        }
        n = Math.floor(n / 10);
        power *= 10;
    }
    
    return result.reverse();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)需要处理数字的每一位，位数为 log₁₀(n)
空间复杂度O(log n)结果数组最多包含 log₁₀(n) 个元素