3697. 计算十进制表示

题目描述

给你一个 正整数 n。

如果一个正整数可以表示为 1 到 9 的单个数字和 10 的非负整数次幂的乘积，则称这个整数是一个 10 进制分量。例如，500、30 和 7 是 10 进制分量 ，而 537、102 和 11 则不是。

请将 n 表示为若干仅由 10 进制分量组成的和，且使用的 10 进制分量个数最少。

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

示例 1：

输入：n = 537

输出：[500,30,7]

解释：

我们可以将 537 表示为500 + 30 + 7。无法用少于 3 个 10 进制分量表示 537。

示例 2：

输入：n = 102

输出：[100,2]

解释：

我们可以将 102 表示为100 + 2。102 不是一个 10 进制分量，因此需要 2 个 10 进制分量。

示例 3：

输入：n = 6

输出：[6]

解释：

6 是一个 10 进制分量。

提示：

1 <= n <= 10⁹

解法

方法一：模拟

我们可以不断地对 \(n\) 进行取模和整除操作，取模得到的值乘以当前的位值 \(p\) 就是一个 10 进制分量。如果取模的结果不为 \(0\)，我们就将这个分量加入答案中。然后我们将 \(p\) 乘以 \(10\)，继续处理下一个位。

最后，我们将答案反转，使其按降序排列。

时间复杂度 \(O(\log n)\)，其中 \(n\) 是输入的正整数。空间复杂度 \(O(\log n)\)，用于存储答案。

Python3JavaC++GoTypeScript

class Solution:
    def decimalRepresentation(self, n: int) -> List[int]:
        ans = []
        p = 1
        while n:
            n, v = divmod(n, 10)
            if v:
                ans.append(p * v)
            p *= 10
        ans.reverse()
        return ans

class Solution {
    public int[] decimalRepresentation(int n) {
        List<Integer> parts = new ArrayList<>();
        int p = 1;
        while (n > 0) {
            int v = n % 10;
            n /= 10;
            if (v != 0) {
                parts.add(p * v);
            }
            p *= 10;
        }
        Collections.reverse(parts);
        int[] ans = new int[parts.size()];
        for (int i = 0; i < parts.size(); ++i) {
            ans[i] = parts.get(i);
        }
        return ans;
    }
}

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

func decimalRepresentation(n int) []int {
    ans := []int{}
    p := 1
    for n > 0 {
        v := n % 10
        n /= 10
        if v != 0 {
            ans = append(ans, p*v)
        }
        p *= 10
    }
    slices.Reverse(ans)
    return ans
}

function decimalRepresentation(n: number): number[] {
    const ans: number[] = [];
    let p: number = 1;
    while (n) {
        const v = n % 10;
        n = (n / 10) | 0;
        if (v) {
            ans.push(p * v);
        }
        p *= 10;
    }
    ans.reverse();
    return ans;
}

3697. 计算十进制表示

题目描述

解法

方法一：模拟

评论