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}

解法

方法一：递归

我们先来看一下前几行的规律：

n = 1: 0
n = 2: 0 1
n = 3: 0 1 1 0
n = 4: 0 1 1 0 1 0 0 1
n = 5: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
...

可以发现，每一行的前半部分和上一行完全一致，后半部分是上一行的反转。注意，这里的“反转”指的是 $0$ 变 $1$, $1$ 变 $0$。

如果 $k$ 在前半部分，那么第 $k$ 个字符就是上一行的第 $k$ 个字符，直接递归 $kthGrammar(n - 1, k)$ 即可。

如果 $k$ 在后半部分，那么第 $k$ 个字符就是上一行的第 $k - 2^{n - 2}$ 个字符的反转，即 $kthGrammar(n - 1, k - 2^{n - 2}) \oplus 1 $。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

Python3

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0
        if k <= (1 << (n - 2)):
            return self.kthGrammar(n - 1, k)
        return self.kthGrammar(n - 1, k - (1 << (n - 2))) ^ 1

Java

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;
    }
}

C++

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;
    }
};

Go

func kthGrammar(n int, k int) int {
	if n == 1 {
		return 0
	}
	if k <= (1 << (n - 2)) {
		return kthGrammar(n-1, k)
	}
	return kthGrammar(n-1, k-(1<<(n-2))) ^ 1
}

TypeScript

function kthGrammar(n: number, k: number): number {
    if (n == 1) {
        return 0;
    }
    if (k <= 1 << (n - 2)) {
        return kthGrammar(n - 1, k);
    }
    return kthGrammar(n - 1, k - (1 << (n - 2))) ^ 1;
}

方法二：位运算 + 脑筋急转弯

题目中索引从 $1$ 开始，我们将 $k$ 改成 $k-1$，将索引转换为从 $0$ 开始。在接下来的讨论中，索引均从 $0$ 开始。

仔细观察，一行中的第 $i$ 个字符，会在第 $2i$ 和第 $2i+1$ 个位置产生两个字符。

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

如果第 $i$ 个字符是 $0$，那么在位置 $2i$ 和 $2i+1$ 产生的字符分别是 $0$ 和 $1$；如果第 $i$ 个字符是 $1$，产生的字符是 $1$ 和 $0$。

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
      ^     * *

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
        ^       * *

可以发现，第 $2i$ （偶数位）个字符总是和第 $i$ 个字符相同，而第 $2i+1$ （奇数位）个字符是第 $i$ 个字符的反转。也就是说，奇数位上的字符总是发生了一次反转而来的。反转偶数次，字符不变；反转奇数次，相当于反转了一次。

因此，我们只需要看 $k$ 这个数字是否是奇数，若是，累计一次反转。然后将 $k$ 除以 $2$，继续判断，并累计反转次数，直至 $k$ 为 $0$。

最后判断反转的次数是否为奇数，是则答案为 $1$，否则为 $0$。

以上累计反转次数的过程，实际上等价于求 $k$ 的二进制表示中，有多少位是 $1$。

时间复杂度 $O(\log k)$，空间复杂度 $O(1)$。

Python3

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        return (k - 1).bit_count() & 1

Java

class Solution {
    public int kthGrammar(int n, int k) {
        return Integer.bitCount(k - 1) & 1;
    }
}

C++

class Solution {
public:
    int kthGrammar(int n, int k) {
        return __builtin_popcount(k - 1) & 1;
    }
};

Go

func kthGrammar(n int, k int) int {
	return bits.OnesCount(uint(k-1)) & 1
}

TypeScript

function kthGrammar(n: number, k: number): number {
    return bitCount(k - 1) & 1;
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}