LeetCode 779. 第K个语法符号

2022-05-29 HGNULB 约 8 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 779. 第K个语法符号

题意分析

构造一张表：第一行只有一个 0；从第二行开始，把上一行的每个符号替换成两个——0 变成 01，1 变成 10。要求返回第 n 行第 k 个符号（行和列都从 $1$ 开始计数）。

生成规则给出的第一条信息是长度的爆炸速度：第 n 行有 $2^{n-1}$ 个符号。题目给的范围是 $1 \le n \le 30$，$1 \le k \le 2^{n-1}$，也就是最后一行可能有 $2^{29}$ 约五亿个符号。这直接判了「把整行构造出来再取第 k 个」的死刑——无论是数组还是字符串，五亿个元素既超内存也超时间。所以必须找到一条只沿着 k 这条路径回溯的计算方式，而不是构造全体。

第二条信息藏在替换规则的结构里：每个符号恰好裂成两个，且左孩子等于父亲、右孩子等于父亲取反。「恰好裂成两个」意味着这是一棵满二叉树，第 n 行第 k 个符号的父亲是第 n-1 行第 $\lceil k/2 \rceil$ 个；「左同右反」意味着从父亲到孩子的变化只有两种：不变或翻转。这两条合起来说明答案只与从根到该位置的路径上翻转了多少次有关，而且只关心次数的奇偶。

第三条信息是符号集只有 $0$ 和 $1$，取反就是异或 $1$，翻转两次等于没翻转——这正是「只需奇偶」的代数基础。

边界上要覆盖：n = 1, k = 1（根节点，答案是 $0$）；k = 1（每一层都走左孩子，从不翻转，答案恒为 $0$）；k 是该行最后一个（每一层都走右孩子，翻转 n-1 次）；n 取到 $30$ 时 k 接近 $2^{29}$（要确认不会溢出 int）。

解法：位计数

核心思路

最直白的暴力是逐行构造字符串，从 "0" 开始做 n-1 次替换，最后取第 k 个字符。第 $30$ 行有 $2^{29}$ 个字符，约 $512$ MB 内存，直接爆掉，且构造耗时也不可接受。

第一层优化是自顶向下变自底向上：既然只要一个位置，就没必要构造整行。第 n 行第 k 个符号的父亲是第 n-1 行第 $\lceil k/2 \rceil$ 个；k 为奇数时它是左孩子（值与父亲相同），k 为偶数时它是右孩子（值是父亲取反）。于是可以递归回溯，n 每次减一、k 每次折半，$O(n)$ 步就能回到根节点 0。这已经完全可行了，是面试里最常见的答案。

但还可以再看穿一层。观察这条回溯路径上真正被用到的信息：每一步只关心「k 是奇数还是偶数」，也就是当前 k 的最低位；而每一步的效果只有「翻转一次」或「不翻转」。因为翻转两次抵消，最终答案就是根值 $0$ 异或上「翻转次数的奇偶」，也就是整条路径上「走了右孩子」的次数的奇偶。

于是问题变成：从根走到第 n 行第 k 个位置，一共向右拐了几次？把 k 减一变成从 $0$ 开始的下标 k-1，那么这个下标的二进制表示（补足到 n-1 位）逐位就是从根往下每一层的左右选择——高位是靠近根的那一层，某一位是 $1$ 就代表那一层走了右孩子。因此「向右拐的次数」恰好等于 k-1 的二进制中 $1$ 的个数。

于是要维护的量只剩一个：令 ones 为 k - 1 在二进制下 $1$ 的个数，答案就是 ones % 2。这条等式就是整道题的全部内容——不变量是「答案 = 根值 $0$ 异或路径翻转次数的奇偶」，而路径翻转次数被证明等于 popcount(k-1)。

特别注意 n 在这个公式里完全没有出现。这不是疏漏：n 的唯一作用是保证 k 落在合法范围内，一旦 k 给定，从根到它的路径就唯一确定了，与总层数无关。换句话说，同一个 k 在第 $5$ 行和第 $30$ 行给出的符号是相同的——因为深层的那个位置只是在浅层位置下面又接了一串左孩子，而左孩子不改变值。理解这一点，才算真正看穿了这道题。

解题步骤

把 k 转成从 $0$ 开始的下标 k - 1。理由：题目下标从 $1$ 开始，而「二进制位对应左右选择」这个映射要求下标从 $0$ 起算；不减一的话，第一行第一个位置对应的是 1（二进制有一个 $1$），会得出答案 $1$，与真实的 $0$ 相反。

统计 k - 1 的二进制中 $1$ 的个数，Java 用 Integer.bitCount，Go 用 bits.OnesCount。理由：这个计数就是从根到目标位置「向右拐」的总次数，每一次向右拐意味着值相对父亲翻转一次。

返回 ones % 2。理由：根值是 $0$，翻转偶数次仍是 $0$，奇数次变成 $1$；ones % 2 正好把这两种情况映射成 $0$ 和 $1$，不需要额外的异或或条件判断。

参数 n 不参与计算，可以直接忽略。理由：如上所述，n 只约束 k 的合法上界；题目保证 $k \le 2^{n-1}$，所以不需要任何校验。

以 n = 4、k = 5 走一遍。先算 k - 1 = 4，二进制是 100，$1$ 的个数是 $1$，答案 $1 \bmod 2 = 1$。验证一下真实的表：第一行 0；第二行 01；第三行 0110；第四行 01101001。第四行第 $5$ 个字符确实是 1，吻合。再用路径的角度复核：k - 1 = 4 补足到 $3$ 位是 100，从根往下依次是「右、左、左」——第一步向右翻转一次得到 $1$，之后两步都向左保持不变，最终是 $1$，与公式一致。

再走一个对照用例 n = 4、k = 4：k - 1 = 3，二进制 011，$1$ 的个数是 $2$，答案 $0$。查表第四行第 $4$ 个字符是 0，正确；路径是「左、右、右」，翻转两次抵消回 $0$，也吻合。这两个例子放在一起，正好说明「只看翻转次数的奇偶，不看具体在哪一层翻转」。

代码实现

class Solution {
    public int kthGrammar(int n, int k) {
        int ones = Integer.bitCount(k - 1);
        return ones % 2;
    }
}

func kthGrammar(n int, k int) int {
    ones := bits.OnesCount(uint(k - 1))
    return int(ones % 2)
}

复杂度分析

时间复杂度：$O(1)$。Integer.bitCount 与 bits.OnesCount 都是常数时间的位运算（在主流 JVM 与 Go 编译器上会被优化成单条 POPCNT 指令，即使退化成分治式的位并行算法也是固定的 $5$ 步）；若手写循环逐位统计则是 $O(\log k) = O(n)$，本题 $n \le 30$，同样可视为常数。

空间复杂度：$O(1)$。只用了一个整型变量存放位计数结果，既不构造任何一行，也不使用递归栈——这正是相对「逐行构造」和「递归回溯」两种解法的核心优势。

关键点总结

看到「每个元素分裂成固定个数的子元素」的生成规则，要立刻把它识别成一棵满 K 叉树，并意识到「求第 n 层第 k 个」等价于「沿着一条根到叶的路径走一遍」，而不是构造整层。这一步就把指数级的规模降到了线性。

当每一步的变换只有「作用」与「不作用」两种，且作用两次等于不作用（对合变换）时，最终结果只取决于作用次数的奇偶。异或、翻转、取反、旋转 $180$ 度都属于这一类，识别出来就能把路径累积压缩成一个奇偶位。

「层数 + 位置」到「位置的二进制表示」的映射是满二叉树问题的通用工具：把下标转成从 $0$ 开始后，其二进制位从高到低就是从根到该节点的左右选择序列。堆的下标运算、线段树的路径定位、格雷编码都建立在同一个映射上。

参数在最终公式里消失往往不是错误，而是问题结构的体现。本题 n 不出现，是因为在已有位置下方接一串左孩子不改变值；能主动解释清楚「为什么 n 无关」，比背下公式更有说服力。

面试视角：字节和阿里考这题的期望路径是分三级递进——先说「逐行构造会爆内存」，再给出 $O(n)$ 的递归回溯（k 奇偶决定是否取反父亲），最后指出「只关心翻转次数的奇偶，所以等于 popcount(k-1) 的奇偶」得到 $O(1)$ 解。三级都说到，就是满分答案。如果面试官不允许用 Integer.bitCount，随手用 while (x != 0) { ones ^= (x & 1); x >>= 1; } 手写即可，只要能说清原理，用不用内建函数不影响结论。

易错点总结

错误写法：直接对 k 做位计数而不减一，写成 Integer.bitCount(k) % 2 → 用例 n = 1, k = 1 → bitCount(1) = 1，返回 $1$，而第一行第一个符号是 $0$，答案完全相反。

错误写法：逐行构造字符串或数组再取第 k 个 → 用例 n = 30, k = 1 → 第 $30$ 行有 $2^{29}$ 个字符，约 $512$ MB，直接内存溢出，即便不溢出也会超时。

错误写法：递归回溯时把「奇偶」判反，写成 k % 2 == 0 时值与父亲相同 → 用例 n = 2, k = 2 → 认为第二个符号等于父亲 $0$，返回 $0$，而第二行是 01，第 $2$ 个是 $1$。

错误写法：递归回溯时父亲下标写成 k / 2 而不是 (k + 1) / 2 → 用例 n = 2, k = 1 → 1 / 2 = 0，下标变成非法的 $0$，递归时越界或死循环；正确的父亲下标是向上取整。

错误写法：认为答案与 n 有关，写成 (bitCount(k - 1) + n) % 2 之类的形式 → 用例 n = 2, k = 1 → 得到 $(0 + 2) \bmod 2 = 0$ 恰好正确，但 n = 3, k = 1 得到 $1$，而第三行第一个符号仍是 $0$，错误。

错误写法：用 long 或 Integer.bitCount((int)(k - 1)) 时先把 k 提升成 long 再强转回 int 但漏掉高位 → 用例 n = 30, k = 2^29 → k - 1 是 $536870911$，仍在 int 范围内，本题其实不需要 long；反而是无谓加宽后转换不当会截断出错。

错误写法：Go 里写 bits.OnesCount(uint(k)) 忘记减一 → 用例 n = 4, k = 4 → OnesCount(4) = 1，返回 $1$，而第四行第 $4$ 个是 $0$。

错误写法：Go 里用 bits.OnesCount8 或 OnesCount16 这类窄位宽版本 → 用例 n = 30, k = 2^29 → k - 1 超出 $8$ 位或 $16$ 位，强转时高位被截断，位计数偏小，奇偶判断随机出错。

错误写法：把生成规则记反，以为 0 变成 10、1 变成 01 → 用例 n = 2, k = 1 → 认为第二行是 10，返回 $1$，正确答案是 $0$；规则是左孩子与父亲相同。

错误写法：手写位计数时用 x >> 1 处理可能为负的输入 → 用例若因为下标计算失误使 k - 1 变成负数 → Java 的 >> 是算术右移，符号位不断补 $1$，循环永不终止；应使用 >>> 或先保证非负。

相似题目

题目	难度	考察点
191. 位1的个数	简单	单独练习 popcount 的手写实现，是本题公式落地时唯一需要的原语
338. 比特位计数	简单	用递推批量求出所有数的 popcount，考察 `i` 与 `i >> 1` 之间的状态转移
89. 格雷编码	中等	同样把「下标的二进制」映射成构造过程，但要求相邻项恰好差一位
119. 杨辉三角 II	简单	同为「只要某一行的某个位置」，可用组合数直接算而不必构造前面所有行
面试题 08.06. 汉诺塔问题	简单	递归结构同样是每层二分，练习把递归定义直接翻译成代码而不展开全部状态