// 0779. K-th Symbol in Grammar
class Solution {
public int kthGrammar(int n, int k) {
if (n == 1) return 0;
if (k <= 1 << n - 2) return kthGrammar(n - 1, k);
else return kthGrammar(n - 1, k - (1 << n - 2)) ^ 1;
}
}
学习笔记：
这是一道找规律的题目。
0
01
0110
01101001
0110100110010110
后半段都是前半段取反后平移到后面来的。
每一行的前半段都和上面的一样。
我们要找第5行第11个，怎么办呢？
第5行有16个，后8个是前8个取反来的。第5行第11个就是第5行第3个取反。
那么第5行第3个是什么呢？其实就是第4行第3个。
那么第4行第3个是什么呢？其实就是第3行第3个。
那么第3行第3个是什么呢？其实就是第3行第1个取反。
那么第3行第1个是什么呢？其实就是第2行第1个。
那么第2行第1个是什么呢？其实就是第1行第1个也即是0。
所以就有了推导的公式，一旦发现处于后半段就需要取反。
