本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠。在這一系列刷題文章中，我不僅會講解多種解題思路及其優(yōu)化，還會用多種編程語言實現(xiàn)題解，涉及到通用解法時更將歸納總結(jié)出相應(yīng)的算法模板。

為了方便在PC上運行調(diào)試、分享代碼文件，我還建立了相關(guān)的倉庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結(jié)等，還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。

由于本系列文章的內(nèi)容隨時可能發(fā)生更新變動，歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。

我們構(gòu)建了一個包含?n?行(?索引從 1? 開始?)的表。首先在第一行我們寫上一個?0。接下來的每一行，將前一行中的0替換為01，1替換為10。

• 例如，對于?n = 3?，第?1?行是?0?，第?2?行是?01?，第3行是?0110?。

給定行數(shù)?n?和序數(shù)?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

提示:

• 1 <= n <= 30
• 1 <= k <= 2^n - 1

---

解法 遞歸

首先題目給出一個 $n$ 行的表（索引從 $1$ 開始）。并給出表的構(gòu)造規(guī)則為：第一行僅有一個 $0$，然后接下來的每一行可以由上一行中 $0$ 替換為 $01$，$1$ 替換為 $10$ 來生成。

• 比如當 $n=3$ 時，第 $1$ 行是 $0$，第 $2$ 行是 $01$，第 $3$ 行是 $0110$ 。

現(xiàn)在要求表第 $n$ 行中第 $k$ 個數(shù)字，$1\le k\le 2^n$ 。首先我們可以看到第 $i$ 行中會有 $2^{i?1}$ 個數(shù)字，$1\le i\le n$ ，且其中第 $j$ 個數(shù)字按照構(gòu)造規(guī)則會生第 $i+1$ 行中的第 $2?j?1$ 和 $2?j$ 個數(shù)字，$1\le j\le 2^{i?1}$ 。

即對于第 $i+1$ 行中的第 $x$ 個數(shù)字 ${\text{num}}_1$ ，$1\le x\le 2^i$ ，會被第 $i$ 行中第 $?\frac{x+1}{2}?$ 個數(shù)字 ${\text{num}}_2$ 生成。且滿足規(guī)則：

• 當 ${\text{num}}_2=0$ ?時，${\text{num}}_2$ 會生成 $01$：
  $${\text{num}}_1=\{\begin{array}{ll}0,& x\equiv 1(\mathrm{mod}2)\\ 1,& x\equiv 0(\mathrm{mod}2)\end{array}$$
• 當 $nu{m}_2=1$ 時，${\text{num}}_2$ 會生成 $10$：
  $${\text{num}}_1=\{\begin{array}{ll}1,& x\equiv 1(\mathrm{mod}2)\\ 0,& x\equiv 0(\mathrm{mod}2)\end{array}$$

并且進一步總結(jié)我們可以得到：${\text{num}}_1=(x\&1)\oplus 1\oplus {\text{num}}_2$ ，其中 $\&$ 為「與」運算符， $\oplus$ 為「異或」運算符。那么我們從第 $n$ 不斷往上遞歸求解，并且當在第一行時只有一個數(shù)字，直接返回 $0$ 即可。

class Solution {
public:int kthGrammar(int n, int k) {if (n == 1) return 0;return (k & 1) ^ 1 ^ kthGrammar(n - 1, (k + 1) / 2);}
};

復(fù)雜度分析：

• 時間復(fù)雜度：$O(n)$，其中 $n$ 為題目給定表的行數(shù)，遞歸深度為 $n$。
• 空間復(fù)雜度：$O(n)$，其中 $n$ 為題目給定表的行數(shù)，主要為遞歸的空間開銷。

---

解法2 找規(guī)律 + 遞歸

按照方法一，我們可以嘗試寫表中的前幾行：

• $0$
• $01$
• $0110$
• $01101001$
• $?$

我們可以注意到規(guī)律：每一行的后半部分正好為前半部分的“翻轉(zhuǎn)”——前半部分是 $0$ 后半部分變?yōu)?$1$，前半部分是 $1$，后半部分變?yōu)?$0$。且每一行的前半部分和上一行相同。我們可以通過「數(shù)學(xué)歸納法」來進行證明。

有了這個性質(zhì)，那么我們再次思考原問題：對于查詢某一個行第 $k$ 個數(shù)字，如果 $k$ 在后半部分，那么原問題就可以轉(zhuǎn)化為求解該行前半部分的對應(yīng)位置的“翻轉(zhuǎn)”數(shù)字，又因為該行前半部分與上一行相同，所以又轉(zhuǎn)化為上一行對應(yīng)對應(yīng)的“翻轉(zhuǎn)”數(shù)字。那么按照這樣一直遞歸下去，并在第一行時返回數(shù)字 $0$ 即可。

class Solution {
public:int kthGrammar(int n, int k) {if (k == 1) return 0;// 查詢某一個行第k數(shù)，如果k在后半部分，可轉(zhuǎn)化為求解該行前半部分對應(yīng)位置的翻轉(zhuǎn)數(shù)字if (k > (1 << (n - 2))) return 1 ^ kthGrammar(n - 1, k - (1 << (n - 2)));return kthGrammar(n - 1, k); // 一行前半部分和上一行相同}
};

復(fù)雜度分析：

• 時間復(fù)雜度：$O(n)$，其中 $n$ 為題目給定表的行數(shù)。
• 空間復(fù)雜度：$O(n)$，其中 $n$ 為題目給定表的行數(shù)，主要為遞歸的空間開銷。

---

解法3 找規(guī)律 + 位運算

在「方法二」的基礎(chǔ)上，我們來進行優(yōu)化，本質(zhì)上我們其實只需要求在過程中的“翻轉(zhuǎn)”總次數(shù)，如果“翻轉(zhuǎn)”為偶數(shù)次則原問題求解為 $0$ ，否則為 $1$。

首先我們修改行列的索引從 $0$ 開始，此時原先第 $p$ 行的索引現(xiàn)在為 $p?1$ 行，第 $i$ 行有 $2^i$ 位。那么對于某一行 $i$ 中下標為 $x$ 的數(shù)字，如果 $x<2^{i?1}$ 那么等價于求 $i?1$ 行中下標為 $x$ 的數(shù)字，否則 $x$ 的二進制位的從右往左第 $i$ 位（從第 $0$ 位開始）為 $1$ ，此時需要減去該位（“翻轉(zhuǎn)”一次），然后遞歸求解即可。所以我們可以看到最后“翻轉(zhuǎn)”的總次數(shù)只和初始狀態(tài)下的下標 $x$ 二進制表示中 $1$ 的個數(shù)有關(guān)。

因此原問題中求“翻轉(zhuǎn)”的總次數(shù)，就等價于求 $k?1$ 的二進制表示中 $1$ 的個數(shù)。

class Solution {
public:int kthGrammar(int n, int k) {// return __builtin_popcount(k - 1) & 1;k--;int res = 0;while (k > 0) {k &= k - 1;res ^= 1;}return res;}
};

復(fù)雜度分析：

• 時間復(fù)雜度：$O(\log k)$ ，其中 $k$ 為題目給定查詢的下標。
• 空間復(fù)雜度：$O(1)$ ，僅使用常量變量。