第k个语法符号【LC779】
我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
- 例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。
给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）
还是只能想到简单的找规律去模拟这个过程，如何把位运算和递归深入骨髓？
加油！努力写出高级的代码
StringBuilder模拟[内存超出限制]
class Solution { public int kthGrammar(int n, int k) { if (n == 1 && k == 1){ return 0; } if (n == 2){ if (k == 1){ return 0; }else if(k == 2){ return 1; } } StringBuilder sb = new StringBuilder("01"); for (int i = 0; i < n - 2; i++){ for(int j = 0; j < sb.length(); j++){ if (sb.charAt(j) == '0'){ sb.append('1'); }else{ sb.append('0'); } } } return sb.charAt(k-1) - '0'; } }
找规律
1.每一行的后半部分正好为前一半取反，前半部分是 0 后半部分变为 1，前半部分是 1，后半部分变为 0。
2.那么如果k>1或者n>1，那么证明k在某个对称轴后半部分，可以进行取反，这个对称轴为小于k的最大的2n，k-=2n，标记flag取反
3.最后如果flag为true，表明不需取反，返回0；flag为false，表明需要取反，返回1
- 代码
class Solution { public int kthGrammar(int n, int k) { Boolean flag = true; // 当flag为true时，不需要取反；当flag为false时，需要取反； // while (k > 1){// 能够对称反转 // while (Math.pow(2,n) >= k){ // n--; // } // k -= Math.pow(2,n); // flag = !flag; // } while (n > 1){ if (k > Math.pow(2,n-2)){ flag = !flag; k -= Math.pow(2,n-2); } n--; } return flag ? 0 : 1; } }
- 复杂度分析
。时间复杂度：O(n)，其中 n为行数。
。空间复杂度：O(1)。
正向递归
class Solution { public int kthGrammar(int n, int k) { return dfs(n,k); } public int dfs(int n, int k){ if (n == 1){ return 0; } int len = (int)(Math.pow(2,n - 2));// 上一行的长度 if (k <= len){// 前半段 return dfs(n - 1, k); }else{ return dfs(n - 1, k - len) == 0 ? 1 : 0;// 后半段 取反 } } }
- 复杂度分析
。时间复杂度：O(n)，其中 n为行数。
。空间复杂度：O(n)，递归的空间开销
逆向递归
假设第 n 行 第 k 个元素是 1，开始验证，直到最底层（第 1 行），如果一样，说明就是返回当前元素，否则返回相反元素。
class Solution { public int kthGrammar(int n, int k) { return dfs(n, k, 1) == 0 ? 1 : 0; } int dfs(int r, int c, int cur) { if (r == 1) return cur; if ((c % 2 == 0 && cur == 0) || (c % 2 == 1 && cur == 1)) return dfs(r - 1, (c - 1) / 2 + 1, 1); else return dfs(r - 1, (c - 1) / 2 + 1, 0); } } 作者：宫水三叶 链接：https://leetcode.cn/problems/k-th-symbol-in-grammar/solutions/1906532/by-ac_oier-fp2f/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
正向递归+位运算
1 << (n - 2) : pow(2,n-2)
1 ^ n ：本题可以达到取反的功能
class Solution { public int kthGrammar(int n, int k) { if (k == 1) { return 0; } if (k > (1 << (n - 2))) { return 1 ^ kthGrammar(n - 1, k - (1 << (n - 2))); } return kthGrammar(n - 1, k); } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/k-th-symbol-in-grammar/solutions/1903508/di-kge-yu-fa-fu-hao-by-leetcode-solution-zgwd/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
