1545.找出第 N 个二进制字符串中的第 K 位：模拟 或 递归(数学)

【LetMeFly】1545.找出第 N 个二进制字符串中的第 K 位：模拟 或 递归(数学)

力扣题目链接：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 <= 2n - 1

解题方法

解题方法一：模拟

写一个函数，求当前字符串的下一个字符串，一直模拟$n-1$次next就好了。注意最终返回下标k-1。

• 时间复杂度$O(2^n)$
• 空间复杂度$O(2^n)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-03 09:14:52
 */
class Solution {
private:
    void invert(string& s) {
        for (char& c : s) {
            c = c == '0' ? '1' : '0';
        }
    }

    string next(string& now) {
        string ans = now + '1';
        invert(now);
        reverse(now.begin(), now.end());
        ans += now;
        return ans;
    }
public:
    char findKthBit(int n, int k) {
        string now = "0";
        for (int i = 2; i <= n; i++) {
            now = next(now);
        }
        return now[k - 1];
    }
};

解题方法二：递归 + 数学

对于字符串长度：

n1 = 1
n2 = 2 * n1 + 1
n3 = 2 * n2 + 1

...

n_k = ?

答案是$n_k=2^k-1$，原因如下：

$n_{k+1} = 2n_k + 1$

两边都加一：$n_{k+1} + 1 = 2n_k + 1 + 1 = 2(n_k + 1)$

令 $a_k = n_k + 1$，则：$a_{k+1} = 2 \cdot a_k$

$a_k$是一个公比为2的等比数列，且初项$a_1=n_1+1=2$，所以$a_k=2^k$

由于$a_k = n_k + 1$，所以$n_k=a_k-1=2^k-1$。

那么findKthBit就可以依据字符串的长度（计算自$n$）计算出要找的$k$在字符串中的哪个位置了：

字符串长度为$2^n-1$（记为$len$），说明生成这个字符串的上一个字符串的长度为$\frac{len}{2}$（记为$half_len$）。

• 如果$k==half_len+1$，则说明正好处在Si = Si-1 + "1" + reverse(invert(Si-1))中间的1，直接返回1；
• 如果$k\leq half_len$，则说明处在Si-1部分，返回findKthBit(n - 1, k)；
• 否则，说明处在reverse(invert(Si-1))位置，$k$在$len$中是倒数第$len-k+1$个元素，，返回revert(findKthBit(n - 1, len - k + 1))。

• 时间复杂度$O(n)$
• 空间复杂度$O(n)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-03 09:39:20
 */
class Solution {
private:
    inline char invert(char c) {
        return c == '0' ? '1' : '0';
    }
public:
    char findKthBit(int n, int k) {
        if (n == 1) {
            return '0';
        }
        int len = (1 << n) - 1;
        int half_len = len >> 1;
        if (k == half_len + 1) {
            return '1';
        } else if (k <= half_len) {
            return findKthBit(n - 1, k);
        } else {
            return invert(findKthBit(n - 1, len - k + 1));  // n = 2, k = 3 -> len = 3, half_len = 1, next_k = 1
        }
    }
};

Python

'''
LastEditTime: 2026-03-03 20:16:16
'''
class Solution:
    def invert(self, n: str) -> str:
        return '1' if n == '0' else '0'
    
    def findKthBit(self, n: int, k: int) -> str:
        if n == 1:
            return '0'
        len = (1 << n) - 1
        half = len >> 1
        if k == half + 1:
            return '1'
        elif k <= half:
            return self.findKthBit(n - 1, k)
        else:
            return self.invert(self.findKthBit(n - 1, len - k + 1))

C++

当然也可以：

/*
 * @LastEditTime: 2026-03-03 09:28:21
 */
class Solution {
public:
    char findKthBit(int n, int k, bool invert=false) {
        if (n == 1) {
            return invert ? '1' : '0';
        }
        int len = (1 << n) - 1;
        int half_len = len >> 1;
        if (k == half_len + 1) {
            return invert ? '0' : '1';
        } else if (k <= half_len) {
            return findKthBit(n - 1, k, invert);
        } else {
            return findKthBit(n - 1, len - k + 1, 1 ^ invert);  // n = 2, k = 3 -> len = 3, half_len = 1, next_k = 1
        }
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源