[路飞]_leetcode-779-第K个语法符号

[题目地址][B站地址]

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

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

例子:

输入: N = 1, K = 1
输出: 0
输入: N = 2, K = 1
输出: 0
输入: N = 2, K = 2
输出: 1
输入: N = 4, K = 5
输出: 1
解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001
复制代码

注意：

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

本题读题之后最简单直接的解题思路就是通过题意的这种性质，求得第 n 行的结果，然后返回第 k 个字符即可。

代码如下：

var kthGrammar = function(n, k) {
  // 前一行的结果 当前行的结果
  let pre = '0',cur = '';
  // 循环获取每一行结果
  for(let i = 2;i<=n;i++){
    cur = '';
    for(let j = 0;j<pre.length;j++){
      if(pre[j]==='0') cur += '01'
      else cur += '10'
    }
    pre = cur;
  }
  // 返回第 n 行第 k 个字符
  return cur.substr(k-1,1)
};
复制代码

但是这样一版代码当测试用例输入第 30 行的时候，就爆栈了，是因为第 30 的结果字符串的长度是 2 的 31 次方，这个时候内存就不够用了

那既然这种直接求解的方法无法解题，我们就考虑，本题需要找到行与行之间字符的关系，通过这种关系推导第 n 行第 k 个字符

这里我们通过如下方式构建了前五行数据

结果图如下：

观察上图可以发现

规律1

下面一行的某个节点的 k 值等于创建它的节点的 k 值乘以 2 或者乘以 2 再减 1

由此，可以得到通过当前节点 k 值，求得父节点 k 值的公式 => Math.ceil(k/2)

规律2

子节点的 k 值如果是奇数，那么它的值和父节点的值是相同的，反之，它的值和父节点的值是相反的

有了以上两个规律的总结，我们思考这样一个过程，从最底层节点向上查找，直到 k = 1,此时，当前节点就是所在行的最最左侧，而所有 k = 1 的节点的值都是 0

那么我们从目标节点，向上回溯，回溯过程中记录 flag 为它和父节点之间的关系

最后回溯到 k = 1 的节点的时候，因为该节点值肯定为 0,则可以根据此时 flag 的状态推导目标节点的值

如果 flag = true，则目标节点和该节点值相同，返回 0,否则返回 1

代码如下：

var kthGrammar = function(n, k) {
  // 初始化 flag 
  let flag = true;
  // 当 k != 1的时候
  while(k>1){
    // 判断当前 k 值奇偶，更新 flag
    if(!(k%2)) flag = !flag;
    // 向上更新 k
    k = Math.ceil(k/2);
  }
  // 根据 flag 结果推导目标字符的值
  if(flag) return 0;
  return 1;
};
复制代码

至此我们就完成了 leetcode-779-第K个语法符号

如有任何问题或建议，欢迎留言讨论！