1545. Find Kth Bit in Nth Binary String

📘 題目敘述

給你兩個正整數 n 和 k，二進位字串 S_n 的形成方式如下：

S_1 = "0"
對於 i > 1：
S_i = S_{i-1} + "1" + reverse(invert(S_{i-1}))

其中 + 表示字串串接，reverse(x) 會回傳 x 反轉後的字串，invert(x) 會把 x 的每個位元翻轉（0 變 1，1 變 0）。

請回傳 S_n 的第 k 個位元。題目保證給定的 n 和 k 都是有效的。

條件限制

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

🧠 解題思路

這題如果真的把 S_n 建出來會很長（長度是 2^n - 1），但其實我們只問第 k 位，所以可以用遞迴利用結構直接找。

S_n 的結構是：

S_{n-1} + "1" + reverse(invert(S_{n-1}))

因此 S_n 的中間那個 "1" 的位置一定是：

m = 2^(n-1)

我分三種情況看 k 落在哪：

k == m
代表剛好在中間，那答案一定是 '1'
k < m
代表落在左半邊，左半邊就是 S_{n-1}
所以答案等同於 findKthBit(n-1, k)
k > m
代表落在右半邊，右半邊是 reverse(invert(S_{n-1}))
右半邊的位置 k 對應回 S_{n-1} 的位置會是鏡射：

k' = 2*m - k

先去 S_{n-1} 找 k' 的值，得到 b，但右半邊還有 invert，所以要再翻轉一次：
- b == '0' → 回傳 '1'
- b == '1' → 回傳 '0'

遞迴一直縮小 n，最後 n == 1 時 S_1 只有 "0"，直接回傳 '0'。

所有變數

m：S_n 的中間位置 2^(n-1)，也是中間那個 '1' 的位置
b：當 k 在右半邊時，用來接住在 S_{n-1} 對應位置查到的位元，之後再翻轉回傳

🪜 主要流程步驟

1. 基底：n == 1 時直接回傳 '0'

因為 S_1 = "0"，不管 k 是多少（題目保證有效），答案就是 '0'。

2. 計算中間位置 m = 2^(n-1)

S_n 長度是 2^n - 1，中間那個 '1' 的位置固定是 2^(n-1)。

3. k == m：直接回傳 '1'

落在中間就不用再遞迴了。

4. k < m：到左半邊的 S_{n-1} 繼續找

左半邊完全就是 S_{n-1}，所以直接遞迴：

findKthBit(n-1, k)

5. k > m：映射回 S_{n-1} 再翻轉

右半邊是 reverse(invert(S_{n-1}))，所以先用鏡射位置：

k' = 2*m - k

去找 S_{n-1} 的第 k' 位得到 b，最後因為有 invert，要把 b 翻轉後回傳。

⏱️ 複雜度

時間複雜度：O(n)
每次遞迴 n 減 1，最多跑到 n == 1。
空間複雜度：O(n)
遞迴呼叫深度最多 n。

💻 程式碼實作

class Solution {
public:
    char findKthBit(int n, int k) {
        int m = pow(2, n - 1);
        if (n == 1) {
            return '0';
        }
        if (k == m) {
            return '1';
        } else if (k < m) {
            return findKthBit(n - 1, k);
        } else {
            char b = findKthBit(n - 1, 2 * m - k);
            return (b == '0') ? '1' : '0';
        }
    }
};

🔗 題目連結

https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/