题目
我们构建了一个包含 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
解题
方法一:递归
如果节点为左子节点,那么和父节点一样,如何节点为右子节点,那么和父节点值相反。
比如n=3,k=3的情况,此时 (3&1)=1,!(3&1)=0,0异或x=x,因此k为奇数的时候,就和父节点的值相等,因此递归去算父节点的值就行了。
class Solution { public: int kthGrammar(int n, int k) { if(n==1) return 0; return !(k&1)^kthGrammar(n-1,(k+1)/2); } };