第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"。
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) 的字符串，这是可以避免的。）
网友评论