题目描述（Hard）
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13
输出：6
示例 2：
输入：n = 0
输出：0
提示：
链接：https://leetcode-cn.com/problems/number-of-digit-one
方法一、暴力（超时）
我们考虑使用暴力法来解，只需要枚举每一个比n小的数，然后算他们的含有1的数量，相加即可，代码比较简单：
class Solution {
public int countDigitOne(int n) {
int ans = 0;
for (int i = 1; i <= n; i++) {
int count = 0;
int num = i;
while (num != 0) {
// 从个位数开始一位一位的和1比较
if (num % 10 == 1) {
count++;
}
num /= 10;
}
ans += count;
}
return ans;
}
}
但是，当用例非常大的时候，比如，n=824883294
，会超时，过不了所有用例，放弃！
方法二、动态规划（超内存）
第二种方法，我们考虑使用动态规划来解，比如，要求123
这个数含有的1，其实只要看12
和3
含有的1相加就可以了，用DP方程表示为：dp[i]=dp[i/10]+dp[i%10]
，代码也很简单，如下：
class Solution {
public int countDigitOne(int n) {
int ans = 0;
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i % 10] + dp[i / 10];
ans += dp[i];
}
return ans;
}
}
但是，当用例非常大，比如，n=824883294
，申请n+1
的dp数组，直接把内存干爆了。。
方法三：找规律
经过上面两种血的教训，考虑我们肯定不能一个数一个数的去遍历，去找他们含有1的数量，那么，能不能一批一批地去找呢？
比如，把所有的数一起来考虑，先找他们个位可能出现1的数量，再找十位可能出现1的数量？
我们以n=2021
为例，所有小于等于 2021 的数中个位一共会出现多少个 1 呢？
我们可以很容易地发现，个位数出现1的频率是每10个数出现一次，对不对？
所以，个位数出现多少 1 就取决于，一个有多少个 10，比如 2021 一共用 202 个 10，所以，个位出现 1 的数一共有 202 次（1， 11， 21，2011）+ 1次（2021）。
为什么最后一个 1 次要单独拿出来计算呢？
因为这个 1 次是比较特殊的，如果把 n 换成 2020 ，这样最后的 1 次是没有的，你要仔细考虑一下。
只有 n 的个位数大于等于 1 的时候，才需要计算最后的这个 1 次。
同理，我们考虑十位数一个有多少个 1。
很简单，每 100 个数会出现 10 个十位数为 1 的数字，同样地，如果 n 的后面两位小于 10，则不用额外加次数，如果后两位大于等于 10，则需要额外加次数。
比如，n=2021
时，最后要加 10 次，n=2009
时，最后不要加 10次，而n=2015
时，最后要加 15-10+1=6
次，这一块，你仔细体会一下。
同样地道理，可以推断出千位数出现多少个 1，就很简单了，用公式统一表示为（n 表示题目指定的参数，i 为统计哪位上的1）：
count = (n (i * 10) * i) + ?
，?
处的数量就要看 i 及其右边的位数，即n % (i * 10)
（记为 x），是小于 i 、大于等于 i 了，具体大多少了：
x < i，? = 0i <= x < 2 * i, ? = x - i + 1x >= 2 * i，? = i
写成一行：? = min(max(x - i + 1, 0), i)
，请仔细体会。
完整公式为：count = (n (i * 10) * i) + min(max(n % (i * 10) - i + 1, 0), i)
。
有了公式，我们很快就能计算出来 n = 2021
时，百位数一共会出现 2 * 100 + min(max(21-100+1, 0), 100)=200
个1了，它们分别是100,101,..,199,1100,1101,1199
。
好了，这时候写代码就简单得多了：
class Solution {
public int countDigitOne(int n) {
// 2021
int ans = 0;
for (int i = 1; i <= n; i *= 10) {
ans += (n / (i * 10)) * i + Math.min(Math.max(n % (i * 10) - i + 1,0), i);
}
return ans;
}
}
时间复杂度：O()，跟 n 的位数正相关，这里其实是以10为底的对数，不过复杂度统一使用log。 空间复杂度：O(1)。
运行结果如下：
最后
如果对你有帮助，请点个赞吧，谢谢^^
也可以关注我的公号【彤哥来刷题啦】，每日分享题解，一起刷题，一起拿全家桶。
