有規律字串中的第k個符號 K-th Symbol in Grammar Leetcode #779

Nik null on Unsplash

題目敘述

這題的題目一個規律變化的二進位字串，問我們第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 <= 30
• 1 <= 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