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個(gè)數(shù)
Solution
法1：filp or not
樹結(jié)構(gòu)
- 當(dāng)K為奇數(shù)時(shí)對(duì)應(yīng)左孩子，K為偶數(shù)時(shí)對(duì)應(yīng)右孩子;
- 左孩子值和父節(jié)點(diǎn)相同，右孩子值是父節(jié)點(diǎn)的0-1翻轉(zhuǎn);
- 由遞推關(guān)系想到使用
;
- 左孩子的父節(jié)點(diǎn)為（K+1)/2,右孩子的父節(jié)點(diǎn)為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：異或運(yùn)算
1.可以發(fā)現(xiàn)： 左孩子 = 父節(jié)點(diǎn)^0; 右孩子 = 父節(jié)點(diǎn) ^ 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;
}
}
