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.