LeetCode_位运算_递归_中等_779.第K个语法符号

1.题目

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/k-th-symbol-in-grammar

2.思路

（1）递归
本题比较容易想到的使用递归来解决，但是下面的递归代码在 LeetCode 中提交时会出现“超出内存限制”的提示！

（2）递归 & 位运算
思路参考本题官方题解

具体分析过程可见官方题解，这里对 num₁ = (x & 1) ^ 1 ^ nums₂ 进行以下说明，首先看下面的表：

第 i + 1 行中的第 x (1 ≤ x ≤ 2ⁱ) 个数字 num₁ 会被第 i 行中第 ⌊(x+1) / 2⌋ 个数字 num₂ 生成，即 num₁ 同时由 num₂ 和 x 决定：
① num₁ 的取值为 0 或 1；
② 由官方题解的分析可知，x 的奇偶性来代替 x，其取值为 0 或 1，其中，0 表示 x 为偶数，1 表示 x 为奇数；
所以上面的表正好可以表示 num₁、num₂ 和 x 这三者之间的关系，当然要推导出 num₁ = (x & 1) ^ 1 ^ nums₂ 还得额外加一列：

此时再结合多个 0、1 之间的异或运算性质可知，此时的 num₁ 就表示前面三列数字中 1 的个数情况：
① 如果有偶数个 1，则 num₁ = 0；
② 如果有奇数个 1，则 num₁ = 1；
此外，再用 x mod 2 替换 x & 1 即可。

3.代码实现（Java）

//思路1————递归
class Solution {
    public int kthGrammar(int n, int k) {
        return getNthSymbols(n).charAt(k - 1) - 48;
    }
	
	//获取第 n 行的所有字符
    public String getNthSymbols(int n) {
        if (n == 1) {
            return "0";
        } else {
            return replaceSymbol(getNthSymbols(n - 1));
        }
    }
	
	//将字符串 s 中的 "0" 替换为 "01"、"1" 替换为 "10"
    public String replaceSymbol(String s) {
        StringBuilder builder = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == '0') {
                builder.append("01");
            } else {
                builder.append("10");
            }
        }
        return builder.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

//思路2————递归 & 位运算
class Solution {
    public int kthGrammar(int n, int k) {
        if (n == 1) {
            return 0;
        } else {
            return (k & 1) ^ 1 ^ kthGrammar(n - 1, (k + 1) / 2);
        }
    }
}
1
2
3
4
5
6
7
8
9
10