Number of digit one

力扣233

Posted by songjiu on May 30, 2019

统计n以内数字1出现的次数。

题目概述

题目概述

题目分析

最早的想法就是从0到n遍历一遍,把每一个数字当中出现的1都数一遍,但是这种方法铁超时,因此考虑别的方法。从网上寻找了许多相关的解决方法之后,我感觉其中一种通过计算数字每一位当中1的数目的方式比较好,不但将代码写成python之后通俗易懂而且具有延展性,而且可以用作统计出现的2、3…n。
从该数字的个位开始向最高位遍历,确定每一位当中1的个数,再将其累加。设当前判断的位为i位,i左边的数字为p,右边的数字为q。如下图所示:
首先确定的是,当某一位的值小于1的时候(也就是等于0的时候),对于该位来说,q不会增加该位1的个数,只有通过p退位,才有机会出现1(比如:123406789当中,对于0存在的这一位,无论6789怎么变化都不会为该位增加1的个数,唯一的机会就是1234退位成1233,这样这位才会出现1)

首先判断个位的1有多少个

当个位为0的时候,如上文所示,该位的1的个数完全由p来决定,个数为p个(比如123450这个数字,个位的1可以由“00000”1到“12344”1,一共12345个,也就是p的值)。
当个位的值大于等于1的时候,不依靠p他自己也可以提供一个1,所以总数目再+1。(即增加了123451这个值)

然后判断中间各位的1的数目

首先还是当该值为0的时候,同样仅仅受制于p,如上文。
但是这里的1的个数不再是p个了,而是 p*10^(i-1) 个,如(1234x6789这个数字,当前位是x,那么p可以决定的数字1由000110000到123510000肯定都是满足的,所以一共有p*10^i-1个数字1)
当该值为1的时候,除了p*10^(i-1)个1以外(如上文所示),他还可以拥有q+1个1,如(1234x6789这个数字,此时x=1,为123416789,其中1的右部分q可以决定的1的数目即为6789+1=6790个,即000010000到000016789)
当该值大于1的时候,除了p*10^(i-1)个1以外(如上文所示),他还可以拥有10^(i-1)个1,如(1234x6789这个数字,此时x=2,为123426789,那么从000010000到000019999都可以包含一个1,一共1 * 10^(i-1)个1即1*10^(5-1)=10000个)。

最后判断最高位的1的数目

这个时候没有p了,所以最高位的1的数目完全取决于它本身与q的值。 当最高位为0的时候,没有p就没有1。
当最高位为1的时候,有q个1(如上文所示)。
当最高为大于1的时候,有1*10^(i-1)个1(如上文所示)。

改进

解决了1的个数的问题,可以进而改变参数解决0-9的任意问题。

代码

    def countDigitOne(self, n: int) -> int:
        #n=10
        if n<=0:
            return 0
        count = 0
        n=str(n)
        for i in range(len(n)-1,-1,-1):
            p=n[0:i]#左
            q=n[i+1:]#右
            if i==len(n)-1:#个位有多少个1
                if len(p)>0:
                    count+=int(p)
                if int(n[i])>=1:
                    count+=1
            elif i>0 and i<len(n)-1:#中间位有多少个1
                count+=int(p)*10**len(q)
                if int(n[i])==1:
                    count+=int(q)+1
                elif int(n[i])>1:
                    count+=10**len(q)
            else:#最高位有多少个1
                if int(n[i])==1:
                    count+=int(q)+1
                elif int(n[i])>1:
                    count+=10**len(q)
        return count