提的Bug被同事说“不是问题”，结果线上崩了，怎么办?

算法题：数字 1 的个数

“数字 1 的个数”这题，说简单吧，确实也简单，暴力一点从 1 数到 n，一个个数有几个 1 就累加上去。但这思路吧，太原始，面试的时候这么写，估计凉得飞快。咱们还是得用点“正经”的算法思路，展现点“人上人”的气质💼。

题目本身是让你统计从 1 到 n 的所有数字中，数字 1 出现的次数。比如 n=13，你得遍历 1~13，像 1、10、11、12、13 这些都包含 1，最终答案是 6。

暴力解法就不多说了，真就写个循环 + 字符串转化，然后 indexOf 去数 '1'。这个写法虽然能过小数据，但一上来要你搞个 n = 10^9，你不超时谁超时？

那怎么高效做？讲真，核心思路是“按位分析”。我当时刷这题的时候，想到了一种很巧的做法，就是把每一位上 1 出现的可能都加起来。

假设我们现在是分析个位、十位、百位...的 1 出现次数，定义几个变量：

publicintcountDigitOne(int n){
int res = 0;
long digit = 1; // 当前位：个位、十位、百位...
long high = n / 10, cur = n % 10, low = 0;

while (high != 0 || cur != 0) {
if (cur == 0) {
            res += high * digit;
        } elseif (cur == 1) {
            res += high * digit + low + 1;
        } else {
            res += (high + 1) * digit;
        }

// 下一轮
        low += cur * digit;
        cur = high % 10;
        high /= 10;
        digit *= 10;
    }

return res;
}

咋理解？我们按位来看，比如你要算 1~21345 里 1 出现的次数。

• 分析个位的时候：看的是从 02134 有多少个十位是 19，对应当前位是几种情况。
• 十位的时候：看的是从 0~213 有多少个百位的组合。
• 每一位都可以拆成高位、当前位、低位三个部分，根据当前位的不同（0、1、>1），统计方式不一样。

你别说，这玩意儿初看还挺抽象，但真写代码实现起来，逻辑是非常顺畅的，性能也超级好，时间复杂度 O(log n)，空间复杂度 O(1)，优雅得一批😎。

我记得当时面阿里实习的时候，有个大哥直接让我手写这个题，写完之后他来了一句：“能写对这个的，基础还可以。”我心里默默地吐槽：这也算基础题？你要是把它塞 Leetcode 里的 Hard，我也信啊！

当然，说到这里，哥们儿还真想吐槽一下：现在很多面试题为了刷出候选人的“极限操作”，常常喜欢拿这种技巧型题目当门槛题，但实际上这种题你在线上系统里能用上几次？更多的时候我们写业务逻辑，看的是稳定、可维护，而不是谁能三秒想到数学公式。

不过呢，刷这种题也确实锻炼思维，尤其是像这种“位运算+数学推理”的组合拳，有时候能给你打开一些思路上的死结。你哪天碰到个奇葩业务需求，比如要查某个 ID 范围里某个数字出现次数，就能秒出解法了。

总之，兄弟们，这题别用暴力法去糊弄自己，能手写出这种算法，才是真的“入了门”。下次再遇到“数字 2 的个数”“某数字的个数”这类变种，思路照搬就完事儿了✨。