Keshawn_lu's Blog

Leetcode 779. 第K个语法符号

递归
字数统计: 397阅读时长: 1 min
2022/10/20 Share

题目简介：

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

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

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

示例 1:

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

示例 2:

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

提示:

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

思路：

一开始想的是用正常构造方法进行递归，发现会超时。

将前几行的数字打印出来后，发现后一半数字是前一半数字的翻转（即1变成0，0变成1），并且当前行的前一半数字与前一行的数字完全相同。

因此，我们只需要不断向上递归，判断第k个数字是属于前一半还是后一半即可。

若属于前一半，则去找上一行的第k个数字；若属于后一半，则将上一行的第k - sum / 2个数字取反即可。（sum为当前行的数字总数）。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:

    int kthGrammar(int n, int k) {

        if(n == 1)
            return 0;

        int sum = pow(2, n - 1);    //这一行的数字总数
        if(k - 1 < sum / 2){  //k在前半部分

            return kthGrammar(n - 1, k);
        }

        else    //在后半部分，翻转
            return kthGrammar(n - 1, k - sum / 2) ^ 1;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网