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

解题

方法一:递归

参考链接

如果节点为左子节点,那么和父节点一样,如何节点为右子节点,那么和父节点值相反。

比如n=3,k=3的情况,此时 (3&1)=1,!(3&1)=0,0异或x=x,因此k为奇数的时候,就和父节点的值相等,因此递归去算父节点的值就行了。

class Solution {
public:
    int kthGrammar(int n, int k) {
        if(n==1) return 0;
        return !(k&1)^kthGrammar(n-1,(k+1)/2);
    }
};
相关文章
|
6月前
编译原理(1)----LL(1)文法(首符号集,后跟符号集,选择符号集)
编译原理(1)----LL(1)文法(首符号集,后跟符号集,选择符号集)
90 5
|
5月前
|
C语言
C语言——字符串大小写互换
C语言——字符串大小写互换
88 0
|
6月前
|
编译器 C语言
【C语言】字母转换大小写的三种方法
【C语言】字母转换大小写的三种方法
250 0
|
6月前
|
C语言
C语言刷题:整数加逗号、删除公共字符、求最小公倍数和将字符串倒置
C语言刷题:整数加逗号、删除公共字符、求最小公倍数和将字符串倒置
74 0
|
机器学习/深度学习 Cloud Native Go
779. 第K个语法符号:简单模拟
这是 力扣上的 779. 第K个语法符号,难度为 中等。
【C语言】大小写字母判断、转化函数总结
以下函数的头文件都是 #include <ctype.h>
复习C部分:1.什么是常量 2.初时字符串 3.初识转义字符 4.注释 5.初识选择语句 6.初识循环语句 7.初识函数和数组 8.初识操作符 9.初始操作符2
复习C部分:1.什么是常量 2.初时字符串 3.初识转义字符 4.注释 5.初识选择语句 6.初识循环语句 7.初识函数和数组 8.初识操作符 9.初始操作符2
108 0
复习C部分:1.什么是常量 2.初时字符串 3.初识转义字符 4.注释 5.初识选择语句 6.初识循环语句 7.初识函数和数组 8.初识操作符 9.初始操作符2
|
索引
【每日一题Day2】LC779.第k个语法符号
我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为01,1替换为10。
58 0
|
索引
【Day33】每日一题 [779. 第K个语法符号 ]
学习每日一题 [779. 第K个语法符号 ]。
84 0
【Day33】每日一题 [779. 第K个语法符号 ]
|
索引
LeetCode每日一题——779. 第K个语法符号
我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为01,1替换为10。
100 0