【2022-10-20每日一题】779. 第K个语法符号[Medium]

2022-10-20每日一题：779. 第K个语法符号

难度：Medium

标签：位运算 、 递归 、 数学

我们构建了一个包含 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

方法一：递归

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

func kthGrammar(n, k int) int {
    if n == 1 {
        return 0
    }
    return k&1 ^ 1 ^ kthGrammar(n-1, (k+1)/2)
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为题目给定表的行数。
• 空间复杂度：O(n)，其中 n 为题目给定表的行数，主要为递归的空间开销。

方法二：找规律 + 递归

func kthGrammar(n, k int) int {
    if k == 1 {
        return 0
    }
    if k > 1<<(n-2) {
        return 1 ^ kthGrammar(n-1, k-1<<(n-2))
    }
    return kthGrammar(n-1, k)
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为题目给定表的行数。
• 空间复杂度：O(n)，其中 n 为题目给定表的行数，主要为递归的空间开销。

方法三：找规律 + 位运算

func kthGrammar(n, k int) (ans int) {
    // return bits.OnesCount(uint(k-1)) & 1
    for k--; k > 0; k &= k - 1 {
        ans ^= 1
    }
    return
}

复杂度分析

• 时间复杂度：O(logk)，其中 k 为题目给定查询的下标。
• 空间复杂度：O(1)，仅使用常量变量。

LeetCode题库地址

• https://leetcode.cn/problems/k-th-symbol-in-grammar