Leetcode 779. 第K个语法符号

我们构建了一个包含 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

提示:

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

我的想法：
1.最开始是想把第n行的数字都列出来。
搞一个 s = “0” ，两层循环

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        s = "0"
        for i in range(n-1): # 遍历n次
            slength = len(s) # 取slength为s的长度
            j = 0 # j用来遍历当前的s
            tmplist = list() # 搞一个数组，每当i加1，都为空
            while j < slength: # 循环遍历
                if s[j] == "0": # 当s[i]为0的时候，数组续上 01
                    tmplist.append("01")
                else: # 否则，数组续上 10
                    tmplist.append("10")
                j += 1
            s = "".join(tmplist)
        return int(s[k-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

直接干超时了。

超出时间限制
15 / 55 个通过的测试用例
最后执行的输入
n = 30 k = 434991989

又将数组换成字符串，照样超时。

2.然后寻思了下，不能直接两个循环了，那就找规律呗

1. 0
2. 0 1
3. 0 1 1 0
4. 0 1 1 0 1 0 0 1
5. 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
6. 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

然后发现，第六行的前半部分正好是第五行的全部内容，第五行的前半部分正好是第四行的全部内容…

1. 0
2. 0 1
3. 0 1 1 0
4. 0 1 1 0 1 0 0 1
5. 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
6. 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

然后发现，第六行的后半部分，是第五行的后半部分加第五行的前半部分，以此类推…

1. 0
2. 0 1
3. 0 1 1 0
4. 0 1 1 0 1 0 0 1
5. 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
6. 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

研究半天写了个代码，又超时。

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:  
        if n == 1:
            return 0
        elif n >= 2:
            s = "01"
            f0 = "0"
            f1 = "1"
            for i in range(n-2):
                s,f1,f0 = s + f1 + f0,f1 + f0,s
            return int(s[k-1])
1
2
3
4
5
6
7
8
9
10
11

但是可以按着那个思考，先看k在第六行的31位：

1. 0
2. 0 1
3. 0 1 1 0
4. 0 1 1 0 1 0 0 1
5. 0 1 1 0 1 0 0 1 - 1 0 0 1 0 1 1 0
6. 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 - 0 1 0 1 1 0 - 0 1 1 0 1 0 0 1

第六行这个第31位的0，实际上是第五行第7位的0.第五行第7位的0也可以看做是第四行第7位的0。第四行第7位的0可以看作是第三行第1位的0。第三行第1位的0可以看作是第二行第1位的0，又可以看作是第一行第1位的0。

再看k在第六行的第17位：

1. 0
2. 0 1
3. 0 1 - 1 - 0
4. 0 1 1 0- 1 0 - 0 1
5. 0 1 1 0 1 0 0 1 - 1 0 0 1 - 0 1 1 0
6. 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 - 1 0 0 1 0 1 1 0 - 0 1 1 0 1 0 0 1

第六行这个第17位的1，实际上是第五行第9位的1，也可以看做是第四行第5位的1，也可以看作是第三行第3位的1，也可以看作是第二行第2位的1。

也就是说，如果k在当前行的前半部分位置，也就在上一行的同样位置。
如果k在当前行的后半位置，分情况讨论：
如果k在当前行的3/4之后，对应前一行的前半部分；
如果k在当前行的1/2之后、3/4之前，对应前一行的后半部分

具体写出来，有点傻，但是ac了。

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        n = n-1
        while n >= 2:
            if k > 2 ** (n-2) * 3:
                k = 2 ** (n-2) - 2 ** n + k
            elif k > 2 ** (n-1):
                k = k - 2 **(n-1) + 2**(n-2)
            n -= 1
        if k == 1 :
            return 0 
        if k == 2:
            return 1
1
2
3
4
5
6
7
8
9
10
11
12
13

可以看看这几个题解：
https://leetcode.cn/problems/k-th-symbol-in-grammar/solutions/1906763/-by-muse-77-zw7u/
https://leetcode.cn/problems/k-th-symbol-in-grammar/solutions/1903508/di-kge-yu-fa-fu-hao-by-leetcode-solution-zgwd/
https://leetcode.cn/problems/k-th-symbol-in-grammar/solutions/1906532/by-ac_oier-fp2f/
https://leetcode.cn/problems/k-th-symbol-in-grammar/solutions/1906933/by-eternity-to-xh8p/
https://leetcode.cn/problems/k-th-symbol-in-grammar/solutions/1906354/pythonjavatypescriptgo-ji-yi-hua-di-gui-043m3/