[数据结构与算法]leetcod779. 第K个语法符号

找规律

首先写出前几个来

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001

你会发现，

• 前面一半的数字和上一行相等
• 之后跟上一个1
• 后面一半的数字，等于从第一行开始加到倒数第三行，也就是上上行

很神奇，现在先不考虑，规律是怎么来的，但是可以直接使用这个规律进行做题。

几个重要的结论

$2^n?1表示数字的总个数$
$2^{(n?1)}表示本层的数字的个数$
$2^{(n?2)}表示上一层数字的个数,也就是本层的前一半$
$2^{(n?1)}?1表示上面数字层数之和$

思路

1. 如果小于等于前一半，直接找上一层对应的为止就行了。也就是$k<2^{(n?2)}$的时候直接返回$pow(n?1,k)$
2. 如果是中间的那一个直接就是1。也就是说$2^{(n?2)}+1==k$的时候直接返回1
3. 如果大于前一半: 需要映射到第几层的第几个呢？

此时的k代表的是数字的个数

首先减去前一部分$k?2^{(n?2)}?1$

其次计算在第几层，需要所在的层数累计个数大于等于k,也就是说

$2^x?1>=k$
$2^x>=k+1$
$x>=log(k+1)$ 需要上取整,那么可以写成$(int)logk+1$

层数是$x$, 那么是第几个数字呢？
$k?(2^{(x?1)}?1)$
也就是减去上面的全部数字的个数，就是这一层数字的个数

代码

• 需要注意log是以10为底的，需要使用换底公式改成以2为底的。
• 另外上面规律是从第二行开始的，第一行直接返回。

class Solution {
public:
    int kthGrammar(int n, int k) {

        if (n == 1) return 0;
        // 下面的规律是从第二行开始的
        int pre_cnt = pow(2, n - 2) + 1;
        if (k == pre_cnt) return 1;
        if (k < pre_cnt) return kthGrammar(n - 1, k);
        // k > pre_cnt
        k -= pre_cnt; 
        // 换底公式求log(2, k);          
        int x = (int)(log(k) / log(2)) + 1;
        return  kthGrammar(x, k - pow(2, x - 1) + 1);
    }
};

• java代码

package leetcode.everyDay.October;

/**
 * @author: Zekun Fu
 * @date: 2022/10/20 9:55
 * @Description: 第k个语法符号
 */
public class leet779 {
    public static int kthGrammar(int n, int k) {
        if (n == 1) return 0;
        // 下面的规律是从第二行开始的
        int pre_cnt = (int)Math.pow(2, n - 2);
        if (k == pre_cnt + 1) return 1;
        if (k <= pre_cnt) return kthGrammar(n - 1, k);
        k -= pre_cnt;
        int x = (int)(Math.log(k)/ Math.log(2))+ 1;
        return kthGrammar(x, k - (int)Math.pow(2, x - 1) + 1);
    }
    public static void main(String[] args) {
        System.out.println((Math.log(4)) / Math.log(2));
        System.out.println(kthGrammar(4, 8));
    }
}