原题
在第一行我们写上一个 0
。接下来的每一行,将前一行中的0
替换为01
,1
替换为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
注意:
N
的范围[1, 30]
.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/