拼多多员工中696万彩票辞职，曾经的工位成了新打卡地！

刚看到个拼多多的贴子，说有个哥们中了696万，当天就提离职走人了，现在已经有同事开始去他“曾经”的工位打卡拍照，挺魔幻的画风。

网友们的回复我看了看，有人说“我中了我也立刻走”，有人算账说“税后也就那样，还是得上班”，还有人感慨“说明以前过得确实挺苦”。怎么说呢，我觉得这事最真实的一点是：普通打工人对“说走就走”的自由，是真的馋。

但话说回来，696万听着多，摊到一线城市房贷、父母养老、孩子教育上，其实就是一份“底气”，不是无限续杯。真到自己身上，未必能像他这么潇洒提桶，更多人可能会先悄悄还债、存钱，再谋下一步。

至于去工位打卡这事，我反而挺能理解，当个许愿池，给自己打个气也没啥。但别把好运当规划。

面 试 题 ：旋转数字

最近刷题的时候，又看到一个名字挺唬人的题——「旋转数字」。刚看到还以为是矩阵旋转，结果一看：啊？只是让你数数字而已，不过细节还挺有意思的。

大概意思是这样：

给你一个正整数 N ，问从 1 到 N 之间，有多少个数满足下面两个条件：

1. 把这个数“旋转 180 度”以后，还是一个合法的数字

2. 并且旋转前后，这个数变成了 不一样的数

所谓“旋转 180 度”，其实就是按位看每个数字：

• 0、1、8：转完还是自己

• 2 和 5：互相变

• 6 和 9：互相变

• 3、4、7：转完就不是数字了，直接非法

比如：

• 12 → 旋转后变成 51，合法而且变化了，这是好数字

• 11 → 旋转后还是 11，没变，不算

• 37 → 里面有 7，转完就废了，直接非法

我们要做的，就是统计有多少个“好数字”。

如果不考虑性能，最直接的思路其实很简单：

对 1 ~ N 的每个数 x ：

1. 按位检查每一位是不是在合法集合 {0,1,2,5,6,8,9} 里

2. 至少要出现一位在“会变”的集合 {2,5,6,9} 里

3. 两个条件都满足，就计数 +1

用 Java 写一个“检查一个数是否是好数字”的函数，然后暴力从 1 数到 N 就完事。

这种写法在面试里也能过，但如果 N 比较大，检查每个数都拆位、转字符串，性能会稍微差一点。

稍微聪明一点：用 DP 复用前缀结果

这道题有个很好利用的结构： 一个数 x ，可以拆成“前面几位”和“最后一位”。

比如 x = 123 ：

• 前缀： 12

• 最后一位： 3

如果我们知道前缀 12 的合法性，再加上最后一位 3 的合法性，就能推导出 123 是不是好数字。

所以可以搞两个数组：

• valid[i] ：数字 i 是否 完全合法 （没有 3、4、7 这些非法的）

• diff[i] ：数字 i 是否 至少包含一位会变化的数字 （2、5、6、9）

状态转移就很自然了：

• 把 i 拆成 a = i / 10 （前缀）， b = i % 10 （最后一位）

• 如果前缀 a 已经非法了，那 i 也必定非法

• 否则看最后一位 b ：

• • valid[i] = false

  • diff[i] = false （整个数直接报废）

  • valid[i] = true

  • diff[i] = true （因为当前这一位就会变）

  • valid[i] = true

  • diff[i] = diff[a] （有没有“会变”的数字，完全取决于前缀）

  • 如果 b 是 0、1、8：

  • 如果 b 是 2、5、6、9：

  • 如果 b 是 3、4、7：

最后再扫一遍 1 ~ N ，统计那些满足：

• valid[i] == true

• diff[i] == true

的数字个数，就是答案。

时间复杂度是 O(N) ，每个数只做 O(1) 的运算，比每次转字符串舒服很多。

按照上面的思路，直接上代码：

publicclassRotatedDigits{

 // 主函数：返回 1..n 里有多少个“好数字”
publicintrotatedDigits(int n){
// valid[i] 表示 i 这个数是否合法（不包含 3、4、7）
boolean valid = newboolean[n + 1];
// diff[i] 表示 i 是否至少包含一位会变化的数字（2、5、6、9）
boolean diff = newboolean[n + 1];

 // 0 本身是合法的（虽然不会参与统计，但方便做前缀）
valid[0] = true;
diff[0] = false;

 for (int i = 1; i <= n; i++) {
int a = i / 10; // 前缀
int b = i % 10; // 最后一位

 // 如果前缀已经非法了，后面没必要看，直接标记非法
if (!valid[a]) {
valid[i] = false;
diff[i] = false;
continue;
}

 if (b == 0 || b == 1 || b == 8) {
// 这一位旋转后不变
valid[i] = true;
// 是否“变过”，继承前缀的结果
diff[i] = diff[a];
} elseif (b == 2 || b == 5 || b == 6 || b == 9) {
// 这一位旋转后会变成别的数
valid[i] = true;
diff[i] = true;
} else {
// 3、4、7 直接非法
valid[i] = false;
diff[i] = false;
}
}

 int ans = 0;
for (int i = 1; i <= n; i++) {
if (valid[i] && diff[i]) {
ans++;
}
}
return ans;
}

 // 简单测一下
publicstaticvoidmain(String[] args){
RotatedDigits rd = new RotatedDigits;
System.out.println(rd.rotatedDigits(10)); // 输出 4 ：2,5,6,9
System.out.println(rd.rotatedDigits(20)); // 可以自己算着对一下
}
}

这个写法的几个点你可以注意一下：

• 用数组把“前缀的信息”保存下来，后面的数字直接复用

• 没有用字符串，都是整数除法+取模，效率还不错

• valid 和 diff 分开，更好理解逻辑：

• • 一个是“是不是合法数字”

  • 一个是“有没有发生变化”

这题其实就是典型的“按位拆解 + 状态复用”的套路，看上去是在玩数字，其实是在练 DP 的味道。 先写出暴力，再顺着“前缀”的思路把状态拆出来，你会发现很多数位题都是一个套路。