leetcode779-第K个语法符号

原题

在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为011替换为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)].

解法

思想

递归分析要查找的字符是上一行的哪个数字得到的,然后根据奇偶性得到目标字符

代码

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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月21日
下一篇 2020年1月22日

相关推荐

  • leetcode198-打家劫舍

    原题 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会…

    算法 2020年5月29日
    050
  • leetcode887-鸡蛋掉落

    原题 你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。 你知道存在楼层 F ,满足 0 &…

    算法 2020年4月11日
    0120
  • leetcode322-零钱兑换

    原题 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 示例 1…

    算法 2020年3月8日
    0150
  • leetcode99-恢复二叉搜索树

    原题 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。 示例 1: 输入: [1,3,null,null,2]    1 …

    算法 2020年3月1日
    070
  • leetcode221-最大正方形

    原题 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 …

    算法 2020年5月8日
    0110
  • leetcode695-岛屿的最大面积

    原题 给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围…

    算法 2020年3月15日
    01220
  • 海量数据-两种方法解决top k问题

    假如提供一百万个数据(甚至更大)的无序数组,如何从中获取最大的k个元素? 最容易想到的是先降序排序然后获取前k个元素,那假设我们用最常用的O(nlogn)级别的排序算法,要获取to…

    2020年4月4日
    0200
  • leetcode141-环形链表

    原题 给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没…

    2019年12月14日
    090
  • leetcode260-只出现一次的数字III

    原题 给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。 示例: 输入: [1,2,1,3,2,5] 输出: [3,5…

    算法 2020年4月28日
    0140
  • leetcode383-赎金信

    原题 https://leetcode.cn/problems/ransom-note/ 解法 记录下字母出现次数 func canConstruct(ransomNote str…

    算法 3天前
    030

发表回复

登录后才能评论