What is a deci-binary number?

A deci-binary number is a decimal number where each digit is either 0 or 1, and there are no leading zeros.

How do I apply a greedy strategy to this problem?

A greedy strategy involves selecting the largest possible deci-binary number at each step and reducing the number until the sum equals the given number.

How does the problem pattern relate to greedy algorithms?

The greedy choice is evident in picking the largest valid deci-binary number at each iteration, minimizing the total count of numbers needed to sum to the target.

What if the input number is very large?

The problem can still be solved efficiently by iterating over the digits, and the algorithm should handle input sizes up to 10^5 digits.

What is the time complexity of this problem?

The time complexity is O(n), where n is the length of the input string, as we process each digit once.

#1689

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

十-二进制数的最少数目

如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个十-二进制数。例如， 101 和 1100 都是十-二进制数，而 112 和 3001 不是。给你一个表示十进制整数的字符串 n ，返回和为 n 的十-二进制数的最少数目。示例 1：输入： n…

字符串贪心

题目描述

如果一个十进制数字不含任何前导零，且每一位上的数字不是 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 <= 10⁵
n 仅由数字组成
n 不含任何前导零并总是表示正整数

lightbulb

解题思路

方法一：脑筋急转弯

题目等价于找字符串中的最大数。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串长度。空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def minPartitions(self, n: str) -> int:
        return int(max(n))

speed

复杂度分析

指标	值
时间	complexity depends on iterating through each digit of n. Space complexity involves tracking values through each iteration but remains manageable within the input constraints.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to apply greedy algorithms effectively.
question_mark
Understanding how to reduce a problem to simpler subproblems.
question_mark
Proficiency in validating constraints and invariants in problem-solving.

warning

常见陷阱

外企场景

error
Forgetting to handle multiple digits efficiently while maintaining a greedy approach.
error
Not ensuring that deci-binary numbers are constructed correctly according to the problem's rules.
error
Misunderstanding the greedy choice strategy and missing edge cases.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling very large input sizes efficiently.
arrow_right_alt
Modifying the problem to use other number systems.
arrow_right_alt
Optimizing space complexity while maintaining time efficiency.

help

常见问题

外企场景

继续练习

#1702 修改后的最大二进制字符串 #1663 具有给定数值的最小字符串 #1717 删除子字符串的最大得分