目前70w,接到深圳110w offer,定居成都,有小孩,划得来去吗?

n = 999999999 这种数据一放出来，老老实实从 1 枚举到 n，再一位一位拆数字，基本就不用跑了。

这题“计数器”我一般按这个意思看：给一个正整数 n，统计从 1 到 n 里面，数字 0 到 9 分别出现了多少次。

比如从 1 到 13：

1 2 3 4 5 6 7 8 9 10 11 12 13

1 出现 6 次，0 出现 1 次，2 出现 2 次，3 出现 2 次。

这种题看着像模拟，其实不能模拟。要按“数位”算。

拿 n = 2593 举例，看十位这一位，也就是 factor = 10。

high = 2593 / 100 = 25cur  = 2593 / 10 % 10 = 9low  = 2593 % 10 = 3

每一位都拆成三段：高位、当前位、低位。

对某个数字 d 来说：

如果当前位 cur 大于 d，那么这一位上 d 的出现次数，可以多吃一整段：

(high + 1) * factor

如果 cur 等于 d：

high * factor + low + 1

如果 cur 小于 d：

high * factor

但数字 0 要单独处理。这个地方最容易错。

因为数字不能有前导 0。比如 0012 这种，在 1 到 n 的自然写法里不存在。 所以算 0 的时候，高位要少算一组。

如果 high == 0，当前位根本不用算 0如果 cur == 0，次数是 (high - 1) * factor + low + 1如果 cur > 0，次数是 (high - 1) * factor + factor

我见过不少代码，1 到 9 都对，只有 0 错。一般就是这里没扣掉前导 0。

Java 代码可以这么写，没必要搞太复杂：

import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;publicclassMain{publicstaticvoidmain(String[] args)throws Exception {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));long n = Long.parseLong(br.readLine().trim());long[] ans = countDigits(n);        StringBuilder out = new StringBuilder();for (int i = 0; i < 10; i++) {if (i > 0) out.append(' ');            out.append(ans[i]);        }        System.out.println(out);    }privatestaticlong[] countDigits(long n) {long[] cnt = newlong[10];if (n <= 0) {return cnt;        }for (long factor = 1; factor <= n; factor *= 10) {long high = n / (factor * 10);long cur = (n / factor) % 10;long low = n % factor;for (int d = 1; d <= 9; d++) {if (cur > d) {                    cnt[d] += (high + 1) * factor;                } elseif (cur == d) {                    cnt[d] += high * factor + low + 1;                } else {                    cnt[d] += high * factor;                }            }if (high == 0) {// 当前已经是最高位了，不能把前导 0 算进去            } elseif (cur == 0) {                cnt[0] += (high - 1) * factor + low + 1;            } else {                cnt[0] += (high - 1) * factor + factor;            }if (factor > Long.MAX_VALUE / 10) {break;            }        }return cnt;    }}

这里我用了 long，不是为了装腔。计数结果可能比 n 大，尤其 n 很大的时候，int 容易炸得很安静。

再看一下 n = 13 的过程。

个位 factor = 1：

1 出现：2 次，分别是 1、112 出现：2 次，分别是 2、123 出现：2 次，分别是 3、134~9 各 1 次0 出现：1 次，来自 10

十位 factor = 10：

1 又出现 4 次：10、11、12、13

最后 1 总共就是 6 次。

这题真正要盯住的不是公式多难，而是两个边界：

一个是 0 不能按普通数字算。 另一个是 factor *= 10 别溢出。

这两个处理干净，剩下就是一位一位扫，复杂度大概是 O(位数 * 10)，n 再大也就跑十来轮。