`
frank-liu
  • 浏览: 1661485 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

leetcode: Number of Digit One

 
阅读更多

问题描述:

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Hint:

  1. Beware of overflow.

原问题链接:https://leetcode.com/problems/number-of-digit-one/

 

问题分析

解法一:

    这个问题粗看起来有一种很简单直观的解法,就是每次计算一个数字里所包含1的个数。然后遍历所有数字把它们的个数加起来。一个简单的实现如下:

 

public static int countDigitOld(int n) {
        int count = 0;
        for(int i = 1; i <= n; i++) {
            count += count1InInteger(i);
        }
        return count;
   }

   private static int count1InInteger(int n) {
        int count = 0;
        while(n != 0) {
            count += (n % 10 == 1) ? 1: 0;
            n /= 10;
        }
        return count;
   }

    这里就是通过对一个数不停的除以10,然后求它当前最低位是否为1。然后将这些求得的值加起来。再将这个方法应用到1到n的所有数字中。这种方法的整体执行时间比较长,它的时间复杂度为O(NlogN)。所以在实际中如果数字n比较大,它的执行时间还是会比较长的。

 

方法二:

    针对上述的问题,有没有更加高效的解法呢?我们可以尝试从给定一个数字它所在的范围来考虑。对于一个数字来说,如果我们能够统计推导出它在某个位为1的数字个数,再将所有的数字的个数加起来,这样不就是我们要求的结果了么?那么这种方法是否可行呢?我们先根据一个小的示例来推导一下:

 

1位数

假设数字n是1位数的情况:

    这个时候数字n只能取0到9。那么当n >= 1的时候,出现的个数为1,当n < 1的时候,出现的个数为0。

 

2位数

再看数字n是2位数的情况:

    这个时候情况稍微复杂一点。我们针对几种情况来考虑。当n刚好为最小的2位数即10的时候,出现1的数字就两个,1和10。所以总的出现次数为2。

    n为11的时候呢,出现1的数字有1, 10, 11。对于数字11来说,它的个位和十位都出现了1,如果我们按照各位数字出现1的个数来统计,就有1和11两个数字,然后按照10位数字来统计就有10和11。虽然11统计了两次,但是它里面数字1也出现了两次,正好和我们统计的结果是一样的。这里在个数出现的数字1的数字总数是2, 在10位出现数字1的总数是2。因此总的出现次数为4。

    粗看前面这两个数字,似乎也没有什么规律可循,我们再看看数字12。它在个位上出现1的数字有1, 11。而在10位上出现1的数字则有10, 11, 12。10位上出现的数字1的个数为3。这种情况下出现1的总数字数为5。

     这个时候,我们似乎发现一点点规律。对于10位数字上出现1的个数,如果它的十位数正好是1,则它的个数为个位数上的值加1。比如12,它在十位数上出现1的个数为3个,而它的个位数是2。如果这个时候个位数是3的话,它的值可以延伸到13,则在十位数上多一个出来。

    那么对于十位数的数字大于1的情况呢?比如23。它个位数上的数字为1的数字有这些:1, 11, 21 。它十位数上数字为1的数字有: 10, 11, 12, 13, 14, 15, 16, 17, 18, 19。总共有13个。

    针对上述的情况我们可以针对两位数有一个这样的总结,如果个位数的数字大于等于1,则个位数为1的个数为10位数的数字加1。否则就等于10位数的数字。而十位数的数字呢,如果它大于1,则个数为10,如果等于1则为个位数的数字加1。

 

3位数

    现在我们按照前面针对2位数的情况来套一下3位数的示例,看看是否适用。假设有数字100,对于它的个位数出现1的个数来说,按照前面的推断,它是取决于它的高位的数字。当个位数小于1的话,它出现的次数为10位数的数字。在这里如果引申到它的高位数的数字,是否符合条件呢?这里个位数为1的数字有1, 11, 21,31, 41, 51, 61, 71, 81, 91。正好10个数字。和我们的推断符合。如果个位数大于等于1呢?比如101或者102。出现1的数字除了上述的10个,还要101。也符合它的出现个位为高位数加1的情况。

    那么对于十位的数字呢?比如前面的100来说,它出现1的次数为10, 11, 12... 19。正好10个。如果数字小于110,那么它的数字还是取决于它的高位数,也就是10。如果数字大于等于110呢?比如110, 则10位数字的个数为11。而对于111或者112来说呢?它出现的个数还和低位的数字相关。实际上它是相当于低一位的数字2 + 1,再加上它高位的数字1 × 10。那么对于十位数字大于2的3位数情况呢?比如说123。它出现的数字情况为10, 11...19, 然后就是110, 111, ...119。正好20个。恰好为高位数的数字 (1 + 1) × 10。

    因此对于3位数来说,里面十位数包含1的个数可以这么概括,如果十位数的数字为0,则它出现的个数为高位数 × 10。比如101, 201, 301等,它们里面十位数出现1的数目分别为10, 20, 30。如果十位数的数字为1,则它出现的个数为高位数×10 + 低位数 + 1。比如110, 111,它里面十位数出现1的个数分别为11, 12 。如果十位数的数字大于1,则它出现的个数为高位数的数字 + 1再乘以10,比如120, 121,123等,它们里面十位数出现1的个数为20。这是在3位数里针对10位数总结出来的规律。那么对于百位数来说,该是个什么样的情形呢?

    比如说101, 110, 111等数字来说。因为它的百位数是1,如果按照前面的规律来套的话,它的高位数不存在,也可以说就是0,这样它的高位数 = 0,再乘以10,则为0,同时再把它的低位数个数 + 1,我们来看对不对。对于101来说,它在百位数上出现的数字是1的数字有100, 101。对于110来说,它出现这些的有100, 101,... 110,正好11个。那么对于百位数上大于1的数字来说呢?比如200, 210,221, 223等。200以内的百位为1的数字为100, 101...199,实际上有100个。也就是说,对于百位数大于1的数字来说,它应该是它的高位数加1再乘以100。所以,这里我们前面假设的乘以10是针对10位数字的,对于百位数字的应该乘以100。那么对于千位的数字呢?我们应该也可以这么来推导。

 

    我们可以总结出这么一个更加通用一点的规律,对于一个某一位的数字来说,如果它为0,则它这个位置所出现1的个数为它高位数的值乘以当前它所在的进位。比如说它是个位,则高位值乘以1,十位则高位值乘以10。比如说100,它的10位出现1的数字的个数为它高位的1乘以它当前的进位10,所以表示10。同理,求它个位数出现1的个数则为它的高位数10在乘以它当前的进位1,结果也是10。

   如果这个数字为1呢,则它这个位置所出现1的个数为它高位数的值× 当前的进位 + 低位数 + 1 。比如说110里面十位的位置,它的值为10 + 1 = 11。

    而如果这个数字大于2,则它这个位置所出现的1的个数为它高位数的值加1再乘以10,比如说220, 230等,它在十位出现1的数字的个数为30。

    这样,有了这么一大通的分析和推导,我们终于知道怎么来实现这个问题了。首先定义一个factor,来计算在某个进位上它的值,比如说个位它就是1,十位它就是10,百位它就是100...

    然后计算某个数字的高位部分highNum,它相当于n / (factor * 10)。比如当考虑个位数字的时候,需要截取的就是10位及以上的,所以需要除以当前的进位 × 10。

    对于数字的低位部分lowNum呢,它的实现如下lowNum = n - (n / factor) * factor。这样就正好把比当前进位更低位的给取出来了。

    而对于当前位的数字currNum,它的求法则是currNum = (n / factor) % 10 。

    这样,我们再根据currNum的值来判断累加每次的值就得到最终的结果了。于是我们可以得到如下的代码:

 

public class Solution {
    public int countDigitOne(int n) {
        int count = 0;
        long factor = 1;
        long lowerNum = 0;
        long higherNum = 0;
        long currNum = 0;
        while(n / factor != 0) {
            lowerNum = n - (n / factor) * factor;
            currNum = (n / factor) % 10;
            higherNum = n / (factor * 10);
            if(currNum > 1) count += (higherNum + 1) * factor;
            else if(currNum == 1) count += higherNum * factor + lowerNum + 1;
            else count += higherNum * factor;
            factor *= 10;
        }
        return count;
    }
}

     上述算法的时间复杂度为O(ln(N)/ln(10) + 1),速度和前面的比起来确实快多了。

 

总结

   对于求给定一个非负整数所在范围内各个位置出现数字1的解法确实比较有挑战性。如果不是能够有耐心推导出后面这个规律的话,会比较艰难。而且根据这个问题还可以有一些变化,比如求里面出现其他数字的总数以及针对不同数制,比如八进制二进制的情况,这些值得深入分析举一反三。

 

参考材料

编程之美 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics