1689.十-二进制数的最少数目：一次遍历比大小（脑筋急转弯）

【LetMeFly】1689.十-二进制数的最少数目：一次遍历比大小（脑筋急转弯）

力扣题目链接：https://leetcode.cn/problems/partitioning-into-minimum-number-of-deci-binary-numbers/

如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个 十-二进制数 。例如，101 和 1100 都是 十-二进制数，而 112 和 3001 不是。

给你一个表示十进制整数的字符串 n ，返回和为 n 的 十-二进制数 的最少数目。

 

示例 1：

输入：n = "32"
输出：3
解释：10 + 11 + 11 = 32

示例 2：

输入：n = "82734"
输出：8

示例 3：

输入：n = "27346209830709182346"
输出：9

 

提示：

• 1 <= n.length <= 105
• n 仅由数字组成
• n 不含任何前导零并总是表示正整数

解题方法：遍历

123变成了000的时候，$123$就变成了$0$。

每次每个字符可以减0或1，最多几次可以将字符串减为全0？

答案是字符串中最大的那个字符对应的数字次。

• 时间复杂度$O(len(n))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-01 19:51:09
 */
class Solution {
public:
    int minPartitions(string n) {
        char M = '0';
        for (char c : n) {
            M = max(M, c);
        }
        return M - '0';
    }
};

Python

'''
LastEditTime: 2026-03-01 19:52:13
'''
class Solution:
    def minPartitions(self, n: str) -> int:
        return ord(max(n)) - ord('0')  # 记得python str不能直接相减

Java

/*
 * @LastEditTime: 2026-03-01 20:20:21
 */
class Solution {
    public int minPartitions(String n) {
        return n.chars().max().getAsInt() - '0';
    }
}

Go

/*
 * @LastEditTime: 2026-03-01 20:10:52
 */
package main

// 要的是max不是min别搞错了
func max1689(a, b rune) rune {
    if a < b {
        return b
    }
    return a
}

func minPartitions(n string) int {
    m := rune('0')
    for _, c := range n {
        m = max1689(m, c)
    }
    return int(byte(m) - '0')
}

Rust

/*
 * @LastEditTime: 2026-03-01 20:23:19
 */
impl Solution {
    pub fn min_partitions(n: String) -> i32 {
        let mut m = '0';
        for c in n.chars() {
            if c > m {
                m = c;
            }
        }
        (m as i32) - ('0' as i32)
    }
}

Rust - one line

/*
 * @LastEditTime: 2026-03-01 20:26:52
 */
impl Solution {
    pub fn min_partitions(n: String) -> i32 {
        (*n.as_bytes().iter().max().unwrap() - b'0') as i32
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源