侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【递归, 位运算】第K个语法符号

GabrielxD
2022-10-20 / 0 评论 / 0 点赞 / 10 阅读 / 516 字 / 正在检测是否收录...

题目

779. 第K个语法符号


我们构建了一个包含 n 行( 索引从 1  开始 )的表。首先在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为011替换为10

  • 例如,对于 n = 3 ,第 1 行是 0 ,第 2 行是 01 ,第3行是 0110

给定行数 n 和序数 k,返回第 n 行中第 k 个字符。( k 从索引 1 开始

示例 1:

输入: n = 1, k = 1
输出: 0
解释: 第一行:0

示例 2:

输入: n = 2, k = 1
输出: 0
解释: 
第一行: 0 
第二行: 01

示例 3:

输入: n = 2, k = 2
输出: 1
解释:
第一行: 0
第二行: 01

提示:

  • 1 <= n <= 30
  • 1 <= k <= 2^n - 1

解题

方法一:递归 位运算

思路

把每一行看作每一层就可以构造一棵满二叉树:

image-20221020005702822

这样我们就找到了规律:每个节点上的值只与其父节点的值以及其是左子节点还是右子节点有关,具体来说:

  • 左子节点上的值与其父节点相同(00,110\to0, 1\to1
  • 右子节点上的值与其父节点相反(01,100\to1, 1\to0

众所周知,满二叉树可以用数组存储,此时由某节点 xx 可以找到其父节点 x+12\frac{x+1}{2} ,那么求第任意层的第任意个值都可以递归到其根节点 00 上。

异或上一个 11 可以做到把 1100 ,把 0011

代码

class Solution {
    public int kthGrammar(int n, int k) {
        if (n == 1) return 0;
        return (k & 1) == 0 ?
            kthGrammar(n - 1, (k + 1) / 2) ^ 1 :
            kthGrammar(n - 1, (k + 1) / 2);
    }
}
一行写法
class Solution {
public:
    int kthGrammar(int n, int k) {
        return n == 1 ? 0 : !(k & 1) ^ kthGrammar(n - 1, (k + 1) / 2);
    }
};
class Solution {
public:
    int kthGrammar(int n, int k) {
        return n == 1 ? 0 : !(k & 1) ^ kthGrammar(n - 1, (k + 1) / 2);
    }
};
0

评论区