难度: Medium
我们构建了一个包含 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 <= 301 <= k <= 2n - 1运行时间: 24 ms
内存: 0.0 MB
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
cur = 0
left, right = 1, 2 ** (n - 1)
for _ in range(n - 1):
mid = (left + right) // 2
if k <= mid:
right = mid
else:
left = mid + 1
cur = 0 if cur else 1
return cur
这个题解采用了二分查找的思路。根据题目的规律可以发现，每一行的前一半和后一半是完全对称的，且后一半的数字与前一半相反。利用这个特点，我们可以在每一层二分查找需要的数字是在前一半还是后一半，然后递归到下一层继续查找。通过这种方式，我们可以在对数时间内找到第 k 个数字。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
cur = 0 # 当前数字，初始为0
left, right = 1, 2 ** (n - 1) # 二分查找的左右边界
for _ in range(n - 1): # 循环 n-1 次
mid = (left + right) // 2 # 计算中点
if k <= mid:
right = mid # 如果 k 在左半部分，缩小右边界
else:
left = mid + 1 # 如果 k 在右半部分，缩小左边界
cur = 0 if cur else 1 # 更新当前数字，与上一层相反
return cur # 返回最终的数字
这种对称性可以从题目描述的生成规则中导出。对于给定的一行数字，下一行是通过以下方式生成的：每个0变为01，每个1变为10。从这个规则可以看出，第二行的前半部分（生成自第一行的0）是01，后半部分（生成自第一行的1）是10。这种模式在所有行中重复：每行的前一半生成下一行的前一半和后一半，后一半生成下一行的与前一半相反的后一半。因此，每一行的前一半和后一半是对称的，且后一半的数字与前一半相反。
这是因为每一行的后一半与前一半是对称且相反的。当我们通过二分查找确定k位于当前考察的范围的后半部分时，我们需要更新当前值`cur`。如果前一层`cur`是0（表示前半部分），在找到后半部分时，根据生成规则，应该是1。反之，如果前一层`cur`是1（表示后半部分），后半部分就应该是0。因此，每次当k落在后半部分时，我们需要取反当前`cur`的值以符合行的生成规则。
题解中的这个边界是基于每一行的长度来确定的。在第n行，元素的数量是2的(n-1)次方。这是因为，从第一行开始，每一行的元素数量是前一行的两倍，第一行有一个元素，第二行有两个元素，依此类推。所以，第n行有2^(n-1)个元素。当进行二分查找时，我们需要知道整个搜索区间的范围，这个范围就是从1到2^(n-1)，覆盖了第n行的所有可能位置。
题解中的二分查找逻辑是正确的，并且在所有情况下都能找到第k个数字。由于每次迭代都正确地将搜索范围减半，并适当地更新当前的`cur`值（基于前一半或后一半的对称反转规则），这确保了不会错过任何可能的情况。此外，由于递归的深度受限于n，这保证了算法的效率。然而，必须注意正确处理边界值，比如当k正好是中点时的情况，以及在最终迭代中准确返回`cur`值。