第K个语法符号

第K个语法符号

• 解决方案
  • 方法一：暴力法
  • 方法二：递归（父变体）
  • 方法三：递归（翻转变体）
  • 方法四：二进制计数

解决方案

---

方法一：暴力法

思路和算法

我们完全按照题目描述中的指示处理每一行，而只需要保存最新的那一行。

不幸的是，字符串的长度可能有 10 亿左右，因为每一行的长度都是前一行的两倍，所以这种方法不够高效。

<iframe src="https://leetcode-cn.com/playground/vDuPjtLQ/shared" frameborder="0" width="100%" height="259" name="vDuPjtLQ" style="box-sizing: border-box;"></iframe>

复杂度分析

• 时间复杂度：<math><semantics><annotation encoding="application/x-tex">O(2^N)</annotation></semantics></math>O(2N)，我们解析每一行所需要的时间和其长度有关，共计 <math><semantics><annotation encoding="application/x-tex">2^0 + 2^1 + \cdots + 2^{N-1}</annotation></semantics></math>20+21+⋯+2N−1。

• 空间复杂度：<math><semantics><annotation encoding="application/x-tex">O(2^N)</annotation></semantics></math>O(2N)，最后一行（lastrow）的长度。

---

方法二：递归（父变体）

思路和算法

因为生成每一行只需要前一行的信息，所以我们可以考虑解析前一行的位来输出答案。

<center style="box-sizing: border-box;"> Diagram of digits with relationship to their parent

</center>

来看这个例子，如果我们中间有一行是 "0110"，那么就会生成 "01101001" 作为它的下一行，也就是说第一位 "0" 生成下一行中的第一个 "01"，第二位 "1" 生成下一行中的 "10"，接着 "1" 又生成了 "10"，而最后的 "0" 将会生成最后的 "01"。

<center style="box-sizing: border-box;"> Diagram of digits through repeated function calls

</center>

一般而言，第 K 位的父位应该是第 (K+1) / 2 位。如果父位是 0，那么这一位就是 1 - (K%2)。如果父位是 1，那么这一位就是 K%2。

<iframe src="https://leetcode-cn.com/playground/FTDdMWbt/shared" frameborder="0" width="100%" height="157" name="FTDdMWbt" style="box-sizing: border-box;"></iframe>

复杂度分析

• 时间复杂度：<math><semantics><annotation encoding="application/x-tex">O(N)</annotation></semantics></math>O(N)。找出答案需要 <math><semantics><annotation encoding="application/x-tex">N-1</annotation></semantics></math>N−1 步。

• 空间复杂度：<math><semantics><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1)。

---

方法三：递归（翻转变体）

思路和算法

就像在 方法二 中那样，我们可以尝试按它前面的位来写出这一位。

如果我们写出该序列中的几行，就可以发现：后半部分总是与前半部分相反，也就是说：'0' 变成 '1' 而 '1' 变成 '0'。

我们可以用归纳法来验证这一推断。其关键思想是，如果字符串 <math><semantics><annotation encoding="application/x-tex">X</annotation></semantics></math>X 生成 <math><semantics><annotation encoding="application/x-tex">Y</annotation></semantics></math>Y，那么翻转后的字符串 <math><semantics><annotation encoding="application/x-tex">X'</annotation></semantics></math>X′ 将会生成 <math><semantics><annotation encoding="application/x-tex">Y'</annotation></semantics></math>Y′。

这就引出了下面的算法思想：如果 K 在后半部分，那么我们可以将 K -= (1 << N-2) 设为前半部分，然后翻转得到最终答案。

<iframe src="https://leetcode-cn.com/playground/aJErNcGZ/shared" frameborder="0" width="100%" height="191" name="aJErNcGZ" style="box-sizing: border-box;"></iframe>

复杂度分析

• 时间复杂度：<math><semantics><annotation encoding="application/x-tex">O(N)</annotation></semantics></math>O(N)。找出答案需要 <math><semantics><annotation encoding="application/x-tex">N-1</annotation></semantics></math>N−1 步。

• 空间复杂度：<math><semantics><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1)。

---

方法四：二进制计数

思路和算法

在 方法三 中，每一行的后半部分是前半部分反转后的结果。

当索引 K 写为二进制形式后（从 0 开始索引），后半部分的索引的第一位总是 1。

这意味着，当使用方法三中的算法时，我们翻转最终答案的次数仅仅是 K-1 的二进制表示中的 1 的个数。

<iframe src="https://leetcode-cn.com/playground/B4ZnFpxw/shared" frameborder="0" width="100%" height="140" name="B4ZnFpxw" style="box-sizing: border-box;"></iframe>

复杂度分析

• 时间复杂度：<math><semantics><annotation encoding="application/x-tex">O(\log N)</annotation></semantics></math>O(logN)，即 N 的二进制表示的位数。如果 <math><semantics><annotation encoding="application/x-tex">\log N</annotation></semantics></math>logN 是有界的，那么可以将其视作 <math><semantics><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1)。

• 空间复杂度：<math><semantics><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1)。（在 Python 中，bin(X) 会创造一个长度为 <math><semantics><annotation encoding="application/x-tex">O(\log X)</annotation></semantics></math>O(logX) 的字符串，这是可以避免的。）