【leetcode】779.第K个语法符号（四种方法开阔思路，java实现）

779. 第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

注意：

1. N 的范围 [1, 30].
2. K 的范围 [1, 2^(N-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)$O(2N)，其为生成字符串的总长度 $2^0 + 2^1 + \cdots + 2^{N-1}$20+21+⋯+2N−1。
• 空间复杂度： $O(2^N)$O(2N)，其为最后一行字符串的长度。

方法二： 递归 (父子递推)

思路和算法

既然每一行都是根据上一行来生成的，把这样的上下两行写成比特形式找一下规律。

如果当前行为 "0110"，由此生成的下一行为 "01101001"。

据此可以总结出规律，第 K 个数字是上一行第 (K+1) / 2 个数字生成的。如果上一行的数字为 0，被生成的数字为 1 - (K%2)，如果上一行的数字为 1，被生成的数字为 K%2。

• 第 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;
        
        int value = kthGrammar(N-1, (K+1)/2);
        
        return (value == 0) ? (1- K%2) : (K%2);
    }
}

• 父节点位置：（k+1）/2
• 当k是奇数（k%2=1），父节点值为1时，k对应的值为1；
• 当k是偶数（k%2=0），父节点值为0时，k对应的值为0；
• 当k是奇数（k%2=1），父节点值为0时，k对应的值为0；
• 当k是偶数（k%2=0），父节点值为1时，k对应的值为1；
• 总结：相同为1，不同为0; 正好和“异或”^相反，所以对k取反，再&1，判断位置奇偶性，再与父节点的值异或，即可得当前值.

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

复杂度分析

• 时间复杂度： O(N)。
• 空间复杂度： O(1)。

方法三： 递归 (翻转递推)

思路和算法

同方法二一样，把上下两行写成比特形式找一下规律。

按照规律写出几行，可以注意到一个规律：每一行的后半部分正好是前半部分的 ”翻转“，前半部分是 '0'，后半部分变成 '1'，前半部分是 '1'，后半部分变成 '0'。

可以通过归纳法证明以上规律，核心的思想在于，如果 X 可以生成 Y，那么 Y 就能生成 X。据此可以提出以下的算法： 如果 K 在第二部分，就找 K -= (1 << N-2) 在第一部分的答案，然后将答案翻转。

• 后半部分总是与前半部分相反，也就是说：‘0’ 变成 ‘1’ 而 ‘1’ 变成 ‘0’。
• 思想：如果 K 在后半部分，那么我们可以将 K -= (1 << N-2) 设为前半部分，然后翻转得到最终答案。
• 第 N 行对应的位数是 2 的 N-1 次方, 即 1 << N-1；
• 则前半部分最后一位的位数为 1 << N-2；
• 如果 K <= 1 << N-2， 则直接读取上一行的 K 位置即可；
• 否则，读取未翻转前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)。
• 空间复杂度： O(1)。

方法四： Binary Count

思路和算法

同方法三一样，每一行的后半部分都是前半部分的翻转。

把下标 K 写成二进制的形式，如果 K 在第二部分，那么二进制形式的第一个比特位一定是 1。据此可以将方法三继续简化，实际上翻转的次数等于 K-1 二进制表示形式中 1 出现的个数。

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

复杂度分析

• 时间复杂度：O*(log*N)，其为 N 的二进制字符串表示形式的长度。
• 空间复杂度：O(1)。