1
chuaInQZ 2017-11-11 12:27:28 +08:00 via Android
1 尾递归
2 二分查找+前后遍历 |
2
geelaw 2017-11-11 12:32:36 +08:00 via iPhone
???这个真的连水都算不上
第一个用快速幂的递归写法即可满足要求,而且比迭代要快(如果四则运算是常数) 第二个用 upper_bound 和 lower_bound 的算法即可 |
3
LxExExl 2017-11-11 12:34:09 +08:00 via iPhone
2 二分查找 变换下等号就行了
|
4
geelaw 2017-11-11 12:34:11 +08:00 via iPhone
哦第一个还可以更简单,只要形参和返回值都是 pair 即可
|
5
begeekmyfriend OP @LxExExl 绝知此事要躬行
|
6
LxExExl 2017-11-11 12:45:30 +08:00 via iPhone
@begeekmyfriend 愿闻其详
|
7
begeekmyfriend OP |
8
begeekmyfriend OP @geelaw 不懂你的“快速幂”是啥意思,方便贴一下么?还是利用某种语言的黑科技?
|
9
qiukun 2017-11-11 13:08:03 +08:00 1
@begeekmyfriend fibonacci 是线性关系可以用矩阵表示,矩阵乘法可以用类似普通幂乘的优化
|
10
qwlhappy 2017-11-11 13:23:37 +08:00
这不是...C 语言课后习题的水平?虽说想做到最优可能都要仔细考虑下
|
11
begeekmyfriend OP |
12
begeekmyfriend OP 说第二题很水的我有理由怀疑对方二分编程有没有真正掌握,一写都是 O(N)
|
13
neosfung 2017-11-11 14:03:22 +08:00
def foo(n, a=0, b=1):
return foo(n-1, b, a+b) if n>0 else a+b |
14
neosfung 2017-11-11 14:06:34 +08:00
第二题直接用二分命中一个后,线性搜索前后的数字就行了,最坏情况 O(n)
|
15
begeekmyfriend OP @neosfung 线性就淘汰,哈哈
|
16
neosfung 2017-11-11 14:36:48 +08:00
|
18
sagaxu 2017-11-11 15:01:15 +08:00 via Android
太水了,第一题递归加 cache,第二题两次二分法确定这个数的首尾位置再相减得到个数
|
19
LxExExl 2017-11-11 15:39:34 +08:00 via iPhone
@begeekmyfriend 我去年找工作 lc 算下来刷了起码两遍 重点题三遍 基本到最后每个题都是 10 分钟一次性 ac...
|
20
xiang578 2017-11-11 16:11:22 +08:00
@neosfung #17 应该出现过,利用矩阵快速幂还可以处理比如求 Fibonacci 第 1 亿项对 1e9+7 取模的结果
|
21
helica 2017-11-11 16:21:00 +08:00 via iPhone
感觉有点低估 v 站的 coding 水平了:D
|
22
zjbztianya 2017-11-11 16:28:37 +08:00
@xiang578 1e9+7 暴露了你是 ACMer...
|
23
xiang578 2017-11-11 16:38:48 +08:00
@zjbztianya #22 你这是和我同归于尽……
|
24
mskf 2017-11-11 17:30:48 +08:00 1
//第一题:
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 ); } } |
25
baka 2017-11-12 05:49:47 +08:00 2
斐波那契校招面试一般这么问
1. 斐波那契知道吧,递推式写一下,顺便最简单的递归来写一个 2. O(n)行不行,迭代来写一个 3. 能不能再快点,矩阵快速幂推导一下,快速幂写一个 4. O(1)办得到吗?特征根求一下,通项解出来。特征根原理? |
26
jedihy 2017-11-12 08:31:01 +08:00
1. fib 用 DP 就行,递归都不用。
2. 两次二分即可,两次二分只有等号情况处理不同。 |
27
skadi 2017-11-12 09:52:04 +08:00
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 啊 |
28
skadi 2017-11-12 09:58:04 +08:00
第一题,快速幂
第二题 2 个二分 |