第K个语法符号

题目链接

第K个语法符号

题目描述

注意

• 第一行只有一个数字0，后面每行的数字都是根据前一行的数字推出
• 数字索引以及行数都是从1开始

解答思路

• 由题可得，某行的数字都是根据前一行的数字推出，最终结果必为0或1，如图所示：

• 观察规律，该行的前半部分与上一行的数字相同，后半部分与上一行的数字相反
• 所以对于第n行的第k个字符，只需要找到其与上一行相应位置的关系，以此类推，直到找到第一行为止

代码

方法一：

class Solution {
    public int kthGrammar(int n, int k) {
        // 向上遍历到了第1行，则返回结果
        if (k == 1) {
            return 0;
        }
        if (k > (1 << n - 2)) {
            // 如果在“蓝色区间”，则与上一行值相反
            return 1 ^ kthGrammar(n - 1, k - (1 << n - 2));
        } else {
            // 如果在“黄色区间”，则与上一行值相同
            return kthGrammar(n - 1, k); 
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

关键点

• 根据题意找到相应规律，使用递归的思想