46. K-th Symbol in Grammar

読了目安約1分

Recursion / LeetCode 779 (Medium) — 0 と 1 が増殖する列の k 番目の記号を再帰で求める。

この章の目次

問題

LeetCode 779. K-th Symbol in Grammar（Medium / カテゴリ: Recursion）

1 行目は 0 です。以降の行は、前の行の 0 を 01 に、1 を 10 に置き換えて作ります。 n 行目の k 番目（1 始まり）の記号を返してください。 n 行目の長さは 2^(n-1) になるため、行を実際に作ると間に合いません。

考え方

ヒント 1

n 行目の k 番目は、n-1 行目の ⌈k/2⌉ 番目の記号から生まれた 2 文字の片方です。親の記号が分かれば、自分の記号も決まります。

ヒント 2

親が 0 なら子は 01、親が 1 なら子は 10。つまり k が奇数なら親と同じ、偶数なら親の反転です。基底は n == 1 のとき 0。

Swift 実装のポイント

⌈k/2⌉ は整数演算で (k + 1) / 2 と書けます。
反転は 1 - parent でも parent ^ 1 でも書けます。
再帰の深さは n - 1（最大 29 程度）なので、スタックの心配はありません。

模範解答

Swift
class Solution {
    func kthGrammar(_ n: Int, _ k: Int) -> Int {
        if n == 1 { return 0 }
        let parent = kthGrammar(n - 1, (k + 1) / 2)
        return k % 2 == 1 ? parent : parent ^ 1
    }
}

計算量: O(n)。