V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
begeekmyfriend
V2EX  ›  程序员

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

  •  
  •   begeekmyfriend ·
    begeekmyfriend · 2017-11-11 11:56:53 +08:00 · 4994 次点击
    这是一个创建于 2568 天前的主题,其中的信息可能已经有所发展或是发生改变。
    1、用递归求 Fibonacci,要求速度不低于迭代;
    2、排序的整型数组,有重复,求某个元素出现次数。​​​​
    31 条回复    2017-11-13 19:20:16 +08:00
    chuaInQZ
        1
    chuaInQZ  
       2017-11-11 12:27:28 +08:00 via Android
    1 尾递归
    2 二分查找+前后遍历
    geelaw
        2
    geelaw  
       2017-11-11 12:32:36 +08:00 via iPhone
    ???这个真的连水都算不上

    第一个用快速幂的递归写法即可满足要求,而且比迭代要快(如果四则运算是常数)
    第二个用 upper_bound 和 lower_bound 的算法即可
    LxExExl
        3
    LxExExl  
       2017-11-11 12:34:09 +08:00 via iPhone
    2 二分查找 变换下等号就行了
    geelaw
        4
    geelaw  
       2017-11-11 12:34:11 +08:00 via iPhone
    哦第一个还可以更简单,只要形参和返回值都是 pair 即可
    begeekmyfriend
        5
    begeekmyfriend  
    OP
       2017-11-11 12:41:03 +08:00
    @LxExExl 绝知此事要躬行
    LxExExl
        6
    LxExExl  
       2017-11-11 12:45:30 +08:00 via iPhone
    @begeekmyfriend 愿闻其详
    begeekmyfriend
        8
    begeekmyfriend  
    OP
       2017-11-11 12:58:30 +08:00
    @geelaw 不懂你的“快速幂”是啥意思,方便贴一下么?还是利用某种语言的黑科技?
    qiukun
        9
    qiukun  
       2017-11-11 13:08:03 +08:00   ❤️ 1
    @begeekmyfriend fibonacci 是线性关系可以用矩阵表示,矩阵乘法可以用类似普通幂乘的优化
    qwlhappy
        10
    qwlhappy  
       2017-11-11 13:23:37 +08:00
    这不是...C 语言课后习题的水平?虽说想做到最优可能都要仔细考虑下
    begeekmyfriend
        11
    begeekmyfriend  
    OP
       2017-11-11 13:53:42 +08:00
    @qwlhappy 到不一定要最优。第一题考 memorized+递归;第二题就是考二分编程,传说中 90%的人都会写错的那种

    出面试题的原则——淘汰水货,中等水平做得出来,还能让高手闪光。
    begeekmyfriend
        12
    begeekmyfriend  
    OP
       2017-11-11 13:57:45 +08:00
    说第二题很水的我有理由怀疑对方二分编程有没有真正掌握,一写都是 O(N)
    neosfung
        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
    neosfung
        14
    neosfung  
       2017-11-11 14:06:34 +08:00
    第二题直接用二分命中一个后,线性搜索前后的数字就行了,最坏情况 O(n)
    begeekmyfriend
        15
    begeekmyfriend  
    OP
       2017-11-11 14:22:41 +08:00 via Android
    @neosfung 线性就淘汰,哈哈
    neosfung
        16
    neosfung  
       2017-11-11 14:36:48 +08:00
    neosfung
        17
    neosfung  
       2017-11-11 14:38:08 +08:00
    @qiukun 貌似是编程之美中的方法?
    sagaxu
        18
    sagaxu  
       2017-11-11 15:01:15 +08:00 via Android
    太水了,第一题递归加 cache,第二题两次二分法确定这个数的首尾位置再相减得到个数
    LxExExl
        19
    LxExExl  
       2017-11-11 15:39:34 +08:00 via iPhone
    @begeekmyfriend 我去年找工作 lc 算下来刷了起码两遍 重点题三遍 基本到最后每个题都是 10 分钟一次性 ac...
    xiang578
        20
    xiang578  
       2017-11-11 16:11:22 +08:00
    @neosfung #17 应该出现过,利用矩阵快速幂还可以处理比如求 Fibonacci 第 1 亿项对 1e9+7 取模的结果
    helica
        21
    helica  
       2017-11-11 16:21:00 +08:00 via iPhone
    感觉有点低估 v 站的 coding 水平了:D
    zjbztianya
        22
    zjbztianya  
       2017-11-11 16:28:37 +08:00
    @xiang578 1e9+7 暴露了你是 ACMer...
    xiang578
        23
    xiang578  
       2017-11-11 16:38:48 +08:00
    @zjbztianya #22 你这是和我同归于尽……
    mskf
        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
    );
    }
    }
    baka
        25
    baka  
       2017-11-12 05:49:47 +08:00   ❤️ 2
    斐波那契校招面试一般这么问
    1. 斐波那契知道吧,递推式写一下,顺便最简单的递归来写一个
    2. O(n)行不行,迭代来写一个
    3. 能不能再快点,矩阵快速幂推导一下,快速幂写一个
    4. O(1)办得到吗?特征根求一下,通项解出来。特征根原理?
    jedihy
        26
    jedihy  
       2017-11-12 08:31:01 +08:00
    1. fib 用 DP 就行,递归都不用。
    2. 两次二分即可,两次二分只有等号情况处理不同。
    skadi
        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 啊
    skadi
        28
    skadi  
       2017-11-12 09:58:04 +08:00
    第一题,快速幂
    第二题 2 个二分
    111qqz
        29
    111qqz  
       2017-11-12 19:05:17 +08:00
    @xiang578 1E9+7 还行
    longaiwp
        30
    longaiwp  
       2017-11-13 04:07:38 +08:00
    @xiang578 取模其实还有更好玩的东西,那就是你算的量还可以减少,取模我记得是有一个循环节的
    xiang578
        31
    xiang578  
       2017-11-13 19:20:16 +08:00
    @longaiwp #30 对,取模之后这个序列是有循环节的,之前做一个学校的校赛遇到过
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1142 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 18:31 · PVG 02:31 · LAX 10:31 · JFK 13:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.