Halo

A magic place for coding

0%

LeetCode解题报告(383) -- 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

Problem

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:

1
2
3
Input: n = "32"
Output: 3
Explanation: 10 + 11 + 11 = 32

Example 2:

1
2
Input: n = "82734"
Output: 8

Example 3:

1
2
Input: n = "27346209830709182346"
Output: 9

Constraints:

  • 1 <= n.length <= 105
  • n consists of only digits.
  • n does not contain any leading zeros and represents a positive integer.

Analysis

  这道题题目给出一个数字,要求用01组成的十进制数去构成,问需要多少个这种数。除了最高位外,每一个位置我们都可以根据需要选择0或者1,所以我们只需要关注最大的那个位即可。比如1234,我们只需要关注最后一位即可,因为最后一位满足了,前面的总能找到方法满足。最后一位是4,表示至少要有4个数,而且这四个数最后一位都是1,这样才能构成。

  所以这道题目实际上是一道智力题,我们只需要找到数字中最大的位,那个值就是所需要的deci-binary的数量。


Solution

  无


Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int minPartitions(string n) {
char ch = '0';
int size = n.size();
for (int i = 0; i < size; i++) {
ch = (char)max(ch, n[i]);
}
return ch - '0';
}
};

Summary

  这类智力题对coding考察并不多,主要还是要多观察。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels