老婆在成都，我在广州，为了结束异地，放弃小鹏高级经理职位，降级去成都要少20万，值吗？

那天晚上我正准备下班，Leader一句“这个移除9的题你看下，顺便写个总结”，我人都麻了。脑子里第一反应是：为啥要歧视数字9啊，9招谁惹谁了，斗地主最大不都它么。

先把题意思糊弄清楚哈，大概就是这么个意思： 从 1 开始数数，但是所有带 9 的数都不要，比如 9、19、29、90…统统跳过。然后问你，第 n 个“没有数字9”的数是多少。

举个小例子： 1,2,3,4,5,6,7,8,10,11,12,13… 你看，中间本来该出现 9 的地方，被我们一脚踢掉了，直接从 8 跳到 10。

刚开始我还老老实实写了个“体力活”版本，就是那种最直男的暴力解法，你们肯定也会这么干：一路往上数，遇到带 9 的就跳过，数到第 n 个就停。代码大概长这样：

publicintnthNoNine_brutal(int n){
int count = 0;
int x = 0;
while (count < n) {
        x++;
if (!String.valueOf(x).contains("9")) {
            count++;
        }
    }
return x;
}

这个写法小数据还行，一到 1e9 级别，直接把我本地风扇干到起飞。测一半我都困醒了：这玩意上线不是把服务器干报废？

后来我想起之前踩过的一个坑：凡是那种“把某个数字从世界上抹掉”的题，八成和进制有关。你看我们把所有带 9 的数删掉，剩下的这些数，其实就像一个“没有数字9的十进制系统”，那不就是9进制伪装成10进制吗？

简单说就是：

• 正常世界里，你写 n 的 9 进制表示
• 然后把每一位“当成十进制的某一位”读出来
• 这个读出来的数，就刚好是“移除9世界”里的第 n 个数

随便验一下，不然总感觉像算命：

n = 1：

• 1 的 9 进制 = 1
• 当十进制读 = 1 → 果然是第一个数

n = 8：

• 8 的 9 进制 = 8
• 当十进制读 = 8 → 对，列表里第 8 个是 8

n = 9：

• 9 的 9 进制 = 10
• 当十进制读 = 10 → 刚好跳过了“9”这个带罪之身

再整一个： n = 17

• 17 / 9 = 1…8 → 9 进制是 18
• 当十进制读就是 18 你去前面那串“没9的自然数”里数一数，第 17 个还真是 18，这时候我就放心了：这不是数学，是命。

那这个 9 进制转“假十进制”的代码怎么写？我当时困得眼睛都睁不开了，又不想写什么库函数，心里想：老老实实模拟除9取余就完了。

代码就很朴素，差不多这样：

publicintnthNoNine(int n){
int res = 0;
int base = 1; // 当前是十位、百位、千位这种权重
while (n > 0) {
int digit = n % 9;   // 取 9 进制的一位
        res += digit * base; // 直接塞到“十进制”的某一位上
        base *= 10;          // 往高一位走
        n /= 9;              // 继续处理更高位
    }
return res;
}

你注意一个点啊，这里我 base *= 10，不是 *= 9。因为右边那玩意儿虽然是从 9 进制拆出来的 digit，但我们是按十进制的形式在“拼答案”，一位一位往左挪，所以是乘 10。

还有个小细节，我后来在代码评审的时候被人怼了一句：“你这要是 n 特别大，res 不得炸？用个 long 不香吗？”我一想也对，毕竟谁知道产品哪天脑子一热把 n 搞成 10^12。于是改成这样比较稳一点：

publiclongnthNoNineSafe(long n){
long res = 0;
long base = 1;
while (n > 0) {
long digit = n % 9;
        res += digit * base;
        base *= 10;
        n /= 9;
    }
return res;
}

然后你再想象一下时间复杂度： 暴力那个是 O(答案)，可能要数到天荒地老； 这个是 O(log₉ n)，就是和 n 的位数差不多，怎么跑都很快。

整个过程其实挺魔性的：你肉眼看上去我们是在算“第 n 个没有数字9的数”，实际上程序在背地里做的是“把 n 写成 9 进制再换个壳”。就好比你以为自己在点外卖，其实后台在帮你做消息队列削峰、数据库分库分表那一套，表面上很纯爱，内核全是算发。

最后，我当时把这个题写完提测，一跑全绿，那一刻的感觉就一个字：爽。 本来还想继续优化下，想了想，算了，能过就行，留点 bug 和优化空间给后人，给他们一点参与感。