LeetCode - 556. Next Greater Element III 解題心得 - inversion的創作 - 巴哈姆特
前往
大廳
主題

LeetCode - 556. Next Greater Element III 解題心得

Not In My Back Yard | 2022-11-26 12:00:01 | 巴幣 0 | 人氣 163

題目連結:


題目意譯:
給定一正整數 n,找到最小的整數使得其每個位數恰好可以對應到整數 n 的位數(譯注:也就是每個位數存在於 n 的位數中)並且其值大於 n。如果不存在這樣子的正整數,回傳 -1。

注意到回傳的整數應可被容納進一個 32 位元有號整數(譯注:原文忘記寫「有號」(Signed)了,因此補上),如果一個有一個合法答案文在但無法容納進 32 位元有號整數中,回傳 -1。

限制:
1 ≦ n ≦ 2 ^ 31 - 1



範例測資:
範例 1:
輸入: n = 12
輸出: 21

範例 2:
輸入: n = 21
輸出: -1


解題思維:
其實就是找「下一個排列」,參見這題。當找不到下一個排列的時候,就代表不存在題目所述的正整數,因此回傳 -1。

而實際上在 C++ 中「下一個排列」不用自己寫:把 n 轉成一個字串 s,然後呼叫 next_permutation(s.begin(), s.end()) 即可。當其回傳值為 0 時,代表不存在下一個排列;反之,代表存在且 s 將變為下一個排列,把 s 轉回數字即可(但是記得先判斷是否會大過 2147483647)。




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

創作回應

更多創作