[Java] 779. K-th Symbol in Grammar

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

树结构

1. 当K为奇数时对应左孩子，K为偶数时对应右孩子;
2. 左孩子值和父节点相同，右孩子值是父节点的0-1翻转;
3. 由递推关系想到使用;
4. 左孩子的父节点为（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;
        
    }
}