美文网首页
[Java] 779. K-th Symbol in Gramm

[Java] 779. K-th Symbol in Gramm

作者: 葵sunshine | 来源:发表于2019-07-22 23:20 被阅读0次

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. 由递推关系想到使用\color{red}{递归};
  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;
        
    }
}

相关文章

网友评论

      本文标题:[Java] 779. K-th Symbol in Gramm

      本文链接:https://www.haomeiwen.com/subject/hnnglctx.html