: https://leetcode.com/problems/k-th-symbol-in-grammar/description
: 779. K-th Symbol in Grammar
: 給你一個數字 n 和一個數字 k，n 表示第幾列 k 表示第幾行（列和行從 1 開始）
: 第一列的數字固定為 0，第一列之後的數字按照以下規律：
: 取代前一列的所有 0 -> 01 取代前一列的所有 1 -> 10
: Example：
: n = 3，則
: ROW1=0
: ROW2=01
: ROW3=0110
: 求出第 n 列的第 k 個數字是多少。
思路：一開始想用dp做結果MLE
後來看了答案(哭啊)
可以發現
1. 每一row的前1/2數列 剛好是前一row的數列
2. 每一row的後1/2數列 剛好是前一row的數列 的相反(0 <-> 1)
- 所以可以利用change_count變數記憶到底翻了幾次
3. 第n==2的row的答案恰為k_index - 1
- 所以算到 n == 2 就可以得到 答案應該是 k-1
於是可以寫成下面這樣
========== Python
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
if (n == 1):
return 0
change_count = 0
while(n > 2):
if (k <= 2**(n-2)):
pass
else:
k = k - 2**(n-2)
change_count += 1
n -= 1
k = k - 1
if (change_count % 2 == 1):
k = self.change(k)
return k
def change(self, x):
if x == 1:
return 0
else:
return 1
========== C++
class Solution {
public:
int kthGrammar(int n, int k) {
int change_count = 0;
while(n > 2)
{
if (k <= pow(2, n-2)) {}
else
{
k = k - pow(2, n-2);
change_count++;
}
n