779. 第K个语法符号
# 779. 第 K 个语法符号
我们构建了一个包含 n 行 ( 索引从 1 开始 ) 的表。首先在第一行我们写上一个 0。接下来的每一行,将前一行中的 0 替换为 01,1 替换为 10。
- 例如,对于 n = 3 ,第 1 行是 0 ,第 2 行是 01 ,第 3 行是 0110 。
给定行数 n 和序数 k,返回第 n 行中第 k 个字符。( k 从索引 1 开始)
示例 1:
输入: n = 1, k = 1 |
示例 2:
输入: n = 2, k = 1 |
示例 3:
输入: n = 2, k = 2 |
提示:
- 1 <= n <= 30
- 1 <= k <= $2^n - 1$
# 题解
这道题和腾讯笔试题很像。
本质上每一次操作都是在上一行基础上添加其按位取反后的结果。
class Solution { |
复杂度分析
- 时间复杂度:$O (logk)$
- 空间复杂度:$O (1)$
Invitation
x-17
202111170521
created:2021/11/17
Welcome to X
月缺不改光,剑折不改钢
共矜然诺心,各负纵横志
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 潇十七!
评论