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

[begeekmyfriend]

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

[chuaInQZ]

1 尾递归
2 二分查找+前后遍历

[geelaw]

？？？这个真的连水都算不上

第一个用快速幂的递归写法即可满足要求，而且比迭代要快（如果四则运算是常数）
第二个用 upper_bound 和 lower_bound 的算法即可

[LxExExl]

2 二分查找 变换下等号就行了

[geelaw]

哦第一个还可以更简单，只要形参和返回值都是 pair 即可

[begeekmyfriend]

@LxExExl 绝知此事要躬行

[LxExExl]

@begeekmyfriend 愿闻其详

[begeekmyfriend]

@LxExExl 这是我自己写的 C 参考： https://github.com/begeekmyfriend/bplustree/blob/in-memory/lib/bplustree.c#L27，当然还有一个镜像，合起来就是。不过我不确定你是否掌握，最好自己写一遍

[begeekmyfriend]

@geelaw 不懂你的“快速幂”是啥意思，方便贴一下么？还是利用某种语言的黑科技？

[qiukun]

@begeekmyfriend fibonacci 是线性关系可以用矩阵表示，矩阵乘法可以用类似普通幂乘的优化

[qwlhappy]

这不是...C 语言课后习题的水平？虽说想做到最优可能都要仔细考虑下

[begeekmyfriend]

@qwlhappy 到不一定要最优。第一题考 memorized+递归；第二题就是考二分编程，传说中 90%的人都会写错的那种

出面试题的原则——淘汰水货，中等水平做得出来，还能让高手闪光。

[begeekmyfriend]

说第二题很水的我有理由怀疑对方二分编程有没有真正掌握，一写都是 O(N)

[neosfung]

def foo(n, a=0, b=1):
return foo(n-1, b, a+b) if n>0 else a+b

[neosfung]

第二题直接用二分命中一个后，线性搜索前后的数字就行了，最坏情况 O(n)

[begeekmyfriend]

@neosfung 线性就淘汰，哈哈

[neosfung]

@begeekmyfriend 嗯

[neosfung]

@qiukun 貌似是编程之美中的方法？

[sagaxu]

太水了，第一题递归加 cache，第二题两次二分法确定这个数的首尾位置再相减得到个数

[LxExExl]

@begeekmyfriend 我去年找工作 lc 算下来刷了起码两遍 重点题三遍 基本到最后每个题都是 10 分钟一次性 ac...

[xiang578]

@neosfung #17 应该出现过，利用矩阵快速幂还可以处理比如求 Fibonacci 第 1 亿项对 1e9+7 取模的结果