『LeetCode』779 第K个语法符号

题目

779. 第K个语法符号

我们构建了一个包含 n 行( 索引从 1 开始)的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。

给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

示例 1:

输入: n = 1, k = 1
输出: 0
解释: 第一行：0

示例 2:

输入: n = 2, k = 1
输出: 0
解释:第一行: 0第二行: 01

示例 3:

输入: n = 2, k = 2
输出: 1
解释:
第一行: 0
第二行: 01

提示:

\(1 <= n <= 30\)
\(1 <= k <= 2^{n - 1}\)

题解

【第K个语法符号】二叉树搜索与数学推导

数学

一个简单的想法其实是按照题目模拟，但 \(2^{30}\) 的数据范围肯定是 TLE 的，如果没有，那就是数据太弱了。

但实际上我们仔细观察并不需要完全模拟，只需找到第 k 个数字的具体值就好了，怎么找呢？简单画个四层的图，我们先找规律：

看到这个图，相信不难想到一定，从上向下模拟，如果我们每次都知道向左还是向右，那么就不需要完全模拟了，每层只需 \(O(1)\) 就能进入下一层，而我们完全可以根据 \(k\) 的值得到具体进入下一层是向左还是向右。这里我最先想到的是一个假设，向左还是向右可以看 \(k\) 的二进制位，这是很自然的想法，因为每次进入下一层，结点数量就会加倍，也就是左移一位，对于 \(k\) 的索引我们不按题目中说的以 1 为起点，而是用惯用的以 0 为起点。

给定一个数 \(k\) ，在第 \(n\) 层，我们有 \(2^{n - 1}\) 个结点
第一层的左右子树分别有 \(2^{n - 2}\) 个叶子结点，如果 \(k < 2^{n - 2}\) 那么我们就应该向左进入第二层，否则就应该向右进入第二层。
同理在第二层，左右子树分别有 \(2^{n - 3}\) 个叶子结点，如果 \(k < 2^{n - 3}\) 那么我们就应该向左进入第三层，否则就应该向右进入第三层。
...
以此类推
事实上我们有个简单的办法判断向左还是向右，即检测第一层检测 \(k\) 的第 \(n - 1\) 位，若是 \(0\) 则进入左子树，否则进入右子树，而第二层检测第 \(n - 2\) 位，以此类推，这个只要大家将 \(k\) 写成二进制形式就不难看出原因

有了以上推断，代码其实就很简单了

更进一步，写代码的判断时，我们可能会发现向左值不变，向右值改变，换而言之，\(k\) 的二进制中的 0 不影响结果，而每个 1 会使结果改变一次，所以实际上统计 \(k\) 的二进制中的 1 即可，常规方法还是 \(O(n)\) 的，而使用分治可以优化到 \(O(\log n)\), 这里就不赘述了，大家可以自行研究

# Code language: Python
class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        pre, p, q = 0, k - 1, n - 1
        while q >= 0:
            if pre == 0:
                pre = 1 if (p & (1 << q)) else 0
            else:
                pre = 0 if (p & (1 << q)) else 1
            q -= 1
        return pre

// Code language: Java
class Solution {
    public int kthGrammar(int n, int k) {
        int pre = 0;
        for (int p = k - 1, q = n - 1; q >= 0; --q) {
            if (pre == 0) pre = (p & (1 << q)) > 0 ? 1 : 0;
            else pre = (p & (1 << q)) > 0 ? 0 : 1;
        }
        return pre;
    }
}

// Code language: C++
class Solution {
public:
    int kthGrammar(int n, int k) {
        int pre = 0;
        for (int p = k - 1, q = n - 1; q >= 0; --q) {
            if (pre == 0) pre = (p & (1 << q)) > 0 ? 1 : 0;
            else pre = (p & (1 << q)) > 0 ? 0 : 1;
        }
        return pre;
    }
};

/* Code language: JavaScript */
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kthGrammar = function(n, k) {
    let pre = 0;
    for (let p = k - 1, q = n - 1; q >= 0; --q) {
        if (pre == 0) pre = (p & (1 << q)) > 0 ? 1 : 0;
        else pre = (p & (1 << q)) > 0 ? 0 : 1;
    }
    return pre;
};

/* Code language: Go */
func kthGrammar(n int, k int) (pre int) {
    for p, q := k - 1, n - 1; q >= 0; q-- {
        if pre == 0 && (p & (1 << q)) > 0 {
            pre = 1
        } else if pre == 1 && (p & (1 << q)) > 0 {
            pre = 0
        }
    }
    return
}

时间复杂度: \(O(n)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』779 第K个语法符号

题目

标签

题解

数学