【剑指Offer】从1到n整数中1出现的次数

Posted on | In ,

题目

输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1，10，11和12，1一共出现了5次。

不考虑时间效率的解法，靠它想拿Offer有点难

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int NumberOf1Between1AndN_Solution(int n) {
    int count = 0;

    for (int i = 1; i <= n; i++)
        count += NumberOf1(i);

    return count;
}

private int NumberOf1(int n) {
    int count = 0;

    while (n != 0) {
        if (n % 10 == 1)
            count++;

        n /= 10;
    }

    return count;
}

从数字规律着手明显提高时间效率的解法，能让面试官耳目一新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int NumberOf1Between1AndN_Solution(int n) {
    int count = 0;
    int index = 1;
    int currentN = n;

    while (currentN > 0){
        int current = currentN % 10;
        int high = currentN / 10;
        int low = n - currentN * index;

        count += high * index;

        if (current > 1)
            count += index;
        else if (current == 1)
            count += low + 1;

        index *= 10;
        currentN /= 10;
    }

    return count;
}