LeetCode Ts-3697. Compute Decimal Representation

    AllenLi
    CodingLeetCode Js-Math

    You are given a positive integer n.
    A positive integer is a base-10 component if it is the product of a single digit from 1 to 9 and a non-negative power of 10. For example, 500, 30, and 7 are base-10 components, while 537, 102, and 11 are not.
    Express n as a sum of only base-10 components, using the fewest base-10 components possible.
    Return an array containing these base-10 components in descending order.

    你給予一個正整數 n。
如果一個正整數是 1 ~ 9 之間的數值，則該正整數為十進位。
舉例，500, 30, 和 7 是十進位制，而 537, 102, 11 不是。
將 n 表示為僅由十進制的數值所組成，並盡可能使用最少的十進制數值。
回傳一個包含這些十進制數值的陣列，按降冪排序。

    Example 1:

    Input: n = 537
Output: [500,30,7]
Explanation:
We can express 537 as 500 + 30 + 7. It is impossible to express 537 as a sum using fewer than 3 base-10 components.

    Example 1:

    Input: n = 102
Output: [100,2]
Explanation:
We can express 102 as 100 + 2. 102 is not a base-10 component, which means 2 base-10 components are needed.

    Solution:
    這題可以看作是數學的題目，我們需要找出每個有效的數值，像是 0 在十位數的時候為無效數值，並乘上它所在位置對應的十進位倍數。
    我們可以對應每個位數（個、十、百、千…等），並取出該位數字。
    若數字為 0（例如十位數是 0），則該位數不需要採用計算。
    否則，將數字乘以該位數的十進位倍數後存入結果。

    PS. 我一開始是用 unshift() 插入元素的做法，但是這種做法效率不佳(可見此文章備註說明)，后調整為正向累加結果後，再做反轉陣列的效果比較好。

    Code 1: BigO(n)

    function decimalRepresentation(n: number): number[] {
    let num: number = n;
    let components: number[] = [];
    let placeValue = 1;

    while (num > 0) {
        const digit: number = num % 10;
        if (digit !== 0) {
            components.push(digit * placeValue);
        }
        num = Math.floor(num / 10);
        placeValue *= 10
    }
    return components.reverse();
};

    FlowChart:
    Example 1

    Input: n = 537

digit 7, components [ 7 ], num 53, placeValue 10
digit 3, components [ 7, 30 ], num 5, placeValue 100
component [ 500, 30, 7 ] -> components.reverse() [ 500, 30, 7 ]

    Example 2

    Input: n = 102

digit 2, components [ 2 ], num 10, placeValue 10
digit 0, components [ 2 ], num 1, placeValue 100
digit 1, components [ 2, 100 ], num 0, placeValue 1000
component [ 2, 100 ] -> components.reverse() [ 100, 2 ]

    Remark:
    先做好十進位制的運算，最後再 reverse() 回來，會比使用 unshift() 的方式好，因為 unshift() 的原生做法會把元素插在陣列的最前面，但是他是對記憶體做類似動態陣列的操作，他會把原本的元素往後移一格，再把新元素放到 index = 0 的位置，時間複雜度為 O(n)。
    而 push() + reverse() 的做法是 push 元素在陣列最後面 O(1)，接著 只需要 reverse() 一次這個反轉 O(n) 的操作 。

    Related Posts