第K个语法符号

在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）
例子:

输入: N = 1, K = 1
输出: 0
输入: N = 2, K = 1
输出: 0
输入: N = 2, K = 2
输出: 1
输入: N = 4, K = 5
输出: 1
解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001

注意：
N 的范围 [1, 30].
K 的范围 [1, 2^(N-1)].

解决方案

1.暴力法

思路
我们完全按照题目描述中的指示处理每一行，而只需要保存最新的那一行。
但是不幸的是，字符串的长度可能有 10 亿左右，因为每一行的长度都是前一行的两倍，所以这种方法不够高效。

class Solution {
    public int kthGrammar(int N, int K) {
        int[] lastrow = new int[1 << N];
        for (int i = 1; i < N; ++i) {
            for (int j = (1 << (i-1)) - 1; j >= 0; --j) {
                lastrow[2*j] = lastrow[j];
                lastrow[2*j+1] = 1 - lastrow[j];
            }
        }
        return lastrow[K-1];
    }
}

复杂度分析

时间复杂度： $O(2^N)$ ，我们解析每一行所需要的时间和其长度有关，共计 $2^0 + 2^1 + \cdots + 2^{N-1}$ 。

空间复杂度： $O(2^N)$ ，最后一行（lastrow）的长度。

方法二：递归（父变体）

思路
因为生成每一行只需要前一行的信息，所以我们可以考虑解析前一行的位来输出答案。

来看这个例子，如果我们中间有一行是 "0110"，那么就会生成 "01101001"作为它的下一行，也就是说第一位 "0" 生成下一行中的第一个 "01"，第二位 "1" 生成下一行中的 "10"，接着 "1" 又生成了 "10"，而最后的 "0" 将会生成最后的 "01"。

一般而言，第 K 位的父位应该是第 (K+1) / 2 位。如果父位是 0，那么这一位就是 1 - (K%2)。如果父位是 1，那么这一位就是 K%2。

class Solution {
    public int kthGrammar(int N, int K) {
        if (N == 1) return 0;
        return (~K & 1) ^ kthGrammar(N-1, (K+1)/2);
    }
}
注： &1 表示判断奇偶，判断奇偶后与递归结果 进行异或运算，得出迭代结果

复杂度分析

时间复杂度： $O(N)$ 。找出答案需要 $N-1$ 步。
空间复杂度： $O(1)$ 。

方法三：递归（翻转变体）

思路
就像在 方法二 中那样，我们可以尝试按它前面的位来写出这一位。

如果我们写出该序列中的几行，就可以发现：后半部分总是与前半部分相反，也就是说：'0' 变成 '1' 而 '1' 变成 '0'。

我们可以用归纳法来验证这一推断。其关键思想是，如果字符串 X生成 Y，那么翻转后的字符串 X^' 将会生成 Y^'。

这就引出了下面的算法思想：如果 K 在后半部分，那么我们可以将 K -= (1 << N-2) 设为前半部分，然后翻转得到最终答案。

class Solution {
    public int kthGrammar(int N, int K) {
        if (N == 1) return 0;
        if (K <= 1 << N-2)
            return kthGrammar(N-1, K);
        return kthGrammar(N-1, K - (1 << N-2)) ^ 1;
    }
}

复杂度分析

时间复杂度： $O(N)$ 。找出答案需要 $N-1$ 步。
空间复杂度： $O(1)$ 。

方法四：二进制计数

思路
在 方法三 中，每一行的后半部分是前半部分反转后的结果。

当索引 K 写为二进制形式后（从 0 开始索引），后半部分的索引的第一位总是 1。

这意味着，当使用方法三中的算法时，我们翻转最终答案的次数仅仅是 K-1 的二进制表示中的 1 的个数。

class Solution {
    public int kthGrammar(int N, int K) {
        return Integer.bitCount(K - 1) % 2;
    }
}

复杂度分析

时间复杂度： $O(\log N)$ ，即 N 的二进制表示的位数。如果 $\log N$ 是有界的，那么可以将其视作 $O(1)$ 。
空间复杂度： $O(1)$ 。（在 Python 中，bin(X) 会创造一个长度为 $O(\log X)$ 的字符串，这是可以避免的。）

第K个语法符号