M1545.找出第 N 个二进制字符串中的第 K 位

recursion, https://leetcode.cn/problems/find-kth-bit-in-nth-binary-string/

给你两个正整数 n 和 k，二进制字符串 Sn 的形成规则如下：

• S1 = "0"
• 当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))

其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）。

例如，符合上述描述的序列的前 4 个字符串依次是：

• S1 = "0"
• S2 = "011"
• S3 = "0111001"
• S4 = "011100110110001"

请你返回 Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。

示例 1：

输入：n = 3, k = 1
输出："0"
解释：S3 为 "0111001"，其第 1 位为 "0" 。

示例 2：

输入：n = 4, k = 11
输出："1"
解释：S4 为 "011100110110001"，其第 11 位为 "1" 。

示例 3：

输入：n = 1, k = 1
输出："0"

示例 4：

输入：n = 2, k = 3
输出："1"

提示：

• 1 <= n <= 20
• 1 <= k <= 2^n - 1

方法一：递归

力扣官方题解 链接：https://leetcode.cn/problems/find-kth-bit-in-nth-binary-string/solutions/382517/zhao-chu-di-n-ge-er-jin-zhi-zi-fu-chuan-zhong-de-2/

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if k == 1:
            return "0"
        
        mid = 1 << (n - 1)
        if k == mid:
            return "1"
        elif k < mid:
            return self.findKthBit(n - 1, k)
        else:
            k = mid * 2 - k
            return "0" if self.findKthBit(n - 1, k) == "1" else "1"

复杂度分析

时间复杂度：O(n)。字符串 Sn 的长度为 2^n −1，每次递归调用可以将查找范围缩小一半，因此时间复杂度为 O(log2^n)=O(n)。

空间复杂度：O(n)。空间复杂度主要取决于递归调用产生的栈空间，递归调用层数不会超过 n。

这道题要求我们找出按照特定规则生成的第 n 个二进制字符串 Sn 中的第 k 位字符。由于 n 最大可以达到 20，Sn 的最大长度为 $2^{20}-1\approx {10}^6$，如果直接把字符串生成出来，时间和空间复杂度都会比较高。因此，我们可以通过找规律，利用递归或迭代的方法来以 $O(n)$ 的时间复杂度快速定位第 k 位。

规律分析：

根据字符串生成规则 $S_i=S_{i-1}+\text{"1"}+\text{reverse}(\text{invert}(S_{i-1}))$，我们可以观察到 $S_i$ 是由左半部分 $S_{i-1}$、中间的一个字符 "1"，以及右半部分（$S_{i-1}$ 反转并翻转）构成的。

字符串 $S_i$ 的长度 $L_i=2^i-1$。 因此它的中间位置正好是 $2^{i-1}$。 对于任意给定的 $n$ 和 $k$，有三种情况：

1. $k==2^{n-1}$：此时 k 正好位于字符串的正中间，而中间的字符总是 "1"。
2. $k<2^{n-1}$：此时 k 位于字符串的左半边，因为左半边完全等于 $S_{n-1}$，所以第 k 位字符即等于 $S_{n-1}$ 的第 k 位。
3. $k>2^{n-1}$：此时 k 位于字符串的右半边。因为右半边是 $S_{n-1}$ 反转并按位翻转而来的，所以该位置对应于 $S_{n-1}$ 中的第 $2^n-k$ 个字符，并且在此基础上发生了1次字符反转操作（0变1，1变0）。

我们可以利用一个变量 invert 来记录字符总共被翻转了多少次，将找寻目标不断缩小至较小的 $n$ 和相对应的 $k$，直到命中正中间或者是 $n=1$ 的首个基准字符串 $S_1$ 为止。

Python 3 解答：

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        invert = 0
        while n > 1:
            # 找到当前 Sn 字符串正中间的索引 (按 1-based 算)
            mid = 1 << (n - 1) 
            
            if k == mid:
                # 命中了位于正中间的 "1"
                # 根据反转次数的奇偶性来返回它的最终值
                return "1" if invert % 2 == 0 else "0"
            elif k > mid:
                # 在右半边，映射到左半部分的对应位置，并增加一次翻转计数
                k = (1 << n) - k
                invert += 1
            
            # 递推到更小层级的字符串
            n -= 1
            
        # 当 n 退回 1 时，S1 为 "0"
        return "0" if invert % 2 == 0 else "1"

复杂度分析：

• 时间复杂度：$O(n)$。在最坏情况下，我们要循环找直到 $n=1$。因为 $n$ 的最大值为 20，最多只需进行 20 次极其轻量的运算，速度极快（大约是 $O(\log k)$），完全满足各种严苛运行耗时要求。
• 空间复杂度：$O(1)$。我们只借用了几个常量级别的变量进行追踪计算，并没有额外使用数组或构建长字符串去占据堆内存。