解題說明
Find Kth Bit in Nth Binary String
題目描述： 定義字串序列 S1 = "0"，Si = Si-1 + "1" + reverse(invert(Si-1))。給定 n 和 k，回傳 Sn 中第 k 個位元（1-indexed）。
解題思路： 觀察 Si 的結構：長度為 2^i - 1，中間位置為 "1"。可以用遞迴方式判斷第 k 位在哪個部分：(1) 如果 k 在前半部分，等價於查詢 Si-1 的第 k 位；(2) 如果 k 恰好在中間，答案為 '1'；(3) 如果 k 在後半部分，對應 Si-1 中的某個位置並取反。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每次遞迴使 n 減少 1，最多遞迴 n 層
空間複雜度：O(n) — 遞迴堆疊深度為 n
虛擬碼
1. Base case: if n == 1, return '0'
2. Calculate length = 2^n - 1, mid = length / 2 + 1
3. If k == mid: return '1' (the middle bit is always '1')
4. If k < mid: return findKthBit(n-1, k) (first half is S_{n-1})
5. If k > mid: return inverted findKthBit(n-1, length - k + 1) (second half is reverse(invert(S_{n-1})))其他解法
方法二：迭代模擬 不用遞迴，而是用迴圈模擬。用一個 flip 計數器記錄總共需要反轉幾次，每次判斷 k 落在前半或後半。最後根據 flip 的奇偶性決定是否取反。
方法三：實際建構字串 從 S1 開始，逐步建構到 Sn，然後直接取第 k 位。時間和空間複雜度均為 O(2^n)，當 n 較大時不實際。
延伸思考
- 如果要求 Sn 中 '1' 的總數量，能否不建構字串就算出來？
- 如果遞迴規則改為 Si = Si-1 + "0" + reverse(Si-1)（不取反），第 k 位的查詢邏輯需要如何修改？
- 這個遞迴結構和分形（fractal）有什麼關係？