LeetCode 779. 第K个语法符号

约 3 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 阿里
标签
数学 位运算 递归

题目描述

✅ 779. 第K个语法符号

image-20260928224754943

image-20260928224754946

题意分析

第一行只有 0，之后每个 0 生成 01，每个 1 生成 10。行号和位置都从 1 开始，要求第 n 行第 k 个符号。

每生成一行长度都会翻倍，第 n 行有 $2^{n-1}$ 个字符。只查询一个位置时，无需构造整行，只需确定它在生成过程中的祖先路径，以及这条路径如何改变最初的 0。

解法：位计数

核心思路

[!blue]

把生成过程看成一棵二叉树：一个符号生成的第一个字符是左孩子，第二个字符是右孩子。由 0 -> 01 和 1 -> 10 可知，左孩子始终等于父值，右孩子始终是父值的翻转。因此叶子最终为多少，只取决于从根到它走了多少次右分支。

先把位置变成零基下标 q = k - 1。父节点下标为 p 时，它的两个孩子下标分别是 2 * p 和 2 * p + 1，所以孩子下标的最低位为 0 表示左分支，为 1 表示右分支；去掉最低位，就回到了父节点下标。不断向上重复，恰好读取完 q 的二进制位，每个 1 对应路径上的一次右分支。

根节点是 0，翻转两次会恢复原值，所以右分支次数为偶数时结果为 0，奇数时为 1。直接统计 k - 1 的置位数并对 2 取模，就得到答案，不必真的执行逐层递归。

从根向下看，这条路径使用 n - 1 位，不足的高位补零。增加合法行数只会在同一位置的路径前增加左分支，不改变翻转次数，所以公式不需要使用 n；n 的作用是保证给出的 k 在这一行中存在。

解题步骤

  • 位置先减一。
  • 统计二进制一的数量。
  • 返回奇偶。

k == 1 时，零基下标为零，整条路径都是左分支，结果始终为零；这也覆盖第一行。题目限制 n <= 30，k - 1 能放进当前整数类型，Java 的 bitCount 与 Go 的 OnesCount 都能完整统计所需位数。

代码实现

class Solution {
    public int kthGrammar(int n, int k) {
        // 零基位置中的一，表示从根到该位置的右分支次数
        int ones = Integer.bitCount(k - 1);

        return ones % 2;
    }
}

import "math/bits"

func kthGrammar(n int, k int) int {
    // 零基位置中的一，表示从根到该位置的右分支次数
    ones := bits.OnesCount(uint(k - 1))
    return int(ones % 2)
}

复杂度分析

  • 时间复杂度：固定整数位宽下 $O(1)$。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • n 保证位置合法，公式无需构造对应层。
  • 路径编码采用零基位置。

易错点总结

[!yellow]

  • 直接统计 k，会把第一行首个符号算成一。
  • 把层数也加进奇偶，会错误改变同一位置在更深行的结果。
  • 只使用较窄位宽，会丢掉高位翻转信息。

相似题目

题目 难度 关联与区别
191. 位1的个数 简单 第k项可由k-1二进制置位数的奇偶性确定，位计数替代指数长度的展开。
1545. 找出第 N 个二进制字符串中的第 K 位 中等 同样查询递归生成串的单个位置，原题还包含反转与取反，需要按递归结构映射位置。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/49967314
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！