LeetCode: 233. 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.

Example:

1
2
3
Input: 13
Output: 6 
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

挺巧妙的一道hard题。

这题需要我们找所有小于等于n的数字中1的数量。这里的思路是逐位寻找。

对于数字12345来说，我们先找个位，及所有形式为x1的数字都是成立的，其中1234>=x>=0；接着找十位上是1的数字，即所有x1y，其中123>=x>=0，9>=y>=0；接着找百位上是1的数字，即所有x1y，其中12>=x>=0，99>=y>=0；接着找千位上是1的数字，即所有x1y，其中1>=x>=0，999>=y>=0…接着找万位上是1的数字，即所有1y，其中2345>=y>=0…

事实上，我们可以发现规律，对于xpy来说，如果p>1，那么p位上为1的数字为：x*(10*y的位数)+10y的位数；如果p==1，那么p位上为1的数字为：x\(10*y的位数)+y的值+1，y的值+1表示从0到y的数字；如果p为0，那么p位上为1的数字为x*(10*y的位数)。

代码实现

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
30
31
32
33
34
class Solution {
private:
    int countIndexOne(int n, int index) {
        u_long threshold = pow(10, index);
        if (threshold > n) {
            return -1;
        }

        int result = 0;
        result += int(n / pow(10, index+1)) * pow(10, index);

        if (n / threshold % 10 == 1) {
            result += (n % threshold + 1);
        } else if (n / threshold % 10 > 1) {
            result += threshold;
        }

        return result;
    }
public:
    int countDigitOne(int n) {
        if (n < 1)
            return 0;
        int sum = 0, tmp = 0;
        int i = 0;
        while (true) {
            tmp = countIndexOne(n, i++);
            if (tmp == -1)
                break;
            sum += tmp;
        }
        return sum;
    }
};