当前位置：首页 > news >正文

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

news 2026/3/26 17:00:35

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

力扣题目链接：https://leetcode.cn/problems/find-kth-bit-in-nth-binary-string/

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

S₁= "0"
当i > 1时，S_i= S_i-1+ "1" + reverse(invert(S_i-1))

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

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

S₁= "0"
S₂= "011"
S₃= "0111001"
S₄= "011100110110001"

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

1 <= n <= 20
1 <= k <= 2ⁿ- 1

解题方法

解题方法一：模拟

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

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

AC代码

C++

/* * @LastEditTime: 2026-03-03 09:14:52 */classSolution{private:voidinvert(string&s){for(char&c:s){c=c=='0'?'1':'0';}}stringnext(string&now){string ans=now+'1';invert(now);reverse(now.begin(),now.end());ans+=now;returnans;}public:charfindKthBit(intn,intk){string now="0";for(inti=2;i<=n;i++){now=next(now);}returnnow[k-1];}};

解题方法二：递归 + 数学

对于字符串长度：

n1 = 1 n2 = 2 * n1 + 1 n3 = 2 * n2 + 1 ... n_k = ?

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

n k + 1 = 2 n k + 1 n_{k+1} = 2n_k + 1nk+1=2nk+1
两边都加一：n k + 1 + 1 = 2 n k + 1 + 1 = 2 ( n k + 1 ) n_{k+1} + 1 = 2n_k + 1 + 1 = 2(n_k + 1)nk+1+1=2nk+1+1=2(nk+1)
令a k = n k + 1 a_k = n_k + 1ak=nk+1，则：a k + 1 = 2 ⋅ a k a_{k+1} = 2 \cdot a_kak+1=2⋅ak
a k a_kak是一个公比为2的等比数列，且初项a 1 = n 1 + 1 = 2 a_1=n_1+1=2a1=n1+1=2，所以a k = 2 k a_k=2^kak=2k
由于a k = n k + 1 a_k = n_k + 1ak=nk+1，所以n k = a k − 1 = 2 k − 1 n_k=a_k-1=2^k-1nk=ak−1=2k−1。

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

字符串长度为2 n − 1 2^n-12n−1（记为l e n lenlen），说明生成这个字符串的上一个字符串的长度为l e n 2 \frac{len}{2}2len（记为h a l f _ l e n half\_lenhalf_len）。
如果k = = h a l f _ l e n + 1 k==half\_len+1k==half_len+1，则说明正好处在S_i= S_i-1+ “1” + reverse(invert(S_i-1))中间的1，直接返回1；
如果k ≤ h a l f _ l e n k\leq half\_lenk≤half_len，则说明处在S_i-1部分，返回findKthBit(n - 1, k)；
否则，说明处在reverse(invert(S_i-1))位置，k kk在l e n lenlen中是倒数第l e n − k + 1 len-k+1len−k+1个元素，，返回revert(findKthBit(n - 1, len - k + 1))。

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

AC代码

C++

/* * @LastEditTime: 2026-03-03 09:39:20 */classSolution{private:inlinecharinvert(charc){returnc=='0'?'1':'0';}public:charfindKthBit(intn,intk){if(n==1){return'0';}intlen=(1<<n)-1;inthalf_len=len>>1;if(k==half_len+1){return'1';}elseif(k<=half_len){returnfindKthBit(n-1,k);}else{returninvert(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 '''classSolution:definvert(self,n:str)->str:return'1'ifn=='0'else'0'deffindKthBit(self,n:int,k:int)->str:ifn==1:return'0'len=(1<<n)-1half=len>>1ifk==half+1:return'1'elifk<=half:returnself.findKthBit(n-1,k)else:returnself.invert(self.findKthBit(n-1,len-k+1))

C++

当然也可以：

/* * @LastEditTime: 2026-03-03 09:28:21 */classSolution{public:charfindKthBit(intn,intk,boolinvert=false){if(n==1){returninvert?'1':'0';}intlen=(1<<n)-1;inthalf_len=len>>1;if(k==half_len+1){returninvert?'0':'1';}elseif(k<=half_len){returnfindKthBit(n-1,k,invert);}else{returnfindKthBit(n-1,len-k+1,1^invert);// n = 2, k = 3 -> len = 3, half_len = 1, next_k = 1}}};