刷题打卡，第 33 天
题目一、779. 第K个语法符号
题目一、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
解题思路：
通过题目描述，我们可以知道，整个表中只包含两种数字 0 和 1 ，当某一行某个数字为 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个字符上的数字，返回。 } }
提交结果：
⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~
