企业官网建设流程全解析

题目

标题和出处

标题：十-二进制数的最少数目

出处：1689. 十-二进制数的最少数目

难度

4 级

题目描述

要求

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

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

示例

示例 1：

输入：n = "32" \texttt{n = "32"}n = "32"
输出：3 \texttt{3}3
解释：10 + 11 + 11 = 32 \texttt{10} + \texttt{11} + \texttt{11} = \texttt{32}10+11+11=32

示例 2：

输入：n = "82734" \texttt{n = "82734"}n = "82734"
输出：8 \texttt{8}8

示例 3：

输入：n = "27346209830709182346" \texttt{n = "27346209830709182346"}n = "27346209830709182346"
输出：9 \texttt{9}9

数据范围

• 1 ≤ n.length ≤ 10 5 \texttt{1} \le \texttt{n.length} \le \texttt{10}^\texttt{5}1≤n.length≤105
• n \texttt{n}n仅由数字组成
• n \texttt{n}n不含任何前导零并总是表示正整数

解法

思路和算法

对于字符串n nn的每一位digit \textit{digit}digit，当digit > 0 \textit{digit} > 0digit>0时至少需要digit \textit{digit}digit个十-二进制数作为加数才能满足所有加数之和的当前位等于digit \textit{digit}digit。理由如下。

• 如果不发生进位，则如果作为加数的十进制数个数小于digit \textit{digit}digit，则一定存在加数的该位上的值大于1 11，不符合十-二进制数的要求。

• 如果发生进位，则进位来源于更低位，此时至少需要10 × digit 10 \times \textit{digit}10×digit个十-二进制数，否则一定存在加数的更低位上的值大于1 11，不符合十-二进制数的要求。

将字符串n nn中的最大的一位数记为maxDigit \textit{maxDigit}maxDigit，则和为n nn的十-二进制数的最少数目一定大于等于maxDigit \textit{maxDigit}maxDigit。可以构造出和为n nn的maxDigit \textit{maxDigit}maxDigit个十-二进制数，做法如下。

1. 创建maxDigit \textit{maxDigit}maxDigit个与n nn长度相同的十-二进制数，初始时每个十-二进制数的所有位都是0 00。允许存在前导零。

2. 对于n nn中等于maxDigit \textit{maxDigit}maxDigit的每一位，将全部maxDigit \textit{maxDigit}maxDigit个十-二进制数的对应位上的值设为1 11。

3. 对于n nn中大于0 00且小于maxDigit \textit{maxDigit}maxDigit的每一位，将该位的值记为digit \textit{digit}digit，则digit < maxDigit \textit{digit} < \textit{maxDigit}digit<maxDigit，从maxDigit \textit{maxDigit}maxDigit个十-二进制数中任选digit \textit{digit}digit个数将对应位上的值设为1 11。

由于每次对maxDigit \textit{maxDigit}maxDigit个十-二进制数的赋值都只是对其中的一个数位操作，且每次操作的数位各不相同，因此构造出的和为n nn的maxDigit \textit{maxDigit}maxDigit个十进制数都符合十-二进制数的要求。

根据上述分析，可以使用贪心的思想计算和为n nn的十-二进制数的最少数目。

具体做法是，遍历字符串n nn并得到最大的一位数maxDigit \textit{maxDigit}maxDigit，则maxDigit \textit{maxDigit}maxDigit即为最少数目。

代码

classSolution{publicintminPartitions(Stringn){intmaxDigit=0;intlength=n.length();for(inti=0;i<length;i++){intdigit=n.charAt(i)-'0';maxDigit=Math.max(maxDigit,digit);}returnmaxDigit;}}

复杂度分析

• 时间复杂度：O ( m ) O(m)O(m)，其中m mm是字符串n nn的长度。需要遍历字符串n nn一次并计算最少数目。

• 空间复杂度：O ( 1 ) O(1)O(1)。