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

数组

fibonacci

leetcode

整型

31 条回复 • 2017-11-13 19:20:16 +08:00

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

2017-11-11 12:41:03 +08:00

@LxExExl 绝知此事要躬行

6

LxExExl

2017-11-11 12:45:30 +08:00 via iPhone

@begeekmyfriend 愿闻其详

7

begeekmyfriend

OP

2017-11-11 12:56:08 +08:00

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

8

begeekmyfriend

OP

2017-11-11 12:58:30 +08:00

@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

2017-11-11 13:53:42 +08:00

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

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

12

begeekmyfriend

OP

2017-11-11 13:57:45 +08:00

说第二题很水的我有理由怀疑对方二分编程有没有真正掌握，一写都是 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

2017-11-11 14:22:41 +08:00 via Android

@neosfung 线性就淘汰，哈哈

16

neosfung

2017-11-11 14:36:48 +08:00

@begeekmyfriend 嗯

17

neosfung

2017-11-11 14:38:08 +08:00

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

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 个二分

29

111qqz

2017-11-12 19:05:17 +08:00

@xiang578 1E9+7 还行

30

longaiwp

2017-11-13 04:07:38 +08:00

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

31

xiang578

2017-11-13 19:20:16 +08:00

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