这道题题意比较好理解，所以很容易能想到使用递归，我们可以正常分析下，第i行的第j个数字，会生成第i+1行的第2j-1和第2j个数字，且满足0生成的是01，1生成的是10，主要是递归的公式不好得出，官方解的num1=(x&1)⊕1⊕num2，其中x表示下一行的第x个数，可以从另一个角度分析，每一行的前半部分和上一行完全相同，后半部分是上一行的01翻转，所以可以分成两部分递归。还有一个思路是位运算的思路，通过找规律可以发现，偶数位2i的字符适合第i个字符相同的，第2i+1奇数位的字符是第i个字符的反转，注意这里考虑的是一行，因为前面也说了前半部分和上一行相同，所以可以放在一行思考，那么就可以对k及逆0行判断，如果k是奇数，就要一次反转，奇数次反转，然后除以2也就是取前半部分然后继续判断，累计次数，直到k为0，而这个过程就是取k-1的二进制中有多少个1，然后与1进行与运算判断即可。
func kthGrammar(n, k int) int {
if n == 1 {
return 0
}
return k&1 ^ 1 ^ kthGrammar(n-1, (k+1)/2)
}func kthGrammar(n int, k int) int {
if n == 1 {
return 0
}
// 如果是前半部分，向上直接递归
if k <= (1 << (n - 2)) {
return kthGrammar(n-1, k)
}
// 如果是后半部分需要做01的反转
return kthGrammar(n-1, k-(1<<(n-2))) ^ 1
}func kthGrammar(n int, k int) int {
return bits.OnesCount(uint(k-1)) & 1
}