779. 第K个语法符号

我就是我 2024-04-01 08:58 27阅读 0赞

问题描述：  
我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。  
给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

示例：  
`输入: n = 2, k = 2 输出: 1 解释: 第一行: 0 第二行: 01`

算法思路：  
先推到第四行看看。  
![红色为新添的数字][aaa0a7dd054b4706bc281d2ba7264d39.png]  
红色为新添的数字。

明显发现其实**每一行都是新添一个取反(上一行的数)**。  
0 取反为 1， 0 1 取反为1 0

假设我们查询第四行的第7个数，第七个数必是第三个数（7-4=3）的取反，第三个数即“1”，第三个数是第三行新添来的，必是第一个数(3-2=1)的取反。第一个数是0，故第三个数是1，第七个数也就是0。

直接上代码：

1.  用while的方式实现

public int kthGrammar(int n, int k) {
        
            int flag = 0;
            while(k != 1){
        
                double a = Math.pow(2,n-2);
                if(k>a){
        
                    k -= a;
                    flag = 1 ^ flag; //异或
                }
                n--;
            }
            return flag;
        }

![在这里插入图片描述][5bdc55ae4dfd4dbbaed24309dca1d39c.png]

1.  用递归方式实现

public int kthGrammar(int n, int k) {
        
            // 递归的方式
            if(k == 1){
        
                // 第一行的数是0
                return 0;
            }
    
            // 如果不是本行添加的，那就到上一行再处理
            if(k <= (1 << (n - 2))){
        
                return kthGrammar(n-1,k);
            }
            return 1 ^ kthGrammar(n-1,k-(1 << (n - 2)));
        }

[aaa0a7dd054b4706bc281d2ba7264d39.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bed2be6f403d4e5caf5ff01591a14d39.png
[5bdc55ae4dfd4dbbaed24309dca1d39c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e8b9a4d5b2cf467f9704618ce26ea0c3.png