Medium

题目描述

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

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

其中 + 表示串联操作，reverse(x) 将字符串 x 反转，invert(x) 将 x 中的每一位取反（0 变为 1，1 变为 0）。

例如，序列中的前四个字符串为：

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

返回 Sn 的第 k 位字符。题目数据保证 k 对于给定的 n 是有效的。

示例 1：

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

示例 2：

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

提示：

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

解题思路

这道题有两种主要解法：

解法一：直接模拟 由于 n 的范围很小（≤ 20），我们可以直接按照题目描述构造字符串。每次构造 Si 时，需要：

  1. 取 Si-1
  2. 加上 “1”
  3. 加上 reverse(invert(Si-1))

这种方法简单直观，但空间复杂度较高。

解法二：递归优化（推荐） 观察字符串的构造规律：Si = Si-1 + “1” + reverse(invert(Si-1))

  • Si 的长度为 2^i - 1
  • Si 的中间位置（第 2^(i-1) 位）总是 “1”
  • Si 的前半部分就是 Si-1
  • Si 的后半部分是 Si-1 的反转取反

利用这个规律，我们可以递归地找到第 k 位，而不需要构造完整的字符串：

  1. 如果 k 在前半部分，递归查找 Si-1 的第 k 位
  2. 如果 k 是中间位置，返回 “1”
  3. 如果 k 在后半部分，递归查找对应位置并取反

这种方法时间复杂度 O(n)，空间复杂度 O(n)（递归栈）。

代码实现

class Solution {
public:
    char findKthBit(int n, int k) {
        if (n == 1) return '0';
        
        int length = (1 << n) - 1;  // 2^n - 1
        int mid = length / 2 + 1;
        
        if (k == mid) {
            return '1';
        } else if (k < mid) {
            return findKthBit(n - 1, k);
        } else {
            // k > mid, 在后半部分
            int mirror_pos = length - k + 1;
            char result = findKthBit(n - 1, mirror_pos);
            return result == '0' ? '1' : '0';
        }
    }
};

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if n == 1:
            return "0"
        
        length = (1 << n) - 1  # 2^n - 1
        mid = length // 2 + 1
        
        if k == mid:
            return "1"
        elif k < mid:
            return self.findKthBit(n - 1, k)
        else:
            # k > mid, 在后半部分
            mirror_pos = length - k + 1
            result = self.findKthBit(n - 1, mirror_pos)
            return "1" if result == "0" else "0"

public class Solution {
    public char FindKthBit(int n, int k) {
        if (n == 1) return '0';
        
        int length = (1 << n) - 1;  // 2^n - 1
        int mid = length / 2 + 1;
        
        if (k == mid) {
            return '1';
        } else if (k < mid) {
            return FindKthBit(n - 1, k);
        } else {
            // k > mid, 在后半部分
            int mirrorPos = length - k + 1;
            char result = FindKthBit(n - 1, mirrorPos);
            return result == '0' ? '1' : '0';
        }
    }
}

var findKthBit = function(n, k) {
    if (n === 1) return '0';
    
    const length = (1 << n) - 1;
    const mid = Math.floor(length / 2) + 1;
    
    if (k === mid) {
        return '1';
    } else if (k < mid) {
        return findKthBit(n - 1, k);
    } else {
        const mirrorPos = length - k + 1;
        const bit = findKthBit(n - 1, mirrorPos);
        return bit === '0' ? '1' : '0';
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型递归解法直接模拟
时间复杂度O(n)O(2^n)
空间复杂度O(n)O(2^n)

说明：

  • 递归解法每次递归深度减1，最多递归n次，时间复杂度O(n)
  • 直接模拟需要构造长度为2^n-1的字符串，时间和空间复杂度都是O(2^n)
  • 推荐使用递归解法，效率更高