📘 題目敘述
一個十進位數如果滿足每一位數字都只會是 0 或 1，且沒有前導零，則稱這個十進位數為 deci-binary。 例如 101 和 1100 是 deci-binary，而 112 和 3001 不是。
給你一個字串 n，代表一個正的十進位整數，請回傳最少需要多少個正的 deci-binary 數字，才能讓它們的總和等於 n。
條件限制
1 <= n.length <= 10^5n只包含數字字元n沒有前導零，且代表一個正整數
🧠 解題思路
這題的核心其實就是看 n 裡面最大的那個數字是多少。
理由是：
每個 deci-binary 的每一位最多只能貢獻 1。 所以如果 n 的某一位是 d，代表那一位總共需要湊出 d，而每個數在那一位最多出 1，所以至少要 d 個數才能湊出那一位。
因此整個 n 的最少數量，至少要大於等於所有位數的最大值。
反過來也一定做得到： 假設最大位數是 ans，我就可以用 ans 個 deci-binary 數字去分配每一位的 1，讓每一位的 1 的個數剛好等於 n 那一位的數字，這樣就能組成 n。
所以答案就是：
n中出現的最大數字。
我的程式碼就是掃一遍字串，找到最大 digit。
所有變數
ans：目前掃到的最大 digit（最後回傳它）
🪜 主要流程步驟
1. 初始化 ans = 0
一開始先假設最大 digit 是 0。
2. 掃過 n 的每個字元，更新最大 digit
對每個字元 a：
a - '0'會得到它對應的數字- 用
ans = max(ans, a - '0')更新最大值
3. 回傳 ans
掃完後 ans 就是最大 digit，也就是最少需要的 deci-binary 數量。
⏱️ 複雜度
- 時間複雜度：
O(|n|)只掃一遍字串。 - 空間複雜度：
O(1)
💻 程式碼實作
class Solution {
public:
int minPartitions(string n) {
int ans = 0;
for (char a : n) {
ans = max(a - '0', ans);
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/