LC 70. Climbing Stairs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| /**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
const q = [[1, 1], [1, 0]]
const res = pow(q, n)
return res[0][0]
};
const pow = (a, n) => {
let ret = [[1, 0], [0, 1]]
while (n > 0) {
if ((n & 1) === 1) {
ret = multiply(ret, a)
}
n >>= 1
a = multiply(a, a)
}
return ret
}
const multiply = (a, b) => {
const c = new Array(2).fill(0).map(() => new Array(2).fill(0))
for (let i = 0; i < 2; i++) {
for (let j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
}
}
return c
}
|
评论和交流请发送邮件到 me@tianhegao.com