Description
On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.
Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).
第一行输入0，接下去每一行从左至右解析，0->01,1->10,输出第N行的第K个数
Solution
法1：filp or not
树结构
- 当K为奇数时对应左孩子，K为偶数时对应右孩子;
- 左孩子值和父节点相同，右孩子值是父节点的0-1翻转;
- 由递推关系想到使用
;
- 左孩子的父节点为（K+1)/2,右孩子的父节点为K/2
class Solution {
public int kthGrammar(int N, int K) {
if(N == 1) return 0;
// right child
if(K % 2 == 0) return (kthGrammar(N-1,K/2)== 0)? 1 : 0;
//left child
else return (kthGrammar(N-1,(K+1)/2)== 0)? 0 : 1;
}
}
法2：异或运算
1.可以发现： 左孩子 = 父节点^0; 右孩子 = 父节点 ^ 1;
class Solution {
public int kthGrammar(int N, int K) {
if(N == 1) return 0;
// right child
if(K % 2 == 0) return kthGrammar(N-1,K/2)^1;
// left child
else return kthGrammar(N-1,(K+1)/2)^ 0;
}
}
