图解LeetCode——779. 第K个语法符号（难度：中等）

一、题目

我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

【例如】对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。

给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

二、示例

2.1> 示例 1:

【输入】 n = 1, k = 1 【输出】 0 【解释】 第一行：0

2.2> 示例 2:

【输入】 n = 2, k = 1 【输出】 0 【解释】 第一行: 0 ，第二行: 01

2.3> 示例 3:

【输入】 n = 2, k = 2 【输出】 1 【解释】第一行: 0，第二行: 01

提示:

• • 1 <= n <= 30
• • 1 <= k <= 2n - 1

三、解题思路

通过题目描述，我们其实能够感受到生成每行最终结果是有规律性的，那么我们就先列出从第1行到第4行的结果。如下图所示，浅蓝色是每一行的新增部分，我们发现了一个规律，就是新增部分（蓝色）都是上一行（黄色）取反的。如第4行中：

【黄色部分】等同于第3行——0110。 【蓝色部分】等同于第3行的取反——1001。

发现了这个规律后，我们就可以很快地计算出第n行中所有的字符。由于题目中的“提示”部分已经指出1 <= n <= 30， 所以，这么长的0和1我们是没办法赋值给数字类型的，那么存储到字符串String类型？这样的代价也很大，那么有什么更好的办法吗？其实根据上面的规律来看，我们可以发现，无论是第几行的第几个字符，其实都是从第1行的这个“0”演变出来的。那么我们只要能找出第n行第k个字符与第1行的这个0的演变关系，就可以计算出它到底是0还是1了。

如下图所示，我们假设要找出第4行，第6列的这个字符是什么。那么为了找到它与第1行的“0”的演变关系，我们就需要从第4行向上去找，如下所示：

第4行第6列与第3行第2列之间的关系是——字符相反。 第3行第2列与第2行第2列之间的关系是——字符相同。 第2行第2列与第1行第1列之间的关系是——字符取反。 【最终结论】第4行第6列与第1行第1列之间的关系是——字符相反&字符相反，即：字符相同的。

好了，解题思路就这些了，总结出一句话就是：找出第n行第k个字符与第1行的这个0的演变关系。具体的操作过程，请参照下图所示：

四、代码实现

class Solution {
    public int kthGrammar(int n, int k) {
        if (k == 1) return 0; // 向上遍历到了第1行，则返回结果
        if (k > (1 << n - 2)) return 1 ^ kthGrammar(n - 1, k - (1 << n - 2)); // 如果在“蓝色区间”，则与上一行值相反
        else return kthGrammar(n - 1, k); // 如果在“黄色区间”，则与上一行值相同
    }
}