LeetCode 1545. Find Kth Bit in Nth Binary String

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

題目大意

初始字串 S_1 = '0'
那之後符合 S_i = S_{i - 1} + "1" + reverse(invert(S_{i - 1}))

reverse 就是整個整個字串反轉、 invert 是邏輯反轉 ('1' 變 '0'， '0' 變 '1')

我們要求 S_n 字串中的第 k 個字符 (index 從 1 開始的第 k 個)

思考

首先思考，這題已經給了遞迴表達式，這應該會對解題有某種幫助
如果設 S_n.length() 為

${\mathcal{l}}_n$ ，則按照遞迴表達我們知道

${\mathcal{l}}_n=2\cdot {\mathcal{l}}_{n-1}+1$

我們可以想通：

1. S_n 的長度必為奇數
2. S_n 的中間是只有一個 (由上可知)，而且不考慮 S_1 的話一定是 '1' (根據遞迴表達)

這樣的情況想到什麼了？沒錯，我們可以使用 binary search 的概念去求出所求

C++:

class Solution
{
public:
    char findKthBit(int n, int k)
    {
        if (n == 1)
            return '0';

        const int len = (1 << n) - 1;
        const int mid = len / 2 + 1;

        if (k == mid)
            return '1';
        if (k < mid)
            return findKthBit(n - 1, k);
        return '1' - findKthBit(n - 1, len - k + 1) + '0';
    }
};

Go:

func findKthBit(n int, k int) byte {
	if n == 1 {
		return '0'
	}

	length := (1 << n) - 1
	mid := length/2 + 1

	if k == mid {
		return '1'
	}
	if k < mid {
		return findKthBit(n-1, k)
	}
	return '1' - findKthBit(n-1, length-k+1) + '0'
}