• 【Day33】每日一题 [779. 第K个语法符号 ]


    在这里插入图片描述

    在这里插入图片描述

    您的点赞收藏以及关注是对作者最大的鼓励喔 ~~

    刷题打卡,第 33 天


    题目一、779. 第K个语法符号

    原题链接: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

    解题思路
    通过题目描述,我们可以知道,整个表中只包含两种数字 01 ,当某一行某个数字为 1 时,在下一行中会变成 10;相对的,当某一行某个数字为 0 时,在下一行中会变成 01

    也就是说,每增加一行,下一行的长度就会是当前行的两倍,我们知道第一行只有一个数字 0,那么接下来就需要求出第n行第k位置的数字是多少。

    根据上述总结,我们知道每一行的长度是按照指数级增长的,那么反过来,当我们某行某个位置的下标除以2,就能获得其上一行对应的数字下标,当然这个规律的前提是下标从0开始,而题目给定的位置下标是从1开始的,所以我们在计算前需要将位置下标k减去1

    我们不断获取上一行对应数字的位置下标,单靠上一步骤是不够的,还需要判断当前位置是第一位还是第二位:(这里的意思是,每个数字在下一行都对应两个数字,我们需要确定当前位置下标是当中的第一个数字还是第二个数字)。这时候我们已经为k减去1,可以运算:

    • 如果当前数字下标与同一行下一个位置下标同时/2相等,说明是两个数中的第一个位置
    • 如果当前数字下标与同一行下一个位置下标同时/2不相等,说明是第二个位置的数

    将获取到的位置放置在数组中,我们从第一行开始遍历:

    • 如果当前数字为0,那么就从01中找数组中记录好的第一或二个数字作为下一行对应数字
      • 如果当前数字为1,那么就从10中找数组中记录好的第一或二个数字作为下一行对应数字

    当我们遍历到题目要求的第n行,自然也就得到了第n行第k位置的数字是多少了。

    提交代码

    class Solution {
        public int kthGrammar(int n, int k) {
            int[] arr = new int[n];          //创建数组,记录每行对应数字所在的位置
            int[] zero = {0,1};              //数字0下一行对应的数字
            int[] one = {1,0};               //数字1下一行对应的数字   
            
            int curr = k-1;                  //记录当前数字的位置,(k-1)表示k索引改为从0开始
            for(int i = n-1;i >=1;--i){      //从第n行遍历到第2行
                if(curr/2 == (curr+1)/2){    //当前位置与同一行下一个位置同时除以2,结果相等
                    arr[i] = 0;              //当行数字的位置在第一位:下标[0]
                }else{                       //结果不相等
                    arr[i] = 1;              //当行数字的位置在第二位:下标[1]
                }
                curr = curr / 2;             //获取上一行对应的数字
            }
            int num = 0;                     //用于记录每一行对应的数字
            for(int i = 1;i < n;++i){        //遍历每一行
    
                if(num == 1){                //当前行为数字1
                    num = one[arr[i]];       //下一行就取‘10’两个数中对应的一个数
                }else{                       //当前行为数字1
                    num = zero[arr[i]];
                }
    
            }
            return num;                      //最终遍历到第n行后,获取到第k个字符上的数字,返回。
    
    
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    提交结果

    在这里插入图片描述


    求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
    来刷题⚽ 记录每日LeetCode✔刷题专栏✔
    您的点赞收藏以及关注是对作者最大的鼓励喔 ~~

    在这里插入图片描述

  • 相关阅读:
    Laravel模型层自动返回数据处理
    ping网络延时大怎么解决?
    Golang web 项目中实现自定义 recovery 中间件
    RabbitMQ延迟消息指南【.NET6+EasyNetQ】
    vue3 - pinia 中的 storeToRefs
    跨平台宏定义
    (纯干货建议收藏)大型字符串模拟-超强超全函数技巧总结
    Vue学习第20天——Vue中常用的ajax请求库(axios与vue-rouserce)
    《算法导论》学习(十五)----二叉搜索树(C语言)
    2024年的云原生架构需要哪些技术栈
  • 原文地址:https://blog.csdn.net/ebb29bbe/article/details/127421501