【LeetCode】779、第k个语法符号

21、K-th Symbol in Grammar第k个语法符号

难度：中等

题目描述

• 英文：

  On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0with 01, and each occurrence of 1 with 10.

  Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

• 中文：

  在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

  给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）

• 示例

  Example:

  Input: N = 1, K = 1
  Output: 0
  
  Input: N = 2, K = 1
  Output: 0
  
  Input: N = 2, K = 2
  Output: 1
  
  Input: N = 4, K = 5
  Output: 1
  
  Explanation:
  row 1: 0
  row 2: 01
  row 3: 0110
  row 4: 01101001

• 注意

  1. N 的范围 [1, 30].
  2. K 的范围 [1, 2^(N-1)].

解题思路

思路一

递归思路。

整个结构可以看做是一棵二叉树。

    0
   / \
  0   1
 /\   /\
0  1 1  0

当一个节点是0的时候，两个子节点分别为0和1，当节点是1的时候，两个子节点分别为1和0。通过把K除以2，可以知道K的位置是左节点还是右节点。如果K是偶数，那么当前节点为右子节点，父节点是$N-1$行的第$K/2$个节点，如果K为奇数的话，则当前节点为左子节点。父节点是$N-1$行的第$(K+1)/2$个节点。

当前节点依赖于父节点，所以递归向前查找父节点，直至第一行结束。

代码提交

C++，用时4ms，内存8.1M

class Solution {
public:
    int kthGrammar(int N, int K) {
        if (N==0)
            return 0;
        if (K%2 == 0) {
            return kthGrammar(N-1, K/2)==0 ? 1:0;
        }
        else {
            return kthGrammar(N-1, (K+1)/2)==0 ? 0:1;
        }
    }
};

进行Recursion探索时完成的，其他解法后续补充。