Problem Solving/LeetCode
2023.10.25 Today's Challenge
fabichoi
2023. 10. 25. 23:45
https://leetcode.com/problems/k-th-symbol-in-grammar/
K-th Symbol in Grammar - LeetCode
Can you solve this real interview question? K-th Symbol in Grammar - We build a table of n rows (1-indexed). We start by writing 0 in the 1st row. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each o
leetcode.com
덮어놓고 배열을 만들다간 TL이 날 것 같은 문제.
솔루션을 보니 2진 트리로 만들어서 dfs 돌리는 방법 소개함.
더 놀라웠던건 수학적으로 증명하면 2줄로 마무리 됨 -_-;
class Solution:
def dfs(self, n, k, root):
if n == 1:
return root
total = 2 ** (n-1)
if k > (total / 2):
next_root = 1 if root == 0 else 0
return self.dfs(n-1, k-(total/2), next_root)
else:
next_root = 0 if root == 0 else 1
return self.dfs(n-1, k, next_root)
def kthGrammar(self, n: int, k: int) -> int:
return self.dfs(n, k, 0)
반응형