找出第 N 个二进制字符串中的第 K 位 图解题解

这道题到底在问什么

输入

n=3, k=1

输出

"0"

输入

n=4, k=11

输出

"1"

输入

n=2, k=3

输出

"1"

最优解：一步一步想明白

1. 3记牢:中点第 2^(n-1) 位恒为 "1"。k = 中点直接是 1;k 在左半就降到 S(n-1) 同一个 k;k 在右半镜像到第 2^n - k 位、翻转一次再降层。一路折到 S1,翻转奇偶定答案。
2. 4七个格子代表 S3 的第 1 到第 7 位,现在全是问号,因为我们打算一位都不去算,只靠折叠定位。紫色指针停在第 5 位,这就是要找的目标。右边面板记三件事:当前在哪个串、要找第几位、到目前为止翻转了几次的奇偶。
3. 5先标出正中间。S3 长度 7,正中间是第 4 位,它是构造时硬插进去的那个 "1",所以不用算就知道是 1,标成蓝色。这个中点把整串劈成对称的左右两半:左边第 1 到第 3 位,右边第 5 到第 7 位。
4. 6比一比:目标第 5 位在中点第 4 位的右边,落在右半段。把左半段先压灰,我们只盯右半。右半段不是凭空来的,它是左半段 S2 先把每位取反、再整体反过来得到的,所以右半的每一位都能在左半找到对应。
5. 7右半段第 k 位,正好等于第 2^n 减 k 位「取反」后的样子。这里 2 的 3 次方减 5 等于 3,也就是第 5 位的值,等于第 3 位取反。于是把目标镜像到第 3 位,并且记下一次翻转,翻转奇偶从 0 变成 1。
6. 8左半段本身就是 S2,长度 3。问题干净利落地缩小成:在 S2 里找第 3 位,最后再把翻转应用回去。右边那三格已经折叠完成,压灰收起,我们的视线收回到第 1 到第 3 位。
7. 9同样的套路再来一遍。S2 长度 3,正中间是第 2 位,又是插进去的那个 "1",标蓝。它把第 1 到第 3 位再次劈成左右:左边只剩第 1 位,右边只剩第 3 位。
8. 10目标第 3 位在 S2 中点第 2 位的右边,又落在右半段。这一层的右半,是 S1 取反再反转得到的。把左边第 1 位先压灰,只看右边这一格。
9. 11再镜像一次:2 的 2 次方减 3 等于 1,第 3 位等于第 1 位取反。把目标镜像到第 1 位,再记一次翻转,翻转奇偶从 1 翻回 0。注意奇偶现在是偶数,意味着两次取反最终会互相抵消。
10. 12降到 S1 了,它就是单独一个 "0"。要找的第 1 位,值就是 0,标成绿色。这是递归的出口,再也不用往下折了。接下来只剩一件事:把途中记下的翻转应用回去。
11. 13一路上我们记了两次翻转,两次都是取反。偶数次取反相当于没动,所以底部的 0 原样保留。如果是奇数次,才需要把它翻成 1。这里是偶数,答案保持 0。
12. 14把答案填回第 5 位:是 0。整个过程我们只折叠了两次、看了两个中点再落到 S1 出口,从没真的拼出 S3 那七位。注意第 3、6、7 位始终是问号,因为根本没必要去算它们。
13. 15换个目标,这次找 S3 的第 2 位,看看落在左半会怎样。翻转奇偶重新从 0 起算。之前揭示过的中点蓝格还在,因为同一个 S3 它们的值不变,正好省得重标。
14. 16第 2 位在中点第 4 位的左边,落在左半段。左半段最省心:它就是 S2 一字不差的原样,位置不用镜像、也不用记翻转。把右半压灰,直接降层。
15. 17问题缩小成在 S2 里找第 2 位,k 还是 2,翻转奇偶仍然是 0。左半段的好处就在这,什么都不用改,层数减一就行。
16. 18S2 长度 3,中点正是第 2 位,而我们要找的就是第 2 位,直接撞上了中点。中点恒为 "1",标成绿色,答案当场揭晓,连降层都省了。
17. 19这一路全走的左半段,没碰过任何右半,翻转次数是 0,所以中点的 1 原样就是答案。S3 第 2 位是 1。可见踩中点是最快的情形,一步到位。
18. 20最后一个例子,找 S3 的第 1 位,也就是整串开头。第 1 位远在中点第 4 位左边,落在左半段,降到 S2、k 仍是 1。
19. 21到了 S2,中点是第 2 位,第 1 位还在它左边,继续落左半,降到 S1,k 依旧是 1。每一层都往左,翻转次数始终为 0。
20. 22降到 S1,要找第 1 位,值是 0,标绿。一路没经过右半,0 次翻转。
21. 23每个 Sn 的开头都是 S1 的那个 "0",所以任何 Sn 的第 1 位都是 0,这跟样例里 n = 3、k = 1 的答案完全吻合。三个例子走完,折叠法的左、右、命中三种走向都见过了。
22. 24把三次查询的结果放一起回看:第 1 位是 0、第 2 位是 1、第 5 位是 0,都标成绿色,中点第 4 位是蓝色的 1。注意第 3、6、7 位至今还是问号,我们一次都没去算它们,这正是折叠法的精髓:要哪一位就只折哪一位,长串永远不必拼出来。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def dfs(n: int, k: int) -> int:
            if k == 1:
                return 0
            if (k & (k - 1)) == 0:
                return 1
            m = 1 << n
            if k * 2 < m - 1:
                return dfs(n - 1, k)
            return dfs(n - 1, m - k) ^ 1

        return str(dfs(n, k))

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    char findKthBit(int n, int k) {
        function<int(int, int)> dfs = [&](int n, int k) {
            if (k == 1) {
                return 0;
            }
            if ((k & (k - 1)) == 0) {
                return 1;
            }
            int m = 1 << n;
            if (k * 2 < m - 1) {
                return dfs(n - 1, k);
            }
            return dfs(n - 1, m - k) ^ 1;
        };
        return '0' + dfs(n, k);
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public char findKthBit(int n, int k) {
        return (char) ('0' + dfs(n, k));
    }

    private int dfs(int n, int k) {
        if (k == 1) {
            return 0;
        }
        if ((k & (k - 1)) == 0) {
            return 1;
        }
        int m = 1 << n;
        if (k * 2 < m - 1) {
            return dfs(n - 1, k);
        }
        return dfs(n - 1, m - k) ^ 1;
    }
}

复杂度

面试官可能追问