Problem:
On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10. Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).
Examples:
Input: N = 1, K = 1 Output: 0 Input: N = 2, K = 1 Output: 0 Input: N = 2, K = 2 Output: 1 Input: N = 4, K = 5 Output: 1 Explanation: row 1: 0 row 2: 01 row 3: 0110 row 4: 01101001
Note:
思路: 暴力的做法:枚举出1~30的字符串,找到第k个字符,输出答案即可。此做法MLE,比如到第30个字符串时,它的长度高达2^29。所以得找找模式了,枚举前5个:
1. 0
2. 0 1
3. 0 1 1 0
4. 0 1 1 0 1 0 0 1
5. 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
很容易发现,比如第5个字符串的前半段刚好是第4个字符串的所有答案,后半段是前半段每位取反。
所以,如果K是后半段,我们把它转成前半段求解,既然前半段是上一个字符串的答案,就可以直接转去求解上一个字符串。
定义canSolve(N, K)
如果K在后半段: canSolve(N, K 映射至前半段K')
canSolve(N - 1, K')
这样问题就被一步步归简为最初的形式。
代码如下:
public int kthGrammar(int N, int K) {
if (N == 1) return 0;
int len = 1 << (N - 1);
len /= 2;
if (K <= len) return kthGrammar(N - 1, K);
else {
return kthGrammar(N - 1, K - len) ^ 1;
}
}
Python版本:
class Solution(object):
def kthGrammar(self, N, K):
"""
:type N: int
:type K: int
:rtype: int
"""
if N == 1: return 0
len = 2 ** (N - 1) / 2
if K <= len: return self.kthGrammar(N - 1, K)
else: return 1 ^ self.kthGrammar(N - 1, K - len)