0%

整数中1出现的次数（从1到n整数中1出现的次数）

发表于 更新于

求出任意非负整数区间中1出现的次数（从1 到 n 中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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    int power(const int base, const int n)
    {
        int number = 1;
        for (int i = 0; i < n; i++)
        {
            number *= base;
        }
        return number;
    }
    int NumberOf1Between1AndN_Solution(int n)
    {
        if (n <= 0)
        {
            return 0;
        }
        else if (n <= 9)
        {
            return 1;
        }
        else if (n <= 10)
        {
            return 2;
        }
        else
        {
            const string text = to_string(n);
            int base_part = power(10, text.length() - 1);
            int base_part_counter = (text.length() - 1) * power(10, text.length() - 2); // count to e.g 999
            if (text[0] == '1')
            {
                const int left_part = n - base_part; // e.g. 234 for 1234
                return base_part_counter + 1 + left_part + NumberOf1Between1AndN_Solution(left_part);
            }
            else
            {
                const int left_digit = text[0] - '0';
                return base_part_counter * left_digit + base_part + NumberOf1Between1AndN_Solution(n - left_digit * base_part);
            }
        }
    }
};