共计 2540 个字符，预计需要花费 7 分钟才能阅读完成。
本题主要在于找规律，从一个例子开始，总结出其中的规律。
<!– more –>
原题
输入一个整数 n，求 1～n 这 n 个整数的十进制表示中 1 出现的次数。
例如，输入 12，1～12 这些整数中包含 1 的数字有 1、10、11 和 12，1 一共出现了 5 次。
示例 1：
输入：n = 12
输出：5示例 2：
输入：n = 13
输出：6
```
限制：* 1 <= n < 2^31
原题 url：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
## 解题
### 暴力法
一开始我的想法是计算出从 1 到 n 中，每一个数中包含的 1 个数，累加在一起，求得结果：class Solution {
public int countDigitOne(int n) {if (n < 1) {return 0;}
// 存储从 1 到上一个数的总结果，初始是从 1 到 1 的总结果
int before = 1;
int temp, count;
for (int i = 2; i <= n; i++) {
temp = i;
count = 0;
while (temp != 0) {
// 计算当前数字的个位数是否等于 1
if (temp % 10 == 1) {count++;}
temp /= 10;
}
before += count;
}
return before;
}}
提示我 ` 超出时间限制 `。接下来我想到的是，当给我们一个数 x 时，如果我知道 (x / 10) 对应的 1 的个数，那么再加上最高位 1 的个数，就得出了当前数字对应的 1 的个数。用一个数组，记录每一个数字对应的 1 的个数。由此可以写出代码：class Solution {
public int countDigitOne(int n) {if (n < 1) {return 0;}
// 存储数字原本含有的 1 的数量
int[] countOne = new int[n + 1];
// 存储从 1 到上一个数的总结果，初始是从 1 到 1 的总结果
int before = 0;
int temp, count;
for (int i = 1; i <= n; i++) {countOne[i] = (i % 10 == 1 ? 1 : 0) + countOne[i / 10];
before += countOne[i];
}
return before;
}}
提示我 ` 超出内存限制 `。看来暴力求解不可取，让我们换一种思路。### 找规律
由上面的暴力法，我们可以得知：1. 这道题肯定不能从 1 开始慢慢算出每一个数所对应的 1 的个数，因为这样会超时。2. 也不可以借用 n 个额外空间，因为这样会超出内存限制。那么正确的思路就应该是，给你一个数 n，你直接计算出从 1 到 n 的数中，所有 1 的总个数。假设给你一个数 3210，你会如何求解呢？我们可以把这个数进行拆分：3210 = 3000 + 200 + 10 + 0
= 3 * 1000 + 2 * 100 + 1 * 10 + 0 * 1
似乎没有看出什么规律，那么我们再试着求出每一位，对应的 1 的个数。 从千位 3 开始，针对 1000 ~ 1999 这 1000 个数字，千位上都是 1，因此这里有 1000 个。
百位 2，针对 100 ~ 199 这 100 个数字，百位上都是 1。一共出现了 3 组，分别是 100 ~ 199、1100 ~ 1199、2100 ~ 2199、3100 ~ 3199，一共 (4 * 100 = 400) 个。
十位 1，针对 10 ~ 19 这 10 个数字，十位上都是 1。一共出现了 32 组，但是再加上 3210 本身十位上也是 1，因此一共有 (32 * 10 + 1 = 321) 个。
个位 0，针对 1、11、21、…、101、111、121、…、1001、1011、1021、…、3201，每 10 个数都会出现 1 个，因此一共有 (321 * 1 = 321) 个。
一共 2042 个。
我用力扣本身的测试用例进行了校验，结果是一致的。我们总结一下上面的过程： 我们将数字 n，按照位，从低到高进行遍历。
我们假设当前位的数字为 cur，高位为 high，低位为 low，位数为 digit。比如 3210 这个数，针对百位而言，cur 是 2，high 是 3，low 是 10，digit 是 100。
针对 cur，有 3 种情况：
1、大于 1，那么此位 1 的个数就是：(high + 1) * digit
2、等于 1，那么此位 1 的个数就是：high * digit + low + 1
3、小于 1（也就是等于 0），那么此位 1 的个数就是：high * digit
接下来我们看看代码：class Solution {
public int countDigitOne(int n) {if (n < 1) {return 0;}
// 高位
int temp = n;
// 低位
int low = 0;
// 1 出现的总次数
int total = 0;
// 当前位数，比如个位时为 1，十位时为 10，百位时为 100
int pow = 1;
while (temp != 0) {
// 当前位上的数字
int num = temp % 10;
// 剩下的高位
temp = temp / 10;
// 如果当前位上的数字是 0
if (num == 0) {
// 只加上高位对应
total += temp * pow;
}
// 如果当前位上的数字是 1
else if (num == 1) {// 加上高位对应的数字，和低位的所有，再加 1( 它本身)。// 比如 10，虽然低位是 0，但本身还有 1
total += temp * pow + low + 1;
}
// 如果当前位上的数字大于 1
else {
// 那么高位 +1
total += (temp + 1) * pow;
}
// 低位
low += num * pow;
// 进入下一位
pow = pow * 10;
}
return total;
}}
提交 OK。我们来分析一下复杂度：* 时间复杂度 `O(log N)`：循环内的计算操作使用 O(1) 时间，循环次数为数字 n 的位数，即 log 以 10 为底 n，因此总时间为 `O(log N)`。* 空间复杂度 `O(1)`：只有几个变量使用常数大小的额外空间。## 总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。本题主要在于找规律，从一个例子开始，总结出其中的规律。有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。[https://death00.github.io/](https://death00.github.io/)
公众号：健程之道
