LeetCode779递归序列

递归序列的问题，具体题目是 “K-th Symbol in Grammar”

题目描述:

在第一行，我们写下一个 0。接下来的每一行，将前一行的每个 0 替换为 01，每个 1 替换为 10。

给定行数 N 和序列中的索引 K，返回第 N 行中第 K 个字符的值（索引从1开始）。这里，第 N 行的长度是 2^(N-1)。

输入: N = 1, K = 1
输出: 0

输入: N = 2, K = 1
输出: 0

输入: N = 2, K = 2
输出: 1

输入: N = 4, K = 5
输出: 1

解题思路:

这个问题可以通过观察序列的生成规则和使用递归或迭代的方法来解决。在这里，我们提供一种递归的解决方案。

这个序列实际上是一个满二叉树，每个节点的值依赖于其父节点的值。如果父节点的值是 0，那么左子节点是 0，右子节点是 1；如果父节点是 1，那么左子节点是 1，右子节点是 0。

如果我们要找第 K 个数字，我们可以观察 K 是在左边还是右边。如果 K 小于或等于当前行的一半，那么它就在左边，我们可以继续在下一行的左半部分寻找。如果 K 大于当前行的一半，那么它在右边，我们可以继续在下一行的右半部分寻找，同时将 K 减去左半部分的长度。

public class Solution {
    // 定义方法 kthGrammar，它将返回第 N 行第 K 个字符的值
    public int kthGrammar(int N, int K) {
        // 递归终止条件：如果 N 为 1，第一行只有一个数字 0
        if (N == 1) return 0;
        
        // 计算前一行的长度，它是当前行长度的一半
        int prevRowLength = (int)Math.pow(2, N - 2);
        
        // 如果 K 在前一行长度的范围内，则表示 K 指向的数字与父节点相同
        if (K <= prevRowLength) {
            return kthGrammar(N - 1, K);
        } else {
            // 如果 K 大于前一行长度，则表示 K 指向的数字与父节点相反
            // 我们使用 1 减去父节点的值，来得到当前节点的值
            return 1 - kthGrammar(N - 1, K - prevRowLength);
        }
    }

    // 主方法用于测试上面定义的方法
    public static void main(String[] args) {
        Solution solution = new Solution(); // 创建 Solution 类的实例
        // 调用 kthGrammar 方法并打印结果，这里以第 4 行第 5 个字符为例
        System.out.println(solution.kthGrammar(4, 5)); // 输出应为 1
    }
}

代码的主要逻辑是使用递归来解决问题。我们首先定义了一个递归方法 kthGrammar，它接受两个参数：行号 N 和位置 K。该方法的目的是找到第 N 行第 K 个位置的值。

如果 N 等于 1，这意味着我们在第一行，根据题目描述，第一行只有一个数 0，因此直接返回 0。
如果 K 的值小于或等于前一行的长度，那么 K 指向的数字与其父节点的值相同。因此，我们递归调用 kthGrammar 方法，行号 N 减 1，位置 K 保持不变。
如果 K 的值大于前一行的长度，那么 K 指向的数字将与其父节点的值相反。我们首先计算前一行的长度，然后递归调用 kthGrammar 方法，行号 N 减 1，位置 K 减去前一行的长度。
最后，我们在 main 方法中测试 kthGrammar 方法，以确保它能正确返回第 N 行第 K 个位置的值。在这个例子中，我们计算第 4 行第 5 个位置的值，并打印出来。预期结果是 1。

__END__