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

描述

输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数
例如， 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次

注意：11 这种情况算两次

数据范围： 1≤n≤30000
进阶：空间复杂度 O(1) \O(1) ，时间复杂度 O(lognn) \O(lognn)

示例1
输入：13
返回值：6

示例2
输入：0
返回值：0

解题思路

假设我们要计算百位上总共有多少1：首先100-199有100个1，而1100-1199又出现了100个1，于是我们知道了每过1000个数字就会出现100个百位上的1，于是我们就有
$$(int)n/1000\ast 100$$
细分讨论一下就是：

当n%1000<100 百位上不会出现1；
当100 <= n%1000 <200，百位上出现的1有 n%1000−100+1 次
当n%1000>=200，百位上的1一共100次
于是我们就可以得到计算公式每一位的计算公式：
$$n/10^{i+i}\ast 10^i+min(max(n\%10^{i+1}-10^i+1,0),10^i)$$
i就表示n的某一位，而前半部分是表示完整在循环中的，后半部分表示部分出现需要讨论的。

代码

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        if (n < 1) {
            return 0;
        }
        int base = 1;
        int res = 0;
        while ( base <= n) {
            res += n/(base*10)*base + min(max(n%(base*10) - base + 1, 0), base);
            base = base*10;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15