原题
在第一行我们写上一个 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
注意:
N的范围[1, 30].K的范围[1, 2^(N-1)].
解法
思想
递归分析要查找的字符是上一行的哪个数字得到的，然后根据奇偶性得到目标字符
代码
class Solution {
public int kthGrammar(int N, int K) {
if(N==0) return 0;
if(K%2 == 1){
if(kthGrammar(N-1,(K+1)/2)==0) return 0;
else return 1;
}else{
if(kthGrammar(N-1,(K+1)/2)==0) return 1;
else return 0;
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode779-%e7%ac%ack%e4%b8%aa%e8%af%ad%e6%b3%95%e7%ac%a6%e5%8f%b7/
相关推荐
-
leetcode682-棒球比赛
原题 你现在是棒球比赛记录员。给定一个字符串列表，每个字符串可以是以下四种类型之一：1. 整数（一轮的得分）：直接表示您在本轮中获得的积分数。2. "+"（一轮的得...
-
leetcode66-加一
原题 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以...
-
leetcode1028-从先序遍历还原二叉树
原题 我们从二叉树的根节点 root 开始进行深度优先搜索。 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，...
-
leetcode210-课程表II
原题 现在你总共有 n 门课需要选，记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0...
-
leetcode133-克隆图
原题 给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。 示例: 输入: {"id":...
-
leetcode125-验证回文串
原题 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明： 本题中，我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a ...
-
leetcode62-不同路径
原题 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi...
-
leetcode42-接雨水
原题 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高...
-
leetcode350-两个数组的交集II
原题 给定两个数组，编写一个函数来计算它们的交集。 输入： nums1 = [1,2,2,1], nums2 = [2,2] 输出： [2,2] 示例2： 输入： nums1 = ...
-
leetcode445-两数相加II
原题 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外，这两个数字都...
