はじめに
LeetCodeの 779. K-th Symbol in Grammarに関して、公式サイトにSolutionがなく、これについて解説している記事もなかったのと、解法が面白かったので書きます。
問題
公式サイトから問題のコピペ
We build a table of n rows (1-indexed). We start by writing 0 in the 1st row. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.
For example, for n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.
Given two integer n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.
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
日本語での要約
初期値0で、0が01、1が10に置換されていく数列を考えます。下記がrow5まで求めたものです。
row1 : 0
row2 : 01
row3 : 0110
row4 : 01101001
row5 : 0110100110010110
今回の問題では、nとkが与えられ、row{n}の左からk番目の数字を返します。回答例はコピペのExampleを見てもらえればわかると思います。
考察
シンプルな解法
まず純粋に上のようにrow nに至るまで数列を生成していく方法を考えます。その時の時間計算量は $O(2^n)$ です。制約条件はn<=30であることを考えるとこのアルゴリズムでは難しそうです。
再帰を用いた解法
分析
row5とrow4を比べます。
- row4 : 01101001
- row5 : 0110100110010110
row5を前半と後半で区切ると、
- row4 : 01101001
- row5 : 01101001 10010110
row5の前半がrow4と一致しており、row5の後半がrow4を反転したものと一致しています。
row4とrow3に関しても、同じことが言えます。
- row3 : 0110
- row4 : 0110 1001
今回はこれを利用します。
定式化
これらの事象を定式化すると、
row{n}のk番目の数字は、
- $1<=k<=2^{n-2}$ の時、row{n-1}のk番目の数字と等しい
- $2^{n-2}<k<=2^{n-1}$ の時、row{n-1}のk番目の数字の反転と等しい
と言うことができます。これはまさしく再帰で解くことができます。これをコードに落とし込むことができれば解けます。時間計算量は$ O(n) $です。
解法コード
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
def calc(n,k):
if n==1:return 0
mid=2**(n-2)
if k>mid: return 1-calc(n-1,k-mid)
else: return calc(n-1,k)
return calc(n,k)
おわりに
LeetCodeに関する日本語の記事はまだまだ少ないのでこれから増やしていきたいですね。