bywangbing / by_-preparation Goto Github PK

准备挺用心的，刷这么多算法也试试外企吧
顺便一些算法题可以深挖一下，外企面到算法有一些亮点
比如斐波那契有复杂度更低的矩阵快速幂解法

原理：
fib[1] = 1, fib[2] = 1, fib[3] = fib[1] + fib[2]
[ fib[2], fib[1], 0 ] * [ 1, 1, 0 ] => [ fib[3], fib[2], fib[1] ]
------------------- [ 1, 0, 1 ]
------------------- [ 0, 0, 0 ]

令 M = [ 1, 1, 0 ]
------ [ 1, 0, 1 ]
------ [ 0, 0, 0 ]

[ fib[2], fib[1], 0 ] * (M ^ n) = [ fib[n + 2], fib[n + 1], fib[n] ]
而 (M ^ n) 可利用快速幂log级复杂度实现

小冰冰，咱们一起加油！！！