題目敘述
這題的題目一個規律變化的二進位字串，問我們第N排，第K個bit是多少?
變化的規律: 上一排的0到下一排展開成01，上一排的1到下一排展開成10
第一排初始化是0第二排是01
第三排是0110
第四排是01101001
...其餘依此類推
測試範例:
Example 1:
Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0
Example 2:
Input: n = 2, k = 1
Output: 0
Explanation:
row 1: 0
row 2: 01
Example 3:
Input: n = 2, k = 2
Output: 1
Explanation:
row 1: 0
row 2: 01
約束條件
Constraints:
1 <= n <= 301 <= k <= 2n - 1
演算法
可以觀察生成規律
奇數編號都會和上一排的父節點(N-1, (K+1)/2)的相同，
偶數編號都會和上一排的父節點(N-1, (K+1)/2)的相反，
由這個生成規律，寫出遞迴關係式，藉由遞迴解找出答案。
程式碼
class Solution:
def kthGrammar(self, N: int, K: int) -> int:
if N == 1:
# Base case:
return 0
else:
# General case:
if K % 2 == 0:
# even index of current level is opposite of parent level's [(K+1)//2]
return 1 - self.kthGrammar(N-1, (K+1)//2)
else:
# odd index of current level is the same as parent level's [(K+1)//2]
return self.kthGrammar(N-1, (K+1)//2)
複雜度分析
時間複雜度:
O( log k ) 最多往上回溯O(log k)次可以找到答案。
空間複雜度:
O( log k ) 遞迴recursion call stack 最大深度。
關鍵知識點
觀察字串生成規律，找出遞迴關係式。
Reference:
[1] Python/JS/Java/Go/C++ by math [w/ Comment] - K-th Symbol in Grammar - LeetCode
