779.第K个语法符号

链接：779.第K个语法符号
难度：Medium
标签：位运算、递归、数学
简介：给定行数 n 和序数 k，返回第 n 行中第 k 个字符。

题解 1 - cpp

• 编辑时间：2022-10-20
• 执行用时：4ms
• 内存消耗：5.9MB
• 编程语言：cpp
• 解法介绍：当前层前半段和上层一样，第三段和第二段相同，第一段和第四段相同。

class Solution {
public:
    int kthGrammar(int n, int k) {
        if (n == 1) return 0;
        else if (n == 2) return k == 1 ? 0 : 1;
        int nmax = pow(2, n - 1), nextK = k;
        if (k > nmax / 2 && k <= nmax / 4 * 3) nextK = k - nmax / 2 + nmax / 4;
        else if (k > nmax / 4 * 3) nextK = k - nmax / 2 - nmax / 4;
        return kthGrammar(n - 1, nextK);
    }
};