ETH官方钱包

前往
大廳
主題

LeetCode - 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers 解題心得

Not In My Back Yard | 2021-06-29 00:00:03 | 巴幣 0 | 人氣 192

題目連結:


題目意譯:
一個十進位數字被稱為十進位制-二元數,如果其每個位數只會是 0 或是 1 並且沒有任何前導 0 。例如,101 和 1100 為十進位制-二元數,而 112 和 3001 則不是。

給定一個字串 n 代表著一個正的十進位整數,回傳最少需要幾個十進位制-二元數才能使得這些數字總和為 n 。

限制:
1 ≦ n.length ≦ 10 ^ 5
n 只由數字組成。
n 不含任何前導 0 ,並且代表著一個正整數。



範例測資:
範例 1:
輸入: n = "32"
輸出: 3
解釋: 10 + 11 + 11 = 32

範例 2:
輸入: n = "82734"
輸出: 8

範例 3:
輸入: n = "27346209830709182346"
輸出: 9


解題思維:
既然每個十進位制-二元數只會出現數字 0 或是 1,那麼對於 n 裡面的最大的位數 x ,我們就需要至少 x 個十進位制-二元數要在該位置為 1 才能使得該位置總和為 x 。

而因為該位數是最大的,所以其他位數所需數便不會超過它。

因此所求即是 x 。




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

創作回應

追蹤 創作集

作者相關創作

更多創作