友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
779. 第K个语法符号
我们构建了一个包含 n 行(*索引从 1 开始 *)的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的 0 替换为 01，1 替换为 10。
-
例如，对于
n = 3，第1行是0，第2行是01，第3行是0110。
给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（k 从索引 1 开始）
示例 1:
输入: n = 1, k = 1 输出: 0 解释: 第一行：0
示例 2:
输入: n = 2, k = 1 输出: 0 解释: 第一行: 0 第二行: 01
示例 3:
输入: n = 2, k = 2 输出: 1 解释: 第一行: 0 第二行: 01
提示:
-
1 <= n <= 30 -
1 <= k <= 2n-1
思路分析
总结出一句话就是：找出第 n 行第 k 个字符与第 1 行的这个 0 的演变关系。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-06-16 22:47:20
*/
public int kthGrammar(int n, int k) {
// 向上遍历到了第1行，则返回结果
if (k == 1) {
return 0;
}
// 如果在“蓝色区间”，则与上一行值相反
if (k > (1 << (n - 2))) {
return 1 ^ kthGrammar(n - 1, k - (1 << (n - 2)));
}
// 如果在“黄色区间”，则与上一行值相同
return kthGrammar(n - 1, k);
}