1545. Find Kth Bit in Nth Binary String
给两个整数n、k
S_n的二元字串定义为下
S_1 = "0"
S_i = S_i-1 + "1" + reverse(invert(s_i-1)) for i>1
请回传S_n的第k个bit
思路:
我一开始是用暴力解法
后来想了一下规律
S_n的长度是2^n - 1
(1)当 k= 2^n / 2 时 就回传"1"
(2) k < 2^n 就去找 findKthBit(n-1, k )
(3) k > 2^n 因为左右两边存在对称关系，第k个bit会是第2^n - ｋ个bit的invert
所以就回传 findKthBit(n-1, 2^n - k int)
这样就可以得到答案了
golang code :
func findKthBit(n int, k int) byte {
if n == 1 {
return '0'
}
length := 1 << n
half := length / 2
if k < half {
return findKthBit(n-1, k)
} else if k == half {
return '1'
} else {
if findKthBit(n-1, length-k) == '1' {
return '0'
}
return '1'
}
}

大师