阅读 2075

小白一路走来,连续刷题三年,谈谈我的算法学习经验

大一从一个小白一路走过来,也在 leetcode 刷了几年了题,也是有点经验,也走过很多坑,在此分享我的一波经验,请耐心看完一定会有所帮助

切勿盲目刷题:刷题前的知识积累

说实话,想要提高自己的算法,我觉得就是脚踏实地着多动手去刷题,多刷题。

但是,如果你是小白,也就是说,你连常见的数据结构,如链表、树以及常见的算法思想,如递归、枚举、动态规划这些都没学过,那么,我不建议你盲目疯狂着去刷题的。而是先去找本书先去学习这些必要的知识,然后再去刷题。 因为,如果这些基础都不懂的话,估计一道题做了几个小时,然后看答案都不不懂,做题没有任何思路,这是很难受的。久而久之,估计没啥动力了,我刚开始就是这样,一道题答案看一天,然而还是不大懂,什么回溯啊,暴力啊,还不知道是啥意思。

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

1、常见数据结构:链表、树(如二叉树)。(是的,链表和二叉树是重点,图这些可以先放着)

2、常见算法思想:贪婪法、分治法、穷举法、动态规划,回溯法。(贪婪、穷举、分治是基础,动态规划有难度,可以先放着)

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

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

1、数据结构与算法分析(c 语言描述版)

我相信大部分人大学看的教程都是清华大学出版社严蔚敏写的那本书,说实话,作为初学者,那本书我没能坚持看下去,可能比较适合大佬看吧。我自己买了一本《数据结构与算法分析(c 语言描述版)》,挺薄的,不过感觉很棒,这本书让我学到了很多,个人感觉也挺容易懂的,代码实现是采用 C 语言来实现的,不是伪代码,如果你想学习数据结构,我觉得这本书是个不错的选择。班级里有挺多人看了《大话数据结构》,挺他们说也挺不错,不过我没看过。

2、挑战程序设计竞赛

这边书也是大一时看的,如果你想刷题,我挺推荐这本书,里面分初级、中级到高级。虽然每道题没有讲的特别详细,但当时都看懂了,真心不错。不过高级那部分我是没看,初级和中级看着挺舒服。也是学到挺多的,推荐给大家。

3、编程之美

不用说,很美,这本书是我今年刚入手看的,只能用强烈推荐来形容,在这本书里,学到了挺多技巧,里面列举的题也不是特别难,目前看了 80%,真香。刚开始我听别人说如果要准备面试谷歌什么的建议看,我以为很难,迟迟没买来看,不过,我看的过程中,感觉还好,相信你也能看的懂,想学习算法、刷题的,强烈推荐。

4、编程珠玑

这本老早就听别人说过了,去年看的,不过也是看了80%左右,和编程之美一样,强烈推荐,这本书里的题,说实话,感觉比编程之美有意思,

5、程序员代码面试指南:IT 名企算法与数据结构题目最优解

这本书是牛客网的左程云写的,这本书重在带你刷题,每道题的解法也是讲的挺详细的,而且,这本书是一个专题一个专题带你刷题的,从栈和队列、链表、二叉树、递归与动态规划、字符串等等。我之前的链表打卡就是从这里找的。大家可以按照自己的弱点挑着刷。对了,代码是采用 Java 实现的,不过你会 C 语言的话,一样能看懂。真心不过,递归和动态规划里面好几道题都命中这次春招笔试了,当然,类似而已。然而,那时我还没有去看这本书动态相关的专题。推荐给大家。

做个补充:这些书籍我都有保存了电子版的,不过百度云发出来经常会链接失效,我不好及时更新,不过你可以关注我的公众号:苦逼的码农,回复**“电子书“**即可获取。我的公众号也有100多原创文章,有很多是讲解算法的, 也非常欢迎你来关注,共同学习。

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

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

总结下:

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

AC不是目的,我们要追求完美

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

我觉得,在做题的时候,一定要追求完美,千万不要把一道题做出来之后,提交通过,然后就赶紧下一道。我认为这意义不大,因为一道题的解法太多了,有些解法态粗糙了,我们应该要寻找最优的方法。

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

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

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

我举道例题吧:

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

这道题我在以前的分章分析过,不懂的可以先看下之前写的:递归与动态规划---基础篇1

方法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 选定专题,连续做了七八十道,刚开始很难受, 后来就慢慢知道了套路了,一道题从两三个小时最后缩到半小时,简单的十几分钟就搞定。感觉自己对这类型的题也不惧怕的。

所以,建议你,一定要学好跳出自己的舒适区。

推荐一些刷题网站

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

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

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

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

至于leetcode,有中文版和英文版,个人建议英文版,英文版里面有各种大佬的解法分析。

leetcode有中文版

英文版

根据自己的兴趣选。

学习一些解题技巧

说实话,有些题在你没看别人的解法前,你好不知道有这么美妙优雅的解法,看了之后,卧槽,居然还可以这样。而我们在刷题的过程中,就要不断累积这些技巧,当你累计多了,你就会形成一种 神经反应,一下子就想到了某种方法。解题技巧很多,例如数组下标法、位图法、双指针等等,我自己也分享过一篇总结一些算法技巧的文章。给你举个例子吧,有时候有些技巧真让你大喊“卧槽”。

1、找出没有重复的数

给你一组整型数据,这些数据中,其中有一个数只出现了一次,其他的数都出现了两次,让你来找出一个数 。

这道题可能很多人会用一个哈希表来存储,每次存储的时候,记录 某个数出现的次数,最后再遍历哈希表,看看哪个数只出现了一次。这种方法的时间复杂度为 O(n),空间复杂度也为 O(n)了。

然而我想告诉你的是,采用位运算来做,绝对高逼格!

我们刚才说过,两个相同的数异或的结果是 0,一个数和 0 异或的结果是它本身,所以我们把这一组整型全部异或一下,例如这组数据是:1, 2, 3, 4, 5, 1, 2, 3, 4。其中 5 只出现了一次,其他都出现了两次,把他们全部异或一下,结果如下:

由于异或支持交换律和结合律,所以:

1^2^3^4^5^1^2^3^4 = (1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5。

也就是说,那些出现了两次的数异或之后会变成0,那个出现一次的数,和 0 异或之后就等于它本身。就问这个解法牛不牛逼?所以代码如下

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}
复制代码

时间复杂度为 O(n),空间复杂度为 O(1),而且看起来很牛逼。

2、m的n次方

如果让你求解 2 的 n 次方,并且不能使用系统自带的 pow 函数,你会怎么做呢?这还不简单,连续让 n 个 m 相乘就行了,代码如下:

int pow(int n){
    int tmp = 1;
    for(int i = 1; i <= n; i++) {
        tmp = tmp * m;
    }
    return tmp;
}
复制代码

不过你要是这样做的话,我只能呵呵,时间复杂度为 O(n) 了,怕是小学生都会!如果让你用位运算来做,你会怎么做呢?

我举个例子吧,例如 n = 13,则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:

m^1101 = m^0001 * m^0100 * m^1000。

我们可以通过 & 1和 >>1 来逐位读取 1101,为1时将该位代表的乘数累乘到最终结果。直接看代码吧,反而容易理解:

int pow(int n){
    int sum = 1;
    int tmp = m;
    while(n != 0){
        if(n & 1 == 1){
            sum *= tmp;
        }
        tmp *= tmp;
        n = n >> 1;
    }
    
    return sum;
}
复制代码

时间复杂度近为 O(logn),而且看起来很牛逼。

给你算法技巧,当然也可以关注我的公众号:苦逼的码农,专注与分享算法、计算机基础等相关文章,已有100多篇原创,欢迎来撩。

推荐阅读:一些常用的算法技巧总结

例如在刷题的时候,我们要学会巧用双指针、数组下标法、位运算等等技巧来解决问题,可能会有意想不到的效果。我给你再找点我之前写文章的一些例子吧:

分享一道解法巧妙的算法题

【算法技巧】位运算装逼指南

这是个长期累积的过程,我自己也精彩在我的公众号里分享一些解题的文章,感兴趣的可以关注我的公众号:苦逼的码农

再说数据结构发重要性

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

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

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

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

4、队列、栈、矩阵。

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

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

最最重要

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

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

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

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

大家也可以关注我的公众号:苦逼的码农,在我的公众号里,我也分享了很多与数据结构算法相同的文章,而且也分享了很多解题技巧。目前已分析了 100 多篇原创文章,下面是一些我觉得 很不错的文章,强烈建议阅读:

链表的重要性不言而喻,如果你把我分享的这10道题都搞懂了,那么你在链表方面算过关的了:

【链表问题】如何优雅着反转单链表

【链表问题】打卡6:三种方法带你优雅判断回文链表

【链表问题】打卡9:将单链表的每K个节点之间逆序

【链表问题】删除单链表中的第K个节点

链表问题】环形单链表约瑟夫问题

就不一道道列出来了,一共挑选了10还不错的文章

十道链表打卡汇总

我还讲解了一些常用数据结构与算法思想,每篇都通俗易懂着讲解了,被各种号所转发

1、为什么你学不会递归?告别递归,谈谈我的一些经验

2、十大排序重要性不言而喻,文章还附带了动画、讲解文章,代码 必学十大经典排序算法,看这篇就够了(附完整代码/动图/优质文章)(修订版)

3、总结了刷题过程中常用的技巧,推荐阅读:一些常用的算法技巧总结

4、用漫画的形式讲解了AVL树:【漫画】以后在有面试官问你AVL树,你就把这篇文章扔给他。

5、大量图讲解了堆的各种操作:【算法与数据结构】堆排序是什么鬼?

索性把写的一些文章链接都分享一波,大家可以挑感兴趣的看算法与数据结构系列文章

也非常欢迎大家关注公众号「苦逼的码农」里面已有100多篇原创文章,我也分享了很多视频、书籍的资源,以及开发工具,欢迎各位的关注,第一时间阅读我的文章。

如果你觉得这篇内容对你挺有启发,为了让更多的人看到这篇文章:不妨

1、点赞,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-)

2、关注我和专栏,让我们成为长期关系

3、关注公众号「苦逼的码农」,主要写算法、计算机基础之类的文章,里面已有100多篇原创文章

公众号主页
大部分的数据结构与算法文章被各种公众号转载相信一定能让你有所收获
我也分享了很多视频、书籍的资源,以及开发工具,欢迎各位的关注,第一时间阅读我的文章。

关注下面的标签,发现更多相似文章
评论