779. 第K个语法符号：简单模拟

题目描述

这是 力扣上的 779. 第K个语法符号，难度为 中等。

题目分析

题目汇总给出一个表格，这个表格比较特殊，行索引111开始，每一行的字符也是从索引111开始，且表格的每一行中的数据是按照特殊方式分裂开来的，例如上一行中的000会分裂成下一行的010101，上一行中的111会分裂成下一行中的 101010

题目要我们迅速的找到第 nn n行的 第 kk k个字符是0 00还是1 11

思考：

那么我们来稍微简单的写几行数据来模拟一下，看看有没有什么规律可循

仔细看例子，我们可以看到第 ii i行的字符个数是 2i−12^{i-1}2i−1，并且仔细的我们还可以发现，第iii行的字符数，总是i+1i+1i+1行的一半，且字符还有很有趣的关系

那就是第 i 行的全部字符是第i+1i+1i+1行的前半部分，i+1i+1i+1 行的后半部分也很有意思，后半部分是前半部分的翻转

此处的翻转意思是：

前半部分的 0 对应着后半部分的 1，前半部分的 1 ，对应这后半部分的 0

那么，看到这里，对于解决这道题是不是有了一些思路呢？

我们就可以将题目中要求我们找到第n行的第k个字符第 n 行的第 k 个字符第n行的第k个字符，转换成了 第n−1行的第k个字符第 n-1 行的第 k 个字符第n−1行的第k个字符（如果这个k 是大于当前行字符的一半，那么就要转换成前半段的字符），一直递归到n==1n == 1n==1的情况我们就可以找到答案了，那么我们就有这样的逻辑：

如果n是等于1n 是等于 1n是等于1的，咱们就可以直接返回0 00

如果n是大于1n 是大于 1 n是大于1的，且满足条件k>1<<(n−2) k > 1<<(n-2)k>1<<(n−2)，满足这个条件，说明找当前行的第 k 个字符，已经是在当前行的后半段了，因此，我们就继续往上找，找上一行的k−1<<(n−2)k - 1<<(n-2)k−1<<(n−2)个字符的翻转

如果n是大于1n 是大于 1 n是大于1的，且不满足条件k>1<<(n−2)k > 1<<(n-2)k>1<<(n−2)，说明当前行要找的第 k 个字符在前半段，那么直接就找上一行的第kkk个字符即可，一直找到n等于1n 等于 1n等于1的时候

对于以上逻辑，已经非常清晰了

接下来，咱们就可以来实现编码了，咱们这次使用 golang 的方式来进行实现

Golang 的实现方式：

• 递归处理即可，每一次都判断当前行的第 k 个字符是否大于当前行的一半，若是，则找上一行对应位置的翻转

• 若不是则找上一行的 第 k 个位置的字符

func kthGrammar(n, k int) int {
    if n == 1 {
        return 0
    }
    // 判断 当前行的第 k 个字符，是否大于上一行的总个数
    // 表示 k 的位置是当前行的后半部分了，那么就需要找到 当前行的第 k 个字符的位置在前半部分的对应翻转位置
    if k > 1<<(n-2) {
        return 1 ^ kthGrammar(n-1, k- 1<<(n-2))
    }
    // 若 k 是当前行的前半部分，那么不需要翻转
    return kthGrammar(n-1, k)
}

这种实现方式，咱们的时间复杂度为 O(n)，此处的 n 是表示表格的 n 行，空间复杂度也是 O(n)，我们使用的是递归的方式，需要递归 n 行，占用栈空间

今天就到这里，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~