刷了 100 道 LeetCode，我也出两题回馈大家，难度适中，绝对不水

[begeekmyfriend]

1、用递归求 Fibonacci，要求速度不低于迭代；
2、排序的整型数组，有重复，求某个元素出现次数。​​​​

[helica]

感觉有点低估 v 站的 coding 水平了:D

[zjbztianya]

@xiang578 1e9+7 暴露了你是 ACMer...

[xiang578]

@zjbztianya #22 你这是和我同归于尽……

[mskf]

//第一题：

public class Fibonacci {

/**
* /a b/
* /c d/
*/
private static class Matrix{
int a;
int b;
int c;
int d;

public Matrix(int a, int b, int c, int d) {
this.a = a;
this.b = b;
this.c = c;
this.d = d;
}
}

public static void main(String[] args) {
Arrays.asList(1,2,3,4,5,6,7,8,9,10).stream().forEach(n->System.out.println(fibonacci(n)));
}


public static int fibonacci(int n){
if(n==1)
return 0;
return Fib(n-1).b;
}

public static Matrix Fib(int n){
if(n==1)
return new Matrix(1,1,1,0);
return (n&1)==0?multi(Fib(n/2),Fib(n/2)):multi(Fib(n/2),Fib(n/2 + 1));
}

private static Matrix multi(Matrix m1,Matrix m2){
return new Matrix(
m1.a*m2.a+m1.b*m2.c,
m1.a*m2.b+m1.b*m2.d,
m1.c*m2.a+m1.d*m2.c,
m1.c*m2.b+m1.d*m2.d
);
}
}

[baka]

斐波那契校招面试一般这么问
1. 斐波那契知道吧，递推式写一下，顺便最简单的递归来写一个
2. O(n)行不行，迭代来写一个
3. 能不能再快点，矩阵快速幂推导一下，快速幂写一个
4. O(1)办得到吗？特征根求一下，通项解出来。特征根原理？

[jedihy]

1. fib 用 DP 就行，递归都不用。
2. 两次二分即可，两次二分只有等号情况处理不同。

[skadi]

namespace dd {
using ll = long long;
template <ll n> struct Fib {
enum { value = Fib<n - 1>::value + Fib<n - 2>::value };
};
template <> struct Fib<0> {
enum { value = 0 };
};
template <> struct Fib<1> {
enum { value = 1 };
};
}

int main(){
std::cout<<dd::Fib<10>::value<<std::endl;
}

斐波那契用模版元编译期计算算不算作弊? :huaji:
PS:虽然文不对题
PPS:炸出了很多 acmer 啊

[skadi]

第一题,快速幂
第二题 2 个二分

[111qqz]

@xiang578 1E9+7 还行

[longaiwp]

@xiang578 取模其实还有更好玩的东西，那就是你算的量还可以减少，取模我记得是有一个循环节的

[xiang578]

@longaiwp #30 对，取模之后这个序列是有循环节的，之前做一个学校的校赛遇到过