LC-779 语法中的第k个字符

问题：

按这个规则生成一系列符号串，输出第N行的第K个符号。

规则为：将前一行的0转换为01，将前一行的1转换为10。第一行为0

所以前4行及例子如下图：

思路：

可以观察前4行，得出一个规律，每一行的前半段是上一行的字符串，后半段是上一行字符串的取反后的字符串。

以第4行为例子，前四个字符是跟第三行一样的，而后4个字符是第三行的区分。

所以我们一开始的思路，肯定是想递归地创建某一行的字符串，然后输出第k个字符。

但是因为这里N的大小最大到30，所以K的最大取值为2的30次方。很容易就超过题目的内存限制。

所以我们使用一种递归的思路，判断K的位置是属于该行的前半段还是后半段。

如果为前半段，则可以化为前一行字符串的第K个字符。如果为后半段，则可以化为前一行字符串取反后的第（K - 中间位置）的字符（取反操作，可以理解成第一行为1）。

代码：

 1 class Solution {
 2 public:
 3     int kthGrammar(int N, int K) {
 4         return recursion(0, N, K);
 5     }
 6     int recursion(int num, int N, int K) {
 7         if (N == 1) return num;
 8         int mid = 1 << (N - 2);
 9         if (K <= mid)
10             return recursion(num, N - 1, K);
11         else
12             return recursion(1 - num, N - 1, K - mid);
13     }
14 };

LC-779 语法中的第k个字符

原文：https://www.cnblogs.com/leo-lzj/p/11530286.html