leetcode779-第K个语法符号

原题

在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为011替换为10

给定行数 N 和序数 K,返回第 N 行中第 K个字符。(K从1开始)

例子:

输入: N = 1, K = 1
输出: 0

输入: N = 2, K = 1
输出: 0

输入: N = 2, K = 2
输出: 1

输入: N = 4, K = 5
输出: 1

解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001

注意:

  1. N 的范围 [1, 30].
  2. K 的范围 [1, 2^(N-1)].

解法

思想

递归分析要查找的字符是上一行的哪个数字得到的,然后根据奇偶性得到目标字符

代码

class Solution {
    public int kthGrammar(int N, int K) {
        if(N==0) return 0;
        if(K%2 == 1){
            if(kthGrammar(N-1,(K+1)/2)==0) return 0;
            else return 1;
        }else{
            if(kthGrammar(N-1,(K+1)/2)==0) return 1;
            else return 0;
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode779-%e7%ac%ack%e4%b8%aa%e8%af%ad%e6%b3%95%e7%ac%a6%e5%8f%b7/

发表评论

电子邮件地址不会被公开。