前往
大廳
主題

LeetCode - 2160. Minimum Sum of Four Digit Number After Splitting Digits 解題心得

Not In My Back Yard | 2023-04-03 12:00:01 | 巴幣 100 | 人氣 155

題目連結:


題目意譯:
你被給定一正整數 num,其由恰好四個位數組成。由 num 中的數字將 num 分成兩個新整數 new1 和 new2。new1 和 new2 中前導零是允許的,num 中所有數字必須都被使用。

例如說,給定 num = 2932,你有著下列數字:兩個 2、一個 9 和一個 3。一些可能的 [new1, new2] 數對為 [22, 93] 、 [23, 92] 、 [223, 9] 和 [2, 329]。

回傳 new1 和 new2 最小可能的總和。

限制:
1000 ≦ num ≦ 9999


範例測資:
範例 1:
輸入: num = 2932
輸出: 52
解釋: 一些可能的 [new1, new2] 數對為 [29, 23] 、 [223, 9] 等等。
最小可能的總和可以從數對 [29, 23] 得到:29 + 23 = 52。

範例 2:
輸入: num = 4009
輸出: 13
解釋: 一些可能的 [new1, new2] 數對為 [0, 49] 、 [490, 0] 等等。
最小可能的總和可以從數對 [4, 9] 得到:4 + 9 = 13。


解題思維:
直接窮舉出所有可能性:每個位數可以屬於 new1 或是 new2,因此會有 2 ^ 4 種可能性。例如說 4009 其中一種可能為 4 和第一個 0 屬於 new1 且第二個 0 和 9 屬於 new2。

而對於每一種可能性可能有多種排列組合。承上例,4 和 0 屬於 new1,所以 new1 可以 04 或是 40。而為了得到最小的總和我們可以直接選擇最小的數字也就是 04;而 new2 也是同理。這樣便可以找到這個可能性的最小數對。

然後我們把每一種可能性得到的最小數對加總後取最小值即可。




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

創作回應

更多創作