779. 第K个语法符号

1.题目内容

我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

  • 例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。
    给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

示例 1:

1
2
3
输入: n = 1, k = 1
输出: 0
解释: 第一行：0

示例 2:

1
2
3
4
5
输入: n = 2, k = 1
输出: 0
解释: 
第一行: 0 
第二行: 01

示例 3:

1
2
3
4
5
输入: n = 2, k = 2
输出: 1
解释:
第一行: 0
第二行: 01

提示:

  • 1 <= n <= 30
  • 1 <= k <= 2n - 1

2.我的解答

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
class Solution {
    public int kthGrammar(int n, int k) {
        boolean out=false;
        int count=0;
        int kCopy=k;
        while(k/2>0){
            k=k/2;
            count++;
        } 
        while(count>=0){
            int temp=(int)Math.pow(2,count);
            if(kCopy-temp==0){
                for(int i=0;i<count;i++){
                    out=!out;
                }
                break;
            }
            else if(kCopy-temp>0) {
                kCopy-=temp;
                out=!out;
            }
            count--;
        }
        return out?1:0;
    }
}

3.算法思想

根据产生的字符串具有对称性和相同位置相反，使用非递归前推思想，首先确定当前的K所在的幂次，将K折返到上一个位置并取反，如此反复直到折叠到将count为0，若K的位置为2的整数次幂，那么将直接折返到剩余幂次数。设置的初始循环取反变量为false，每次折返进行取反，最后根据取反变量进行输出。

4.学习思路