题目描述
这是 力扣上的 779. 第K个语法符号，难度为 中等。
题目分析
题目汇总给出一个表格，这个表格比较特殊，行索引111开始，每一行的字符也是从索引111开始，且表格的每一行中的数据是按照特殊方式分裂开来的，例如上一行中的000会分裂成下一行的010101，上一行中的111会分裂成下一行中的 101010
题目要我们迅速的找到第 nn n行的 第 kk k个字符是0 00还是1 11
思考：
那么我们来稍微简单的写几行数据来模拟一下，看看有没有什么规律可循
| 0 |
| 01 |
| 0110 |
| 01101001 |
仔细看例子，我们可以看到第 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 行，占用栈空间
今天就到这里，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
