小鲸鱼的梦境
0%

『LeetCode』779 第K个语法符号

发表于 分类于 Valine：
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目

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 <  = 2n − 1

标签

位运算, 递归, 数学

题解

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

数学

一个简单的想法其实是按照题目模拟，但 230 的数据范围肯定是 TLE 的，如果没有，那就是数据太弱了。

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

tree

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
# 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
1
2
3
4
5
6
7
8
9
10
11
// 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
// 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 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;
};
1
2
3
4
5
6
7
8
9
10
11
/* 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 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~