前往
大廳
主題

LeetCode - 2165. Smallest Value of the Rearranged Number 解題心得

Not In My Back Yard | 2022-09-16 12:00:09 | 巴幣 0 | 人氣 126

題目連結:


題目意譯:
你被給定一整數 num。重新排列 num 的每一位數使其沒有任何前導零並且其值最小化。

回傳這個重新排列後最小化的數字。

注意數字的正負號在重新排列的過程中不會變動。

限制:
-10 ^ 15 ≦ num ≦ 10 ^ 15



範例測資:
範例 1:
輸入: num = 310
輸出: 103
解釋: 310 可能的位數排列為 013 、 031 、103 、 130 、 301 、 310.
最小的且不包含前導零的數值為 103。

範例 2:
輸入: num = -7605
輸出: -7650
解釋: -7605 其中幾個可能的位數排列為 -7650 、 -6705 、 -5076 、 -0567。
最小的且不包含前導零的數值為 -7650。


解題思維:
首先我們來看 num 是負數的時候,可以看到負數的位數只要從大排到小即可以獲得最小值(因為這樣子產出的「絕對值」最大,加上負號就變為最小了)。而且不需要擔心前導零,因為位數由大排到小,零會排到最後面變成末尾零。例如範例二的情況。

接著是 num 是 0 的時候,毫無反應,就是一個 0。什麼都不必做,直接回傳即可。

最後比較麻煩的是 num 是正數的時候,此時如果我們直接從小排到大,只要位數中有 0 就會產生出前導零。那要怎麼解決前導零呢?很簡單,把隨便一個不是 0 的位數拉到最前面當開頭即可。而拉過來的數字越小,整體就越小。因此我們要做的是去找數字最小的非零位數,將其作為開頭;剩下的位數由小排到大即可獲得最小值。例如範例一的情況。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作