【LeetCode每日一题】【递归/位运算】2022-10-20 779. 第K个语法符号 Java实现

---

题目链接

https://leetcode.cn/problems/k-th-symbol-in-grammar/

题目

题目大意

下一行是由之前一行进行扩展，上一行中的数字0，在下一行中扩展为01，上一行中的数字1，在一行中扩展为10。所以每一行的01序列都是在上一行的基础上扩展而来的，长度是前一行的两倍

我的思路

本来的想法是，按照题目的意思，把第n行的序列模拟出来，然后用charAt获取第k个位置上的元素，看到n和k的范围，觉得这种方法应该不可行

根据提示，可以使用递归

Try to represent the current (N, K) in terms of some (N-1, prevK). What is prevK ?

举个例子，比如n=5，k=15，也就是说，要求第5行的第15位上的数字是什么，借着上面的提示，可以想到：
第5行的第15个数字一定是第4行的第8个数字扩展来的
第4行的第8个数字一定是第3行的第4个数字扩展来的
第3行的第4个数字一定是第2行的第2个数字扩展来的
第2行的第2个数字一定是第1行的第1个数字扩展来的
第1行只有一个数字0，返回0
根据第1行的返回结果0，第2行的第2个数字（偶数位置），则是0扩展以后的第2位：1，返回1
根据第2行的返回结果1，第3行的第4个数字（偶数位置），则是1扩展以后的第2位：0，返回0
根据第3行的返回结果0，第4行的第8个数字（偶数位置），则是0扩展以后的第2位：1，返回1
根据第4行的返回结果1，第5行的第15个数字（奇数位置），则是1扩展以后的第1位：1，返回1
算法结束

class Solution {
    public int kthGrammar(int n, int k) {
        if (n == 1) {
            return 0;
        }
        int res;
        //当前k是奇数
        if ((k & 1) != 0) {
            res = kthGrammar(n - 1, (k + 1) / 2);
            if (res == 0) {
                return 0;
            } else {
                return 1;
            }
        } else {
            res = kthGrammar(n - 1, k / 2);
            if (res == 0) {
                return 1;
            } else {
                return 0;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

官方思路

方案一 递归

首先题目给出一个n行的表（索引从1开始）。并给出表的构造规则为：第一行仅有一个0，然后接下来的每一行可以由上一行中0替换为01，1替换10生成。

现要求表第n行中的第k个数字，$1\le k\le 2^{n-1}$。

首先，第i行中会有$2^{i-1}$个数字，$1\le i\le n$，且其中第j个数字按照构造规则会生成第i+1行中的第 $2\ast j-1$ 和 $2\ast j$ 个数字，$1\le j\le 2^{i-1}$。

即对于第 $i+1$ 行中的第 $x$ 个数字$nu{m}_1$，$1\le x\le 2^i$ ，会被第 $i$ 行中第 $\lfloor \frac{x+1}{2}\rfloor$ 个数字 $nu{m}_2$ 生成。且满足规则：

• 当 $nu{m}_2=0$，会生成01
  • x为奇数时，下一行结果是0
  • x为偶数时，下一行结果是1

n u m 1 = { 0 ， x ≡ 1 ( m o d    2 ) 1 ， x ≡ 0 ( m o d    2 ) num_1 =

num1​={0，x≡1(mod2)1，x≡0(mod2)​

• 当 $nu{m}_2=1$，会生成10
  • x为奇数时，下一行结果是1
  • x为偶数时，下一行结果是0

n u m 1 = { 1 ， x ≡ 1 ( m o d    2 ) 0 ， x ≡ 0 ( m o d    2 ) num_1 =

num1​={1，x≡1(mod2)0，x≡0(mod2)​

为啥我觉得他这个文字写的让人费解…

通俗点来说，就是，第i+1行的第x个数字num1，是由第i行的 第 $\lfloor \frac{x+1}{2}\rfloor$ 个数字生成的num2生成的

所以，生成num1的两个因素：num2，以及 x 这个位置是奇数还是偶数

如果num2=0，并且，x是偶数，那么，0派生成01，num1=1；如果x是奇数，那么，num1=0。

如果num2=1，并且，x是偶数，那么，1派生成10，num1=0；如果x是奇数，那么，num1=1。

也就是说，如果x是奇数，那么num2是啥，num1就是啥；如果x是偶数，那么num2是1，num1就是0；num1是0，num2就是1。

class Solution {
    public int kthGrammar(int n, int k) {
        if (n == 1) {
            return 0;
        }
        return (k & 1) ^ 1 ^ kthGrammar(n-1,(k+1)/2);
    }
}
1
2
3
4
5
6
7
8

方案二 找规律 + 递归

• 0
• 01
• 0110
• 01101001
• 0110100110010110
• …

可以注意到，每一行的后半部分正好为前半部分的“翻转”——前半部分是0，后半部分是1，前半部分是1，后半部分是0。且每一行的前半部分于上一行相同。我们可以通过数学归纳法进行证明

有了这个性质，再思考原问题：对于查询某一行第k个数字，如果k在后半部分，那么原问题转化为求解该前半部分的对应位置的“翻转”数字，又因为该行前半部分与上一行相同，所以又转化为上一行对应的数字的“翻转”数字。一直这样递归下去，并在第一行时返回数字0即可。

class Solution {
    public int kthGrammar(int n, int k) {
        if (n == 1 || k == 1) {
            return 0;
        }
        if (k > (1 << (n - 2))) {
            return 1 ^ kthGrammar(n - 1, k - (1 << (n - 2)));
        }
        return kthGrammar(n - 1, k);
    }
}
1
2
3
4
5
6
7
8
9
10
11

方案三 找规律 + 位运算（不太理解，欢迎讨论）

在方法二的基础上，进行优化，本质上其实只需要求在过程中的“翻转”总次数，如果“翻转”为偶数次，那么原问题求解为0，否则为1。

如果“翻转”为偶数次，那么原问题求解为0，否则为1。
什么意思

首先，修改行的索引从0开始，此时，原先第p行的索引现在为p-1行，第i行有$2^i$次方位。那么对于某一行i中下标x的数字，如果$x<2^{i-1}$，那么等价于求$i-1$中下标为x的数字，否则，x的二进制位的从右往左第i+1位为1，此时需要减去该位（“翻转”一次），然后递归求解即可。

x的二进制位的从右往左第i+1位为1 看不太懂