1545. Find Kth Bit in Nth Binary String
## 思路
遞迴
Base Case: n=1 or k=1 -- 0
k = mid (==2^M) -- 1
k < mid -- r(n-1,k)
k > mid -- 1^r(n-1,-k) // reverse + invert
## Code
```python
class Solution:
def findKthBit(self, n: int, k: int) -> str:
def recur(n, k):
if k == 1 or n == 1:
return 0
if k & (k-1) == 0:
return 1
if k < (1 << n-1):
return recur(n-1, k)
return 1 ^ recur(n-1, (1 << n) - k)
return str(recur(n, k))
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.12 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729300194.A.AE3.html