c++ - 使用 `k` 在语法中查找第 k 个符号背后的直觉

Question

我参加了一个coding contest其中我遇到了以下问题:

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10. Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.)

在解题的同时，I solved it就像树的层序遍历，试图在每一层形成新的字符串。不幸的是，它超时了。然后，我尝试考虑缓存结果等方面的问题，但没有成功。

highly upvoted solutions 之一是这样的:

class Solution {
public:
    int kthGrammar(int N, int K) {
    if (N == 1) return 0;
    if (K % 2 == 0) return (kthGrammar(N - 1, K / 2) == 0) ? 1 : 0;
    else return (kthGrammar(N - 1, (K + 1) / 2) == 0) ? 0 : 1;
    }
};

我的问题很简单 - 使用 K 的值(尤其是 K 的奇偶校验)背后的直觉是什么？ (希望以后遇到这样的问题时能够识别)。

谢谢。

Answer 1

递归地看序列。在生成新行时，前半部分与您用于获取前一行的过程相同，因此扩展部分已经完成。下半场只是相同的顺序颠倒(0 代表 1，1 代表 0)。这是生成奇偶校验图的一种经典方法:翻转所有位并追加，表示在每个二进制数的开头添加一个1。想到将序列0-3扩展为0-7，我们开始

00 => 0
01 => 1
10 => 1
11 => 0

我们现在将 2 位序列复制两次:首先是前导 0，它保留了原始奇偶校验；第二个带前导 1，它反转奇偶校验。

000 => 0
001 => 1
010 => 1
011 => 0
100 => 1
101 => 0
110 => 0
111 => 1

这种直觉对你有用吗？