Leetcode 779求解第N-1行中第K-1个字符 疑问

Question

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kthGrammar = function(n, k) {
    // 0
    // 01
    // 01 10
    let arr=['0']; // 将n行的字符串放入arr数组中
    for( let i = 1; i < n; i ++ ){
        // 第i - 1行字符串根据 0=>01, 1=>10规则生成第i行的字符串
        let baseNum = arr[i - 1]; // 取数组上一次的字符串
        let sumStr = ''; // 第i行的字符串
        for( let j = 0; j < baseNum.length; j ++ ){
            if( baseNum[j] == '0' ){
                // 处理 0
                sumStr += '01';
            }else{
                // 处理 1
                sumStr += '10';
            }
        } // for j
        arr.push( sumStr );
    } // for i

    // 取出 arr[arr.length - 1]字符串，然后取第k-1个字符
    return parseInt( arr[arr.length-1].charAt(k-1));
};

老师，今天的779道题目,在我看来其实就是先得到第N行的字符串, 然后再取出第N行字符串的第K个字符，所以整个求解过程分成了两步。然后leetcode判题系统报错，然后我本地就写了一个测试文件:

随首kthGrammar(N)，N很大时，函数中arr中字符串量惊人了，然后题解用了位运算，我是有点摸不着头脑，就只想到上述的方法，所以请老师帮忙解惑哈。。。

Answer 1

liuyubobobo 2022-10-21 02:32:22

直接去得到第 n 行的字符串肯定不行。下一行字符串的长度是上一行的 2 倍，所以这是指数上升的。

==========

实际上，我们完全不需要求解出第 n 行的整个字符串。

比如 n = 10，此时我们知道第 n 行有 1024 个字符（我用 0-based 的索引，在下面的代码中，我会把原问题的 1-based 索引化成 0-based 的索引）。

这 1024 个字符的前 512 个字符是由 0 变成 01 以后的 0 生成的；后 512 个字符是由 0 变成 01 以后的 1 生成的。如果 k 在前 512 个字符的范围，后 512 个字符我们就可以扔掉；如果 k 在后 512 个字符的范围，前 512 个字符我们就可以扔掉。

如果 k 在前 512 个字符，此时我们相当于变成了求解从 0 开始派生，n = 9 的时候，第 k 个字符是谁；

如果 k 在后 512 个字符，此时我们相当于变成了求解从 1 开始派生，n = 9 的时候，第 k - 512 个字符是谁；

这是一个递归结构。递归过程中每次扔掉一半字符，最后只剩下一个字符而已。

这个思路的参考代码可以参考这里：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0501-1000/0779-K-th-Symbol-in-Grammar/cpp-0779/main.cpp

solve(parent, n, k) 表示求解从 parent 开始派生，n 层以后，第 k 个字符是谁。其中 n 和 k 我都化成从 0 开始的索引(原问题是从 1 开始的）。我个人认为代码逻辑还是很清晰的，如果有问题你可以追加提问。

在这个逻辑的基础上，这个代码还可以进一步使用位运算进行化简，不过我觉得已非必须了。

继续加油！：） 

• 提问者 甲骨文_0001 #1

  老师，如果此时要求解第3行, 第4个字符，那么函数调用是 
  1. sovle(0, 2, 3), mid = pow(2, 1) = 2, 接下来就开始
  2. solve(1, 1, 3-2),
  3.solve(0, 0, 0), 能得出结果了,
  ==================================
  递归代码很清爽，但是和二叉树那样的递归逻辑有很大的不同，而且又像二分法，问题要求在某行某列的值，自己一下子理解不了，有种说不上来的感觉。

• liuyubobobo 回复 提问者 甲骨文_0001 #2

  你的模拟是有错误的。
  
  第 3 行第 4 个字符（假设都是 0-based），调用的是 solve(0, 3, 4)
  
  此时，mid = 1 << (3 - 1) = 1<<2 = 4。
  
  请你再仔细理解一下参数列表，如果需要，请实际运行程序进行调用跟踪。
  
  继续加油！：）

• 提问者 甲骨文_0001 回复 liuyubobobo #3

  谢谢老师哈，我心中要再消化消化，这种递归的语义如果您不说，我根本想不出来的。

点开查看后面1条评论