※ 引述《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
}