Medium
题目描述
我们构建一个有 n 行（从 1 开始编号）的表格。我们从第 1 行写 0 开始。现在在每一个后续行中，我们查看前一行并将每个 0 替换为 01，每个 1 替换为 10。
例如，对于 n = 3，第 1 行是 0，第 2 行是 01，第 3 行是 0110。
给定两个整数 n 和 k，返回第 n 行中第 k 个（从 1 开始编号）符号。
示例 1：
输入：n = 1, k = 1
输出：0
解释：第 1 行：0
示例 2：
输入：n = 2, k = 1
输出：0
解释：
第 1 行：0
第 2 行：01
示例 3：
输入：n = 2, k = 2
输出：1
解释：
第 1 行：0
第 2 行：01
提示：
1 <= n <= 301 <= k <= 2^(n-1)- 尝试用某个
(N-1, prevK)来表示当前的(N, K)。prevK 是什么？
解题思路
这道题可以通过观察规律用递归来解决。
首先分析构建规律：
- 第1行：
0 - 第2行：
01（0→01） - 第3行：
0110（0→01, 1→10） - 第4行：
01101001（0→01, 1→10, 1→10, 0→01）
关键观察：第 n 行的前半部分与第 n-1 行相同，后半部分是第 n-1 行的"翻转"（0变1，1变0）。
具体来说，对于第 n 行的第 k 个位置：
- 如果 k 在前半部分（k <= 2^(n-2)），则它等于第 n-1 行的第 k 个位置
- 如果 k 在后半部分（k > 2^(n-2)），则它等于第 n-1 行的第 (k - 2^(n-2)) 个位置的翻转
这样我们就可以递归地将问题规模减小，直到 n=1 时返回 0。
另一种思路是观察二进制规律：第 n 行第 k 个位置的值等于 (k-1) 的二进制表示中 1 的个数的奇偶性。
代码实现
class Solution {
public:
int kthGrammar(int n, int k) {
if (n == 1) return 0;
int mid = 1 << (n - 2); // 2^(n-2)
if (k <= mid) {
return kthGrammar(n - 1, k);
} else {
return 1 - kthGrammar(n - 1, k - mid);
}
}
};
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
if n == 1:
return 0
mid = 2 ** (n - 2)
if k <= mid:
return self.kthGrammar(n - 1, k)
else:
return 1 - self.kthGrammar(n - 1, k - mid)
public class Solution {
public int KthGrammar(int n, int k) {
if (n == 1) return 0;
int mid = 1 << (n - 2); // 2^(n-2)
if (k <= mid) {
return KthGrammar(n - 1, k);
} else {
return 1 - KthGrammar(n - 1, k - mid);
}
}
}
var kthGrammar = function(n, k) {
if (n === 1) return 0;
let mid = Math.pow(2, n - 2);
if (k <= mid) {
return kthGrammar(n - 1, k);
} else {
return 1 - kthGrammar(n - 1, k - mid);
}
};
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(n) - 递归深度为 n，每层递归只做常数时间操作 |
| 空间复杂度 | O(n) - 递归调用栈的深度为 n |