779. 第K個文法符号 : 正難則反，倒推驗證

​

題目描述

這是 LeetCode 上的 779. 第K個文法符号 ，難度為 中等。

Tag : 「DFS」、「遞歸」

我們建構了一個包含 ​

​n​

​​ 行( 索引從 ​

​1​

​​  開始 )的表。首先在第一行我們寫上一個 ​

​0​

​​。接下來的每一行，将前一行中的 ​

​0​

​​ 替換為 ​

​01​

​​，​

​1​

​​ 替換為 ​

​10​

​。

• 例如，對于​

  ​n = 3​

  ​​，第​

  ​1​

  ​​ 行是​

  ​0​

  ​​ ，第​

  ​2​

  ​​ 行是​

  ​01​

  ​​，第​

  ​3​

  ​​ 行是​

  ​0110​

  ​ 。

給定行數 ​

​n​

​​ 和序數 ​

​k​

​​，傳回第 ​

​n​

​​ 行中第 ​

​k​

​​ 個字元。（ ​

​k​

​​ 從索引 ​

​1​

​ 開始）

示例 1:

輸入: n = 1, k = 1

輸出: 0

解釋: 第一行：0      

示例 2:

輸入: n = 2, k = 1

輸出: 0

解釋: 
第一行: 0 
第二行: 01      

示例 3:

輸入: n = 2, k = 2

輸出: 1

解釋:
第一行: 0
第二行: 01      

提示:

遞歸（倒推驗證）

整理一下條件：首行為 ​

​0​

​​，每次用目前行拓展出下一行時，字元數量翻倍（将 ​

​0​

​​ 拓展為 ​

​01​

​​，将 ​

​1​

​​ 拓展為 ​

​10​

​​），且字元種類仍為 ​

​01​

​。

要求我們輸出第 行第 列的字元，我們可以通過「倒推驗證」的方式來求解：假設第 行第 為 ​​

​1​

​​，若能倒推出首行為 ，說明假設成立，傳回 ​​

​1​

​​，否則傳回 ​

​0​

​。

倒推驗證可通過實作遞歸函數 ​

​int dfs(int r, int c, int cur)​

​​ 來做，含義為當第 行第 列的字元為

• 若「目前列為偶數且」或「目前列為奇數且」時，說明目前列所在的組為​​

  ​10​

  ​​，由此可推出其是由上一行的​

  ​1​

  ​​ 拓展而來，結合每次拓展新行字元數量翻倍的條件，可知是由第行的第列的​​

  ​1​

  ​ 拓展而來，遞歸處理；
• 否則，同理，必然是上一行（第行）對應位置的​​

  ​0​

  ​ 拓展而來，遞歸處理。

最終，當倒推到首行時，我們找到了遞歸出口，直接傳回 ​

​cur​

​。

Java 代碼：

class Solution {
    public int kthGrammar(int n, int {
        return dfs(n, k, 1) == 0 ? 1 : 0;
    }
    int dfs(int r, int c, int {
        if (r == 1) return cur;
        if ((c % 2 == 0 && cur == 0) || (c % 2 == 1 && cur == 1)) return dfs(r - 1, (c - 1) / 2 + 1, 1);
        else return dfs(r - 1, (c - 1) / 2 + 1, 0);
    }
}      

TypeScript 代碼：

function kthGrammar(n: number, k: number): number {
    function dfs(r: number, c: number, cur: number): number {
        if (r == 1) return cur
        if ((c % 2 == 0 && cur == 0) || (c % 2 == 1 && cur == 1)) return dfs(r - 1, Math.floor((c - 1) / 2) + 1, 1)
        else return dfs(r - 1, Math.floor((c - 1) / 2) + 1, 0)
    }
    return dfs(n, k, 1) == 0 ? 1 : 0      

Python 代碼：

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        def dfs(r, c, cur):
            if r == 1:
                return cur
            if (c % 2 == 0 and cur == 0) or (c % 2 == 1 and cur == 1):
                return dfs(r - 1, (c - 1) // 2 + 1, 1)
            else:
                return dfs(r - 1, (c - 1) // 2 + 1, 0)
        return 1 if dfs(n, k, 1) == 0 else 0      

• 時間複雜度：
• 空間複雜度：忽略遞歸帶來的額外空間開銷，複雜度為

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.779​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。