活久见！外包干三年就自动离职。。。

有时候刷题就像开盲盒，本来以为是一道简单的遍历题，结果一看讨论区，全是高端操作，什么数位 DP、递推、数学归纳法，整得跟高考数学填空题似的，思路比代码多十倍。

这题是这样的：

题目描述：给定一个整数 n，求从 1 到 n 的所有整数中，数字 1 出现的次数。

比如 n = 13，从 1 到 13 包括了 1, 10, 11, 12, 13，你一数，嘿，出现了 6 次1。简单暴力点当然能做，直接全都扫一遍，一个个字符串转成字符数组，然后数一数有几个 '1'，问题不大，就是效率不太行。

我试过直接暴力写，像下面这样：

publicintcountDigitOne(int n) {
intcount=0;
for (inti=1; i <= n; i++) {
intnum= i;
while (num > 0) {
if (num % 10 == 1) {
                count++;
            }
            num /= 10;
        }
    }
return count;
}

这段代码倒也没毛病，思路清晰，写起来也很快，适合面试头脑不清醒的时候救急。但问题是，遇上大一点的 n，比如上亿，就容易超时了。你跑一跑就知道，CPU都快冒烟了。

所以咱得稍微动点脑子，来点数学思维，不然面试官会觉得你只会遍历。

其实这个题的核心思想就是“数位拆分”，也就是说，你把每一位当作“当前位”，然后看看这一位上有多少个1是被其他位组合出来的。

举个例子，假设我们看的是 n = 1234，我们把它拆成高位、当前位、低位的组合来分析：

// 拆分：当前位是 digit，低位是 low，高位是 high
// 位因子 base 表示当前位的权重（个位是1，十位是10，以此类推）

根据当前位 digit 的值，我们可以分情况讨论：

• • 如果当前位为0，那么这一位上能产生1的次数就是 high * base
• • 如果当前位为1，那么就是 high * base + (low + 1)
• • 如果当前位大于1，比如2、3… 那就是 (high + 1) * base

实现起来是这样：

publicintcountDigitOne(int n) {
intcount=0;
intbase=1; // 10^i
inthigh= n / 10, low = 0, digit = n % 10;

while (n / base != 0) {
        digit = (n / base) % 10;
        high = n / (base * 10);
        low = n % base;

if (digit == 0) {
            count += high * base;
        } elseif (digit == 1) {
            count += high * base + (low + 1);
        } else {
            count += (high + 1) * base;
        }
        base *= 10;
    }

return count;
}

第一次写这种题目的时候我都怀疑自己是不是进错赛道了，怎么连数学都得复习一遍。但你得承认，这种题能练脑子，尤其适合早上第一杯咖啡下肚后热热身。

网上还有人拿这种题去套“动态规划”模型，非得搞个 dp[i] 数组，我是真的服了。兄弟，这不就是一个按位分析的数学归纳题吗？DP那是真没必要，越优化越复杂，反而跑得慢了 。

当然啦，如果你是想在面试里耍个酷、炫个技，写个 String.valueOf(i).chars().filter(x -> x == '1').count() 也不是不可以，至少代码精炼，还显得你会用流操作，HR一看：哇！Java 8 用得真香！

不过我觉得吧，这题真正有趣的地方就在于，你以为是简单的字符串处理，结果越扒越深，原来藏着数学原理，最后甚至连“高位、当前位、低位”都出来凑热闹，有点像我早上写个工具类，写着写着又搞成了设计模式复习 。

总之，这题一看是考察“你会不会写循环”，其实是看你“能不能从数字里拆出结构”，写出来代码是否干净、优雅、思路清晰。理解了这套逻辑之后，以后再遇到“从 1 到 n 有多少个 X”这种题，基本就稳了。

最后提一句，像这种题，别想着死记硬背什么模板，要理解它为什么能这么拆，不然换个题一脸懵逼，那就白刷了。