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

╰+哭是因爲堅強的太久メ 2023-10-07 20:30 5阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

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

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

## 2.思路 ##

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

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

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

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

此时再结合多个 0、1 之间的异或运算性质可知，**此时的 num1 就表示前面三列数字中 1 的个数情况**：  
① 如果有偶数个 1，则 num1 = 0；  
② 如果有奇数个 1，则 num1 = 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();
        }
    }

//思路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);
            }
        }
    }

[Link 1]: https://leetcode.cn/problems/k-th-symbol-in-grammar/solution/di-kge-yu-fa-fu-hao-by-leetcode-solution-zgwd/