779. 第K个语法符号
程序员文章站
2024-03-19 20:13:46
...
难度:中等
在第一行我们写上一个
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
分析:
一般而言,第 K
位的父位应该是第 (K+1) / 2
位。如果父位是 0
,那么这一位就是 1 - (K%2)
。如果父位是 1
,那么这一位就是 K%2
。
代码:
class Solution {
public int kthGrammar(int N, int K) {
if (N == 1) return 0;
return (~K & 1) ^ kthGrammar(N-1, (K+1)/2);
}
}
结果:
上一篇: centos 常用命令笔记
下一篇: MongoDB如何添加用户?使其有效?