LeetCode 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 0S2 011S3 0111001S4 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 201 k 2n- 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(strings){for(charc:s){cc0?1:0;}}stringnext(stringnow){string ansnow1;invert(now);reverse(now.begin(),now.end());ansnow;returnans;}public:charfindKthBit(intn,intk){string now0;for(inti2;in;i){nownext(now);}returnnow[k-1];}};解题方法二递归 数学对于字符串长度n1 1 n2 2 * n1 1 n3 2 * n2 1 ... n_k ?答案是n k 2 k − 1 n_k2^k-1nk​2k−1原因如下n k 1 2 n k 1 n_{k1} 2n_k 1nk1​2nk​1两边都加一n k 1 1 2 n k 1 1 2 ( n k 1 ) n_{k1} 1 2n_k 1 1 2(n_k 1)nk1​12nk​112(nk​1)令a k n k 1 a_k n_k 1ak​nk​1则a k 1 2 ⋅ a k a_{k1} 2 \cdot a_kak1​2⋅ak​a k a_kak​是一个公比为2的等比数列且初项a 1 n 1 1 2 a_1n_112a1​n1​12所以a k 2 k a_k2^kak​2k由于a k n k 1 a_k n_k 1ak​nk​1所以n k a k − 1 2 k − 1 n_ka_k-12^k-1nk​ak​−12k−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 khalf\_len1khalf_len1则说明正好处在Si Si-1 “1” reverse(invert(Si-1))中间的1直接返回1如果k ≤ h a l f _ l e n k\leq half\_lenk≤half_len则说明处在Si-1部分返回findKthBit(n - 1, k)否则说明处在reverse(invert(Si-1))位置k kk在l e n lenlen中是倒数第l e n − k 1 len-k1len−k1个元素返回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){returnc0?1:0;}public:charfindKthBit(intn,intk){if(n1){return0;}intlen(1n)-1;inthalf_lenlen1;if(khalf_len1){return1;}elseif(khalf_len){returnfindKthBit(n-1,k);}else{returninvert(findKthBit(n-1,len-k1));// 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:return1ifn0else0deffindKthBit(self,n:int,k:int)-str:ifn1:return0len(1n)-1halflen1ifkhalf1:return1elifkhalf:returnself.findKthBit(n-1,k)else:returnself.invert(self.findKthBit(n-1,len-k1))C当然也可以/* * LastEditTime: 2026-03-03 09:28:21 */classSolution{public:charfindKthBit(intn,intk,boolinvertfalse){if(n1){returninvert?1:0;}intlen(1n)-1;inthalf_lenlen1;if(khalf_len1){returninvert?0:1;}elseif(khalf_len){returnfindKthBit(n-1,k,invert);}else{returnfindKthBit(n-1,len-k1,1^invert);// n 2, k 3 - len 3, half_len 1, next_k 1}}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源