※ 引述《wwndbk (snoopy養的狗)》之銘言：
: 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 個數字是多少。
補課
First thought:
DP或是遞迴解 不斷從前一個row往後推下一個row。
Approach:
我把數列列出來
// n = 1: 0
// n = 2: 01
// n = 3: 0110
// n = 4: 01101001
// n = 5: 0110100110010110
// k = 1234567890123456
發現每一個row的前半
都跟前一個row長的一模一樣
後半才是新衍生出來的
這代表什麼？
代表n根本不重要
第n row第3個數字跟第3 row的第3個數字會一樣
所以我們根本不用考慮n
反正題目已經限制k < 2^n
再來是我們去觀察數字生成的方式
// n = 4: 01101001
// n = 5: 0110100110010110
// k = 1234567890123456
從黃色的規律跟紅色的規律可以發現兩個現象
1. 第15跟第16個數字只會受到第8個數字影響
2. 奇數會跟前一個數字一樣 偶數會反轉
例如16->8以及14->7都反轉了 然後15->8 13->7都不反轉
這樣看下來算式就很簡單：
查看是不是偶數，是的話就反轉然後index/2
一直查到1 最後輸出解。
TS code:
function kthGrammar (n: number, k: number): number {
let result = false
for (let i = k; i > 1; i = Math.ceil(i / 2)) {
if (i % 2 === 0) result = !result
}
return result ? 1 : 0
}
結果丟上去速度超慢的 被80%的人屌打
研究了一下 我用到了%以及ceil(i/2)
代表每次運算我都進行了兩次除法
非常吃效能
所以我把它全部改成用二進制去計算
i / 2 -> i >> 1
i % 2 -> (i & 1)
最後效能達到PR90
TS code:
function kthGrammar (n: number, k: number): number {
let result = false
for (let i = k; i > 1; i = i >> 1) {
if ((i & 1) === 0) { result = !result }
else { i++ }
}
return result ? 1 : 0
}