【LeetCode】779. 第K个语法符号

题目

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
1
2
3

示例 2:

输入: n = 2, k = 1
输出: 0
解释: 
第一行: 0 
第二行: 01
1
2
3
4
5

示例 3:

输入: n = 2, k = 2
输出: 1
解释:
第一行: 0
第二行: 01
1
2
3
4
5

提示:

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

题解1(TLE)

思路

• 模拟

代码

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        old = [0]
        for _ in range(n-1):
            new = []
            for n in old:
                if n == 1:
                    new.append(1)
                    new.append(0)
                else:
                    new.append(0)
                    new.append(1)
            old = new
        return old[k-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度

• 时间复杂度：$O(2^n)$
• 空间复杂度：$O(2^n)$

题解2

思路

• 因为$0\to 01$以及$1\to 10$，不难发现有以下递归关系式：
  f ( n , k ) = { f ( n − 1 , ⌈ n 2 ⌉ ) k m o d    2 = 0 0 k m o d    2 = 1 ∧ f ( n − 1 , ⌈ n 2 ⌉ ) = 1 1 k m o d    2 = 1 ∧ f ( n − 1 , ⌈ n 2 ⌉ ) = 0 f(n,k)= \left\{
  f(n−1,⌈n2⌉)kmod2=00kmod2=1∧f(n−1,⌈n2⌉)=11kmod2=1∧f(n−1,⌈n2⌉)=0" role="presentation">f(n−1,⌈n2⌉)01kmod2=0kmod2=1∧f(n−1,⌈n2⌉)=1kmod2=1∧f(n−1,⌈n2⌉)=0$$\begin{array}{rlr}& f(n-1,\lceil \frac{n}{2}\rceil )& k\mathrm{mod}2=0\\ & 0& k\mathrm{mod}2=1\wedge f(n-1,\lceil \frac{n}{2}\rceil )=1\\ & 1& k\mathrm{mod}2=1\wedge f(n-1,\lceil \frac{n}{2}\rceil )=0\end{array}$$
  \right. f(n,k)=⎩ ⎨ ⎧​​f(n−1,⌈2n​⌉)01​kmod2=0kmod2=1∧f(n−1,⌈2n​⌉)=1kmod2=1∧f(n−1,⌈2n​⌉)=0​

代码

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1: return 0
        if k % 2 == 1: return self.kthGrammar(n-1, (k+1)//2)
        if k % 2 == 0: return 1 if self.kthGrammar(n-1, (k+1)//2) == 0 else 0
1
2
3
4
5

复杂度

• 时间复杂度：$O(\log k)$
• 空间复杂度：$O(\log k)$