跟着姚桑学算法-从1到n整数中1出现的次数

题. 从1到n整数中1出现的次数

输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。

例如输入 12，从 1 到 12 这些整数中包含 “1” 的数字有 1，10，11 和 12，其中 “1” 一共出现了 5 次。

数据范围
1≤n≤10^9

样例

输入： 12
输出： 5

【题解】-- 按位数

一个数字： abcdef
求解 1 出现的次数即为各个位为1时其次数总和。(分别讨论各个位为 1 时，这个数字的变化范围，也就得到了总个数)

• 讨论 f 位，则其高位的范围可以为 0 ~ abcde-1，低位只能为 1

f = 0 时，1, 11, 21, …, abcd(e-1)1。共计 abcde 个 1
f = 1 时，abcde1 也符合，共计 abcde + 1
f > 1 时，其高位范围可以为 0 ~ abcde

• 讨论 e 位，则其高位范围可以为 0 ~ abcd-1, 低位可以为 0 ~ 9

e = 0, 10, 110, 210, …, abc(d-1)10。共计 abcd 个 0 ~ 9
e = 1, abcd1f 也符合，共计 abcd 个 0 ~ 9 + 1 个 0 ~ f
e > 1, 则其高位可以为 0 ~ abcd
… 以此类推

复杂度分析：

一个n位数一共有ln(n) / ln(10)位, 所以复杂度是 O(logn)级。

C++代码实现：

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {

        int res = 0;
        for (int m = 1; m <= n; m *= 10) {
            int left = n / (10 * m);
            int right = n % m;
            res += left * m;
            if ((n / m) % 10 == 1) res += right + 1;
            if ((n / m) % 10 > 1) res += m;
            //cout << left << " " << right << " " << res << endl;
        } 
        return res;
    }
};