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'
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.214.188 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729306849.A.B25.html