【递归, 位运算】第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

解题

方法一：递归 位运算

思路

把每一行看作每一层就可以构造一棵满二叉树：

这样我们就找到了规律：每个节点上的值只与其父节点的值以及其是左子节点还是右子节点有关，具体来说：

• 左子节点上的值与其父节点相同（$0\to0, 1\to1$）
• 右子节点上的值与其父节点相反（$0\to1, 1\to0$）

众所周知，满二叉树可以用数组存储，此时由某节点 $x$ 可以找到其父节点 $\frac{x+1}{2}$ ，那么求第任意层的第任意个值都可以递归到其根节点 $0$ 上。

异或上一个 $1$ 可以做到把 $1$ 变 $0$ ，把 $0$ 变 $1$。

代码

class Solution {
    public int kthGrammar(int n, int k) {
        if (n == 1) return 0;
        return (k & 1) == 0 ?
            kthGrammar(n - 1, (k + 1) / 2) ^ 1 :
            kthGrammar(n - 1, (k + 1) / 2);
    }
}

一行写法

class Solution {
public:
    int kthGrammar(int n, int k) {
        return n == 1 ? 0 : !(k & 1) ^ kthGrammar(n - 1, (k + 1) / 2);
    }
};

class Solution {
public:
    int kthGrammar(int n, int k) {
        return n == 1 ? 0 : !(k & 1) ^ kthGrammar(n - 1, (k + 1) / 2);
    }
};