题目描述

leetcode 779. 第K个语法符号

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

  • 例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。

给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）


示例 1:

输入: n = 1, k = 1
输出: 0
解释: 第一行：0

示例 2:

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

示例 3:

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

 

提示:

  • 1 <= n <= 30
  • 1 <= k <= 2n - 1

题解——脑筋急转弯：作图理解，c++一行

思路

先做出前几行的图看一看，可以生成如下一棵满二叉树

B200DCFA0129D79E4CE58FC3CF71201E.jpg
可以看出，某一个位置是1还是0，只取决于它的父亲以及它是left还是right。假如是左孩子，就与父亲相同；否则与父亲相反。所以，我们要判断某一个位置，就要先求它的父亲，然后根据位置判断是否取反即可。

可以采用递归：如果是第一层，直接返回0，否则求它的父亲。(n,k)的父亲的位置，就是(n-1,(k+1)/2)，第二个参数代表k/2向上取整。而某个位置是左孩子还是右孩子，可以判断k是否为奇数，如果是奇数，就是左孩子，那就应该与父亲相同，否则相反。这可以通过异或实现。如果是奇数，k%2==1，否则k%2==0，而0异或一个数不改变值，所以我们将k%2取反再与父亲异或即可。

代码

1
2
3
4
5
6
class Solution {
public:
    int kthGrammar(int n, int k) {
        return n==1?0:(!(k%2))^kthGrammar(n-1,(k+1)/2);
    }
};