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

关于学习数据结构与算法的一些经历分享?

  •  
  •   shuaidi · 2018-12-04 16:53:08 +08:00 · 3436 次点击
    这是一个创建于 1941 天前的主题,其中的信息可能已经有所发展或是发生改变。

    数据结构与算法的地位对于一个程序员来说不言而喻。今天这篇文章不是来劝你们学习数据结构与算法的,也不是来和你们说数据结构与算法有多重要。

    主要是最近几天后台有读者问我是如何学习数据结构与算法的,有没有什么捷径,是要看视频还是看书,去哪刷题等.....而且有些还是大三大四的,搞的我都替你们着急、担心.....

    所以我今天就分享下自己平时都是怎么学习的。

    学习算法的捷径就是多刷题

    说实话,要说捷径,我觉得就是脚踏实地着多动手去刷题,多刷题。

    但是,如果你是小白,也就是说,你连常见的数据结构,如链表、树以及常见的算法思想,如递归、枚举、动态规划这些都没学过,那么,我不建议你去刷题的。而是先去找本书先去学习这些,然后再去刷题。

    也就是说,假如你要去诸如 leetcode 这些网站刷题,那么,你要先具备一定的基础,这些基础包括:

    1、常见数据结构:链表、树(如二叉树)。

    2、常见算法思想:贪婪法、分治法、穷举法、动态规划,回溯法。

    以上列出来的算是最基本的吧。就是说你刷题之前,要把这些过一遍再去刷题。如果你连这些最基本的都不知道的话,那么你再刷题的过程中,会很难受的,思路也会相对比较少。

    总之,千万不要急,先把这些基本的过一遍,力求理解,再去刷题。这些基础的数据结构与算法,我是在大一第二学期学的,我没看视频,我是通过看书学的,那时候看的书是:

    1、算法分析与分析基础:这本比较简单,推荐新手看。

    2、数据结构与算法分析---C 语言描述:代码用 C 写的,推荐看。

    3、挑战程序设计竞赛(第二版):也是很不错的一本书,推荐看。

    具体可以看我的另外一篇文章,里面是介绍这几本书以及一些视频的:(外部链接放了发不了文,搜索公众号“苦逼的码农”,回复“数据结构与算法”即可获取)

    说实话,我那一学期的时间几乎都花在数据结构与算法上,但刷的题很少,只是书本上的一些例题。所以当我把这些基本的过一遍之后,再去一些网站刷题依旧非常菜。

    所以你们千万别指望以为自己把这些思想学完之后刷题会很牛,只有多刷题,只有多动手实践,你的灵敏度才会提高起来。

    在这里说一下前阵子有个非常火爆的专栏--- [数据结构与算法之美]

    我没买这个专栏,我想说的是,买了就一定要去看,千万别浪费。也千万不要觉得学完这个专栏你就会变的多牛逼,如果你只是跟着进度去学习这个专栏,自己没有花时间去刷题、去动手时间。那我可以保证,你学完之后还是那么菜。

    总结下:

    提高数据结构与算法没啥捷径,最好的捷径就是多刷题。但是,刷题的前提是你要先学会一些基本的数据结构与算法思想。

    追求完美

    如何刷题?如何对待一道算法题?

    我觉得,在做题的时候,一定要追求完美,千万不要把一道题做出来之后,提交通过,然后就赶紧下一道。

    算法能力的提升和做题的数量是有一定的关系,但并不是线性关系。也就是说,在做题的时候,要力求一题多解,如果自己实在想不出来其他办法了,可以去看看别人是怎么做的,千万不要觉得模仿别人的做法是件丢人的事。

    我做题的时候,我一看到一道题,可能第一想法就是用很粗糙的方式做,因为很多题采用暴力法都会很容易做,就是时间复杂度很高。之后,我就会慢慢思考,看看有没其他方法来降低时间复杂度或空间复杂度。最后,我会去看一下别人的做法,当然,并不是每道题都会这样执行。

    衡量一道算法题的好坏无非就是时间复杂度空间复杂度,所以我们要力求完美,就要把这两个降到最低,令他们相辅相成。

    我举道例题吧:

    问题: 一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法?

    这道题我在以前的分章分析过,不懂的可以先看下之前写的:(外部链接不让放。。。。。)

    方法 1::暴力递归

    这道题不难,或许你会采取下面的做法:

    public static int solve(int n){
        if(n == 1 || n == 2){
            return n;
        }else if(n <= 0){
            return 0;
        }else{
            return solve(n-1) + solve(n-2);
        }
    }
    

    这种做法的时间复杂度很高,指数级别了。但是如果你提交之后侥幸通过了,然后你就接着下一道题了,那么你就要好好想想了。

    方法二:空间换时间

    力求完美,我们可以考虑用空间换时间:这道题如何你去仔细想一想,会发现有很多是重复执行了。所以可以采取下面的方法:

    //用一个 HashMap 来保存已经计算过的状态
    static Map<Integer,Integer> map = new HashMap();
    public static int solve(int n){
        if(n <= 0)return 0;
        else if(n <= 2){
            return n;
        }else{//是否计算过
            if(map.containsKey(n)){
                return map.get(n);
            }else{
                int m = solve(n-1) + solve(n-2);
                map.put(n, m);
                return m;
            }
        }
    }
    
    

    这样,可以大大缩短时间。也就是说,当一道题你做了之后,发现时间复杂度很高,那么可以考虑下,是否有更好的方法,是否可以用空间换时间。

    方法三:斐波那契数列

    实际上,我们可以把空间复杂度弄的更小,不需要 HashMap 来保存状态:

    public static int solve(int n){
        if(n <= 0)
           return 0;
        if(n <= 2){
            return n;
        }
        
        int f1 = 0;
        int f2 = 1;
        int sum = 0;
        for(int i = 1; i<= n; i++){
            sum = f1 + f2;
            f1 = f2;
            f2 = sum;
        }
        return sum;
    }
    

    我弄这道题给你们看,并不是在教你们这道题怎么做,而是有以下目的:

    1、在刷题的时候,我们要力求完美。

    2、我想不到这些方法啊,怎么办?那么你就可以去看别人的做法,之后,遇到类似的题,你就会更有思路,更知道往哪个方向想。

    3、可以从简单暴力入手做一道题,在考虑空间与时间之间的衡量,一点点去优化。

    推荐一些刷题网站

    我一般是在 leetcode 和牛客网刷题,感觉挺不错,题目难度不是很大。

    在牛客网那里,我主要刷剑指 Offer,不过那里也有个在线刷 leetcode,不过里面的题量比较少。牛客网刷题有个非常方便的地方就是有个讨论区,那里会有很多大佬分享他们的解题方法,不用我们去百度找题解。所以你做完后,实在想不出,可以很方便着去看别人是怎么做的。

    至于 leetcode,也是大部分题目官方都有给出答案,也是个不错的刷题网站。你们可以两个挑选一个,或者两个都刷。

    当然,还有其他刷题的网站,不过,其他网站没刷过,不大清除如何。

    再说数据结构

    前面我主要是说了我平时都是怎么学习算法的。在数据结构方法,我只是列举了你们一定要学习链表树(二叉堆),但这是最基本的,刷题之前要掌握的,对于数据结构,我列举下一些比较重要的:

    1、链表(如单向链表、双向链表)。

    2、树(如二叉树、平衡树、红黑树)。

    3、图(如最短路径的几种算法)。

    4、队列、栈、矩阵。

    对于这些,自己一定要动手实现一遍。你可以看书,也可以看视频,新手可以先看视频,不过前期可以看视频,之后我建议是一定要看书。

    视频和书我以前有推荐过: (外部链接放了发不了文,搜索公众号“苦逼的码农”,回复“数据结构与算法”即可获取

    例如对于平衡树,可能你跟着书本的代码实现之后,过阵子你就忘记,不过这不要紧,虽然你忘记了,但是如果你之前用代码实现过,理解过,那么当你再次看到的时候,会很快就记起来,很快就知道思路,而且你的抽象能力等等会在不知不觉中提升起来。之后再学习红黑树啊,什么数据结构啊,都会学的很快。

    最最重要

    动手去做,动手去做,动手去做。重要的话说三遍。

    千万不要找了一堆资源,订好了学习计划,我要留到某某天就来去做.....

    千万不要这样,而是当你激情来的时候,就马上去干,千万不要留到某个放假日啊什么鬼了,很多这种想法的人,最后会啥也没做的。

    也不要觉得要学习的有好多啊,不知道从哪学习起。我上面说了,可以先学习最基本的,然后刷题,刷题是一个需要长期坚持的事情,一年,两年。在刷题的过程中,可以穿插和学习其他数据结构。

    个人公众号:苦逼的码农,喜欢我就关注,喜欢我的文章就更应该关注了,绝对让你有所收获。后台能回复"v2ex"送你一份资源大礼包。

    7 条回复    2018-12-07 16:59:16 +08:00
    CoderOnePolo
        1
    CoderOnePolo  
       2018-12-04 17:14:12 +08:00
    不错
    shuaidi
        2
    shuaidi  
    OP
       2018-12-04 17:15:57 +08:00
    @CoderOnePolo 谢谢。
    mathzhaoliang
        3
    mathzhaoliang  
       2018-12-04 17:29:27 +08:00
    写斐波那契数列的时候,只要了解线性递推序列的概念,知道它的寄存器包含两个状态,每一步同时更新这两个状态就可以写出非递推的代码。
    ghbaqi
        4
    ghbaqi  
       2018-12-04 17:45:24 +08:00
    扎实
    shuaidi
        5
    shuaidi  
    OP
       2018-12-04 20:51:01 +08:00
    @mathzhaoliang 是的,这个采用递推比较简单、容易想到,不过有些题就不容易想到的。我这道题只是给出一个示例。递归的很多题往往都可以采取递推的方式。
    imwhizzkid
        6
    imwhizzkid  
       2018-12-07 11:28:25 +08:00
    @shuaidi 为什么说这个采用递归比较容易想到?我看了你的答案还是没想明白为什么可以用递归?虽然验证之后确实是这样,但是我不并知道如何推理出 s(n)=s(n-1)+s(n-2)这个结论的?
    tnt666666
        7
    tnt666666  
       2018-12-07 16:59:16 +08:00 via Android
    算法并不重要,也无虚浪费过多时间刷题目,现代程序员只需懂基本排列组合即可。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1019 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 19:35 · PVG 03:35 · LAX 12:35 · JFK 15:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.