题目形容
这是 LeetCode 上的 779. 第 K 个语法符号 ,难度为 中等。
Tag :「DFS」、「递归」
咱们构建了一个蕴含 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
输入: 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}$
递归(倒推验证)
整顿一下条件:首行为 0
,每次用以后行拓展出下一行时,字符数量翻倍(将 0
拓展为 01
,将 1
拓展为 10
),且字符品种仍为 01
。
要求咱们输入第 $n$ 行第 $k$ 列的字符,咱们能够通过「倒推验证」的形式来求解:假如第 $n$ 行第 $k$ 为 1
,若能倒推出首行为 $0$,阐明假如成立,返回 1
,否则返回 0
。
倒推验证可通过实现递归函数 int dfs(int r, int c, int cur)
来做,含意为当第 $r$ 行第 $c$ 列的字符为 $cur$ 时,首行首列字符为何值。同时实现该函数是容易的:
- 若「当前列 $c$ 为偶数且 $cur = 0$」或「当前列 $c$ 为奇数且 $cur = 1$」时,阐明当前列所在的组为
10
,由此可推出其是由上一行的1
拓展而来,联合每次拓展新行字符数量翻倍的条件,可知是由第 $r – 1$ 行的第 $\left \lfloor \frac{c – 1}{2} \right \rfloor + 1$ 列的1
拓展而来,递归解决; - 否则,同理,必然是上一行(第 $r – 1$ 行)对应地位的
0
拓展而来,递归解决。
最终,当倒推到首行时,咱们找到了递归进口,间接返回 cur
。
Java 代码:
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);
}
}
TypeScript 代码:
function kthGrammar(n: number, k: number): number {function dfs(r: number, c: number, cur: number): number {if (r == 1) return cur
if ((c % 2 == 0 && cur == 0) || (c % 2 == 1 && cur == 1)) return dfs(r - 1, Math.floor((c - 1) / 2) + 1, 1)
else return dfs(r - 1, Math.floor((c - 1) / 2) + 1, 0)
}
return dfs(n, k, 1) == 0 ? 1 : 0
}
Python 代码:
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
def dfs(r, c, cur):
if r == 1:
return cur
if (c % 2 == 0 and cur == 0) or (c % 2 == 1 and cur == 1):
return dfs(r - 1, (c - 1) // 2 + 1, 1)
else:
return dfs(r - 1, (c - 1) // 2 + 1, 0)
return 1 if dfs(n, k, 1) == 0 else 0
- 工夫复杂度:$O(n)$
- 空间复杂度:疏忽递归带来的额定空间开销,复杂度为 $O(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.779
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布