题目描述
A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.
Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.
Example 1:
Input: n = “32”
Output: 3
Explanation: 10 + 11 + 11 = 32
Example 2:
Input: n = “82734”
Output: 8
Example 3:
Input: n = “27346209830709182346”
Output: 9
Constraints:
- 1 <= n.length <= 10^5
- n consists of only digits.
- n does not contain any leading zeros and represents a positive integer.
题目分析
刚看到问题时，初步想法是观察最低位是几，假设为x，那么说明至少需要x个最低位为1的数；
确定最低位后，再继续看高一位的，假设为y；如果 y <= x，那么第一步中确定的这些数，十位上设置y个1，(x-y)个0就能满足需求；如果y > x，说明至少需要y个十位上为1的数才能满足。
继续按照规则推理到最高位，我们可以发现，数字的个数跟n的位数无关，只跟n的组成数字中最大的那个数字有关；因此，我们可以写出如下求解:
示例代码
func minPartitions(n string) int {
// 初始化为1
ans := byte('1')
for i := 0; i < len(n); i++ {
// 不断迭代更新为最大的数字(byte表示的数字)
if n[i] > ans {
ans = n[i]
}
}
// byte转int
return int(ans - byte('0'))
}