233. Number of Digit One

https://leetcode.com/problems/number-of-digit-one/

给定一个数字 N,求从 1,2,3,.... , N 所有数字中求1的数目
比如13,从1,2,3,....,13 包含1的数字有 1,10,11, 12, 13,其中11存在2个1,因此总共有6个1

分析:最简单的方法就是逐一遍历每一个数,并对每一个数进判断,这个会非常耗时

  • 我们可以从每一位上来进行计数,比如13,个位有2个1(1, 11),十位有4个1(10, 11, 12, 13),因此总共有 2+4 = 6个1;
  • 而每一位上有多少个1与当前位数字有关,同时还与高位数字以及低位数字有关
    • 比如123,个位上可能出现的1与当前位3有关,同时与高位数字12,以及低位数字0(假设个位后面还存在一位)有关,因此个位出现的1有(1,11,21,31,41,51,61,71,81,91,101,111,121),共13个
    • 十位数字为2,十位上出现的1与当前位2,更高位1,还有低位3有关,因此出现1的有(10,11,12,13,14,15,16,17,18,19,110,111,112,113,114,115,116,117,118,119)
    • 百位数字为1,百位上出现的1与当前为1,高位0,低位23有关,因此出现1的有(100,101,102,103,104,105,...., 123)共24个

总结:

  • 如果当前位为0,那么当前位存在1的情况只能是联合更高位产生,因此1的数目为 更高位 x 当前位的量级
  • 如果当前位为1,那么当前位存在1的情况由两方面产生,一个是联合更高位,另一个是联合低位,从100...到最低为为止,因此1的数目为 更高位 x 当前位的量级 + 低位 + 1(10..)
  • 如果当前位大于1,那么当前位置存在1的情况可以通过当前位联合更高位产生,因此1的数目位 (更高位+1)x 当前位的量级

建议手写操作一下,以便理解

class Solution {
public:
    int countDigitOne(int n) {
        int currnum=0, lowernum=0, highernum=0;
        int cnt = 0;
        int base=1;
        if(n <= 0)
            return 0;
        while(n/base)
        {
            lowernum = n - (n/base) * base;
            currnum = n / base % 10;
            if (base > INT_MAX/10) // base超过整数的表示范围
                highernum=0;
            else
                highernum = n / (base*10);
            

            
            switch(currnum)
            {
                case 0: cnt += (highernum*base);break;
                
                case 1: cnt += (highernum*base + lowernum + 1);break;
                
                default: cnt += (highernum+1)*base;break;
            }
            if (base > INT_MAX/10)// base超过整数的表示范围
                break;
            base *= 10;
        }
        return cnt;
    }
};

结果:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Number of Digit One.
Memory Usage: 6.1 MB, less than 100.00% of C++ online submissions for Number of Digit One.

上一篇:A. Wizard of Orz


下一篇:LeetCode-Python-37. 解数独