leetcode779

题目描述

在第一行我们写上一个 。接下来的每一行，将前一行中的 替换为 ， 替换为 。给定行数 和序数 ，返回第 行中第 个字符。（ 从1开始）。

题目分析

今天做这道题的时候一时间没有想到好的解决办法，于是没有多想就去看了题解，一看才发现这道题的解法竟然有这么多。题目本身难度并不大，但是仔细分析的话还是能发现其中的有趣之处的。首先，这道题虽然有两个输入：行数 和序数 ，但其实输出和 并没有关系，仅仅取决于 。我们只要简单地列几行就能发现，第 行的长度是 ，每一行可以分为两个部分，前半部分和它的上一行完全相等，而后半部分为前半部分的取反结果，我们仅仅需要确定 在这一行的哪一部分，就能将其转化为一个子问题，递归解法的思路就显而易见了（具体解法可以去看官方题解）。那么为什么输出和 无关呢，因为无论 有多大，只要 在第 行的前半部分，那么 与 就是等价的。反过来说，一旦确定了 ，我们总能找到某一行 ，使得 在第 行的后半部分，经过迭代， 可以转化成 ，而 是由 唯一决定的。所以说，递归解法用到了 这一无效条件，如果 非常大，会浪费大量的时间，并不是最优雅的解法。那么该怎么摆脱 的束缚呢？

解决

前面也说过，一旦确定了 ，我们总能找到某一行 ，使得 在第 行的后半部分。为方便理解，我们不妨让 从 开始，事先让 。我们从第 行开始分析，记第 行元素为 。我们要求的是 ， 等于 取反的结果（ 在后半部分，所以满足 ），而在前半部分，可以转化到上一行中，迭代这个过程，我们最终会到达第一行。反过来想，最终的结果其实是经过 次取反操作得到的，取反的源操作数就是第一行的 ，所以问题进一步转化确定 的大小，甚至 具体的大小都不需要知道，只需确定其奇偶。进一步分析， 有多次出现在行的后半部分，就需要进行多少次取反操作，当且仅当 满足条件，而 其实就说明 的二进制表示中最高位为 ，因为 ，所以 的最高位表示的就是 ，所以取反操作将 转化为 其实就是将这个最高位的 去掉了。反之，若在当前行中 的最高位为 ，则说明 在前半部分，直接过渡到上一行即可。综上所述，我们能得到一个令人惊叹的结论：取反操作次数等于 的二进制表示中 的个数。至此，这个问题就被漂亮地解决了。

代码

int kthGrammar(int N, int K) {
        bool ans = 0; K--;
        while(K) {
            if(K%2) ans = !ans;
            K /= 2;
        }
        return ans;
    }