LeetCode（String) Medium1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

小咪咪 2023-09-27 21:54 91阅读 0赞

# 1.问题 #

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 <= 105
 *  n consists of only digits.
 *  n does not contain any leading zeros and represents a positive integer.

# 2. 解题思路 #

## 方法1： ##

> 1.  初始化最大数字为 0
> 2.  遍历输入字符串中的每个字符
> 3.  将字符转换为数字
> 4.  更新最大数字为当前数字和已知最大数字的较大值
> 5.  返回最大数字，即最小的划分数

## 方法2： ##

> 1.  找到字符串中最大的字符作为答案
> 2.  将字符转换为数字，这里使用字符 ‘0’ 的 ASCII 值来得到对应的数字
> 3.  更新答案为当前数字和已知答案的较大值

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int minPartitions(String n) {
        
            // 初始化最大数字为 0
            int maxDigit = 0;
            
            // 遍历输入字符串中的每个字符
            for (char ch : n.toCharArray()) {
        
                // 将字符转换为数字
                int digit = ch - '0';
                // 更新最大数字为当前数字和已知最大数字的较大值
                maxDigit = Math.max(maxDigit, digit);
            }
            
            // 返回最大数字，即最小的划分数
            return maxDigit;
            
        }
    }

## 代码2： ##

class Solution {
        
        
        // 找到字符串中最大的字符作为答案
        public int minPartitions(String n) {
        
            
            int ans = 0;
            for (int i = 0; i < n.length(); i++) {
        
                // 将字符转换为数字，这里使用字符 '0' 的 ASCII 值来得到对应的数字
                int digit = n.charAt(i) - '0';
                // 更新答案为当前数字和已知答案的较大值
                ans = Math.max(ans, digit);
            }
            
            return ans;
        }
    }