LeetCode OJ 之 Number of Digit One （数字1的个数）题目：思路：代码：

121 阅读 0 评论 80 点赞

我是靠谱客的博主无心钢笔，这篇文章主要介绍LeetCode OJ 之 Number of Digit One （数字1的个数）题目：思路：代码：，现在分享给大家，希望可以做个参考。

题目：

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.

思路：

对这个数字的每一位求存在1的数字的个数。从个位开始到最高位。

举个例子54215，比如现在求百位上的1，54215的百位上是2。可以看到xx100到xx199的百位上都是1，这里xx从0到54，即100->199, 1100->1199...54100->54199, 这些数的百位都是1，因此百位上的1总数是55*100

如果n是54125,这时由于它的百位是1，先看xx100到xx199，其中xx是0到53，即54*100, 然后看54100到54125，这是26个。所以百位上的1的总数是54*100 + 26.

如果n是54025，那么只需要看xx100到xx199中百位上的1，这里xx从0到53，总数为54*100

求其他位的1的个数的方法是一样的。

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int countDigitOne(int n) 
    {
        int res=0;
        long left, right, base=1;
        if (n <= 0) 
            return 0;
        while (n >= base) 
        {
            left = n / base;   //left包含当前位
            right = n % base;  //right为当前位的右半边
            
            
            if ((left % 10) > 1)
                res+= (left / 10 + 1) * base;
                
            else if ((left % 10) == 1)
                res+= (left / 10) * base+ (right + 1);
                
            else
                res+= (left / 10) * base;
            base *= 10;
        }
        return res;
	}
	
	
};

可以把上面三个条件合成一步，如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countDigitOne(int n) 
    {
        int res=0;
        long left, right, base=1;
        if (n<=0) 
            return 0;
        while (n>=base) 
        {
            left = n / base;   //left包含当前位
            right = n % base;  //right为当前位的右半边
            
            res += ((left + 8) / 10 * base) + (left % 10 == 1) * (right + 1);
            base *= 10;
        }
        return res;
	}
	
	
};