779. 第K个语法符号

思路

首先多扩充几行看看有什么规律：

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
6: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
......
1
2
3
4
5
6
7

发现有以下规律：

1. 第n行的$2^{n-1}$个数，与第n+1行的前$2^{n-1}$个数是相同的
2. 将第n行的$2^{n-1}$个数的序数划分为两个区间：$[1,2^{n-2}],[2^{n-2}+1,2^{n-1}]$，对于第i个数，$i\in [1,2^{n-2}]$，第$i+2^{n-2}$个数一定是其取反得到的。

通过规律1和2，我们可以做如下操作：

1. 用一个变量count记录翻转次数，表示下标k进行了几次转换
2. 若k在第n行中，且$k\in [2^{n-2}+1,2^{n-1}]$，我们进行一次进行一次翻转，将k修改为前半段对应的下标，并令count++；
3. 若k在第n行中，但是下标不在后半区间，那么k一定是在某一行的后半段的区间中，在该行内做转换。这样做成立的原因就是前面行中的数字与后面行中的数字一定是相等的。
4. 每次进行区间翻转时，实际上就是减去区间长度的一半。
5. 我们可以令下标从0开始，并令k = k-1，做翻转的操作其实就是k减去它最高位1所代表的值，直至减至k=0位置。实际上就是记录k-1二进制表示中1的个数。
6. count为奇数时说明翻转了奇数次才变为0，则原来的数为1；反之原来的数为0。

实际上就是判断k-1二进制表示中1是奇数个还是偶数个，奇偶校验？

代码如下：

class Solution {
public:
    int kthGrammar(int n, int k) {
        int count = 0; //记录反转了几次
        k-=1;
        while(k > 0){
            //每次减去它的lowbit;
            k = k - (k&(-k));
            count++;
        }
        return count % 2 == 1 ? 1: 0;  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13