晋升答辩那天,我准备了20页PPT,把过去一年的成就讲得天花乱坠,结果才发现,晋升名单其实早就在答辩前定好了.答辩只是走个过场

算法题：第K个语法符号

昨天晚上十一点多吧，我在公司楼下抽烟，我们组小李跟我说他刷题刷到一个“第K个语法符号”，看着像个小学生题，结果越写越急，最后还把自己写成了递归地狱……我当时就笑，他说东哥你别笑，你来你也得想一会儿。行，那我就边抽边说，顺手把思路捋一遍。

这个题呢大概是：第一行就一个 0；下一行把上一行每个符号展开，0 变成 01，1 变成 10，然后问你第 N 行第 K 个是 0 还是 1。你别看描述绕，其实它像生产线，上一层是“父节点”，下一层两个“子节点”。我当时脑子里直接冒出来一句：别去生成整行，生成出来你内存直接炸，跟你们线上日志一堆一样，查都查不完。

我先拿烟盒给小李画了个“家谱”关系：第 N 行第 K 个，来自第 N-1 行的第 ceil(K/2) 个。然后关键点是：如果 K 是奇数，它是父节点的“左孩子”，值跟父一样；如果 K 是偶数，它是“右孩子”，值是父的翻转。就这一下，题就活了。

然后小李问：那复杂度呢？我说你递归 N 次，N 最大也就三十来着（一般题都这德行），O(N) 稳稳的，而且根本不需要把字符串拼出来。

我当场用手机备忘录敲了个 Ruby 版本，写得比较“能跑就行”，你们回头可以直接丢到OJ里：

# 第K个语法符号（1-indexed）# 返回 0/1defkth_grammar(n, k)# 第1行只有一个0return0if n == 1  parent = kth_grammar(n - 1, (k + 1) / 2)# k是奇数：左孩子 = parent# k是偶数：右孩子 = 1 - parentif k.odd?    parentelse1 - parentendend# 简单自测（你们别笑，线上我也这么干）if __FILE__ == $0  puts kth_grammar(1, 1) # 0  puts kth_grammar(2, 1) # 0  (01)  puts kth_grammar(2, 2) # 1  puts kth_grammar(4, 5) # 1  (01101001 -> 第5个是1)end

说到这我还岔了一句题外话，小李说“那为啥偶数就翻转？”我说你就把 0->01、1->10 当成规则，父是 0 时子是 0,1；父是 1 时子是 1,0。左边永远等于父，右边永远等于 1-父，这不就完了嘛。别把它想成字符串，想成二叉树，脑子立刻清爽。

然后他又说，有没有更骚的写法。我说有，但你别在面试里装过头哈：其实第 K 个值跟 (K-1) 的二进制里 1 的个数奇偶有关，1 的个数是奇数就输出 1，偶数就输出 0。因为你从根走到那个位置，每遇到一次“走右边”就翻一次，翻的次数就是路径里右转次数，而右转次数刚好等于 (K-1) 的 bitcount。这个你写起来也很短：

defkth_grammar_fast(_n, k)  x = k - 1  cnt = 0while x > 0    x &= (x - 1)   # 每次干掉最低位的1    cnt += 1end  cnt % 2end

不过我一般还是推荐前面那个递归版，解释起来更像“人话”，也不容易被面试官怀疑你背公式。最后我烟抽完了，小李说懂了懂了，结果转身又问我“那要是让我不用递归呢”…哎我说你先把递归写对，别一上来就想着炫技，明天早上九点半还有例会呢，先回去睡觉去。

🔥编程资料合集🔥