Leetcode 779求解第N-1行中第K-1个字符 疑问
来源：1-5 大厂面试为什么总考算法？
甲骨文_0001
2022-10-20
/**
* @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中字符串量惊人了，然后题解用了位运算，我是有点摸不着头脑，就只想到上述的方法，所以请老师帮忙解惑哈。。。
1回答
-
liuyubobobo
2022-10-21
直接去得到第 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 开始的）。我个人认为代码逻辑还是很清晰的，如果有问题你可以追加提问。
在这个逻辑的基础上，这个代码还可以进一步使用位运算进行化简，不过我觉得已非必须了。
继续加油！：）
042022-10-22
相似问题