文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题十-二进制数的最少数目出处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}10111132示例 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≤105n \texttt{n}n仅由数字组成n \texttt{n}n不含任何前导零并总是表示正整数解法思路和算法对于字符串n nn的每一位digit \textit{digit}digit当digit 0 \textit{digit} 0digit0时至少需要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个十-二进制数做法如下。创建maxDigit \textit{maxDigit}maxDigit个与n nn长度相同的十-二进制数初始时每个十-二进制数的所有位都是0 00。允许存在前导零。对于n nn中等于maxDigit \textit{maxDigit}maxDigit的每一位将全部maxDigit \textit{maxDigit}maxDigit个十-二进制数的对应位上的值设为1 11。对于n nn中大于0 00且小于maxDigit \textit{maxDigit}maxDigit的每一位将该位的值记为digit \textit{digit}digit则digit maxDigit \textit{digit} \textit{maxDigit}digitmaxDigit从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){intmaxDigit0;intlengthn.length();for(inti0;ilength;i){intdigitn.charAt(i)-0;maxDigitMath.max(maxDigit,digit);}returnmaxDigit;}}复杂度分析时间复杂度O ( m ) O(m)O(m)其中m mm是字符串n nn的长度。需要遍历字符串n nn一次并计算最少数目。空间复杂度O ( 1 ) O(1)O(1)。