[LeetCode 779]第K个语法符号

题目描述

题目链接：[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 <= $2^{n-1}$

思路分析

1.本质上是二叉树，根节点为0
如果节点值为0，则左孩子为0，右孩子为1
如果节点值为1，则左孩子为1，右孩子为0

2.完全二叉树满足节点对应，父节点为孩子节点/2

代码

class Solution {
public:
    int kthGrammar(int n, int k) {
        function<int(int, int)> f = [&](int n, int k) -> int{
            if(n == 1) return 0; //如果到第一层，返回0
            if(f(n - 1, (k + 1) / 2)){  //如果孩子节点值为1
                if(k % 2) return 1;
                else return 0;
            }else{
                if(k % 2) return 0;
                return 1;
            }
        };

        return f(n, k);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17