怎么学好数据结构？
从小白一路走过来，从大一连续刷过好几年题，看过挺多书，踩过挺多坑，也涨了一些经验，姑且在这里分析一波对数据结构与算法 的学习经验，请耐心看完，相信对你会有所帮助。不然你打我 先撸个目录，方便你们查看 1、书籍+视频推荐 2、数据集结构与算法核心内容总结 3、优质文章推荐 4、算法该如何刷题 5、总结 ----------------2021.9.1更新-------------- 这里有个可以白嫖的项目，推荐给大家 数据结构与算法相关的书籍应该是我看的最多的一种数据吧，从大一到现在，从未间断过，下面就介绍下从大一到现在都看过哪些自认为优秀的书籍，注意，我不知道适不适合你，但我觉得看的过程中很舒服。 1、数据结构与算法分析（c 语言描述版）   我相信大部分人大学看的教程都是清华大学出版社严蔚敏写的那本书，说实话，作为初学者，那本书我没能坚持看下去，可能比较适合大佬看吧。我自己买了一本《数据结构与算法分析（c 语言描述版）》，挺薄的，不过感觉很棒，这本书让我学到了很多，个人感觉也挺容易懂的，代码实现是采用 C 语言来实现的，不是伪代码，如果你想学习数据结构，我觉得这本书是个不错的选择。班级里有挺多人看了《大话数据结构》，挺他们说也挺不错，不过我没看过。 2、挑战程序设计竞赛   这边书也是大一时看的，学习算法，刷一些题是必须的，所谓3分理论7分实践。如果你想刷题，我挺推荐这本书，里面分初级、中级到高级。虽然每道题没有讲的特别详细，但当时都看懂了，真心不错。不过高级那部分我是没看，初级和中级看着挺舒服。也是学到挺多的，推荐给大家。 3、算法（第四版）  这本书估计是卖的最火的一本书吧，采用 Java 语言来实现的，不过在看这本书之前，我觉得你得要有一定的算法基础，例如你得知道啥是队列，啥是栈。我不认为这是本入门书籍，所以，你可以先学习 我上门推荐的那些书，有一定的基础之后，再来学习这本。这本书主要是用大量的图片来演示算法，让人觉得比较友好。 4、编程之美  不用说，很美，这本书是我今年刚入手看的，只能用强烈推荐来形容，在这本书里，学到了挺多技巧，里面列举的题也不是特别难，目前看了 80%，真香。刚开始我听别人说如果要准备面试谷歌什么的建议看，我以为很难，迟迟没买来看，不过，我看的过程中，感觉还好，相信你也能看的懂，想学习算法、刷题的，强烈推荐。 5、编程珠玑  这本老早就听别人说过了，去年看的，不过也是看了80%左右，和编程之美一样，强烈推荐，这本书里的题，说实话，感觉比编程之美有意思， 当然，数据结构与算法的还有很多优秀的书籍，我自己也看过不少，不过以上这些，我觉得很不错。自己也买过算法导论等，不过，没看的下去。 书单给大家整理好了 作为初学者，学习算法是一个相对比较艰难的过程，比起看书，可能看视频会相对好理解点，当然，这里引人而异，有些人喜欢看书不喜欢看视频，这里主要是根据你自身来选择了。 说起视频，我自己看的也不多，我是属于喜欢看书的那一种，不过我觉得这些这些视频还不错，推荐给大家。 牛客网有个初级和进阶班的视频，我觉得很不错，不过我看过进阶班的，初级班的没看过，感觉还不错：  另外，学习算法的过程中，有业余时间也可以学一学项目，毕竟很多算法最终都落地到项目上滴，这里给大家推荐一个   1、时间复杂度 2、空间复杂度 一般最先接触的就是时间复杂度和空间复杂度的学习了，这两个概念以及如何计算，是必须学的，也是必须最先学的，主要有最大复杂度、平均复杂度等，直接通过博客搜索学习即可。 文章推荐： 算法分析神器—时间复杂度 1、线性表 不用说，链表、列表必须，不过重点是链表。 三分钟基础数据结构：如何轻松手写链表？ 以后有面试官问你「跳跃表」，你就把这篇文章扔给他 2、栈与队列 特别是优先队列，再刷题的时候，还是经常用到的，队列与栈，是最基本的数据结构，必学。可以通过博客来学习。相关文章： 三分钟基础知识：什么是栈？ 二叉堆是什么鬼？ 【算法与数据结构】堆排序是什么鬼？ 3、哈希表（必学） 哈希表相关的，推荐通过博客来学习，推荐文章： Hash冲突之开放地址法 4、树 树相关是知识还是挺多的，建议看书，可以看《算法第四版》。相关文章 高频面试题：什么是B树？为啥文件索引要用B树而不用二叉查找树？ 【漫画】以后在有面试官问你AVL树，你就把这篇文章扔给他。 腾讯面试题：有了二叉查找树、平衡树为啥还需要红黑树？ 【面试被虐】游戏中的敏感词过滤是如何实现的？ 学这些数组结构时，可以看看在项目中这些数据结果是如何体现的，这里有个不错的项目： 5、数组 树状数组其实我也没学过，，，， 1、十大排序算法 对于十大算法的学习，假如你不大懂的话，那么我还是挺推荐你去看书的，因为看了书，你可能不仅仅知道这个算法怎么写，还能知道他是怎么来的。推荐书籍是《算法第四版》，这本书讲的很详细，而且配了很多图演示，还是挺好懂的。 推荐文章： 必学十大经典排序算法，看这篇就够了(附完整代码/动图/优质文章)(修订版) 2、图论算法 图还是比较难的，不过我觉得图涉及到的挺多算法都是挺实用的，例如最短路径的计算等，图相关的，我这里还是建议看书的，可以看《算法第四版》。 漫画：什么是 “图”？（修订版） 漫画：深度优先遍历 和 广度优先遍历 漫画：图的 “最短路径” 问题 漫画：Dijkstra 算法的优化 漫画：图的 “多源” 最短路径 3、搜索与回溯算法 这方便的只是都是一些算法相关的，我觉得如果可以，都学一下。像贪心算法的思想，就必须学的了。建议通过刷题来学习，leetcode 直接专题刷。 4、动态规划 我觉得动态规划是最难的一个算法思想了，记得当初第一次接触动态规划的时候，是看01背包问题的，看了好久都不大懂，懵懵懂懂，后面懂了基本思想，可是做题下不了手，但是看的懂答案。一气之下，再leetcdoe专题连续刷了几十道，才掌握了动态规划的套路，也有了自己的一套模板。不过说实话，动态规划，是考的真他妈多，学习算法、刷题，一定要掌握。这里建议先了解动态规划是什么，之后 leetcode 专题刷，反正就一般上面这几种题型。后面有时间，我也写一下我学到的套路，有点类似于我之前写的递归那样，算是一种经验。也就是我做题时的模板，不过感觉得写七八个小时，，，，，有时间就写。之前写的递归文章：为什么你学不会递归？告别递归，谈谈我的一些经验 5、字符匹配算法 我写过两篇字符串匹配的文章，感觉还不错，看了这两篇文章，我觉得你就差不多懂 kmp 和 Boyer-Moore 了。 字符串匹配Boyer-Moore算法：文本编辑器中的查找功能是如何实现的？ 6、流相关算法 这方面的一些算法，我也只了解过一些，感兴趣的可以学习下。 对于上面设计到的算法，我都提供了感觉还不错的文章，建议大家收藏，然后可以利用零碎的时间进行阅读，有些人可能会觉得上面的算法太多，说实话，我觉得不多，特别是对于在校生的，上面涉及到的算法可以不用很懂，但至少得了解。大家也可以关注我的微信公众号『帅地玩编程』，阅读更多原创算法文章。 至于书籍的话，如果你连基本数据结构都还不懂的，建议看《数据结构与算法》相关书籍，例如《大话数据结构》、《数据结构与算法分析》。如果你有一定的基础，例如知道链表，栈，队列，那么可以看《算法第四版》，不过这本书是用 Java 实现的，不过我觉得你只要学过 C，那么可以看的懂。 这些算法的学习，虽然你觉得学了没有什么用，但还是那些话，它对你的影响是潜意识的，它可以给你打下很深厚的基础内功，如果你想走的更远，那么我推荐学习，标注必学的，那么我觉得，你是真的需要抽时间来学习下，标注原理与应用的，代表你可以不知道怎么用代码实现，但是必得知道它的实现原理以及应用。 有空也可以看一看项目 哦 关于算法的，我再整理了一些我觉得值得一读的文章，具体往下看： 上面只是介绍了一些书籍和视频，从另一个角度讲，书籍和视频只是一个工具，从大一学习算法到现在，刷了很多题，也是积累了一些经验，下面跟大家分享下我的经验吧，请耐心看完，相信你会有所收获 说实话，想要提高自己的算法，我觉得就是脚踏实地着多动手去刷题，多刷题。 但是，如果你是小白，也就是说，你连常见的数据结构，如链表、树以及常见的算法思想，如递归、枚举、动态规划这些都没学过，那么，我不建议你盲目疯狂着去刷题的。而是先去找本书先去学习这些必要的知识，然后再去刷题。 因为，如果这些基础都不懂的话，估计一道题做了几个小时，然后看答案都不不懂，做题没有任何思路，这是很难受的。久而久之，估计没啥动力了，我刚开始就是这样，一道题答案看一天，然而还是不大懂，什么回溯啊，暴力啊，还不知道是啥意思。 也就是说，假如你要去诸如leetcode这些网站刷题，那么，你要先具备一定的基础，这些基础包括： 1、常见数据结构：链表、树(如二叉树)。（是的，链表和二叉树是重点，图这些可以先放着） 2、常见算法思想：贪婪法、分治法、穷举法、动态规划，回溯法。（贪婪、穷举、分治是基础，动态规划有难度，可以先放着） 以上列出来的算是最基本的吧。就是说你刷题之前，要把这些过一遍再去刷题。如果你连这些最基本的都不知道的话，那么你再刷题的过程中，会很难受的，思路也会相对比较少。 总之，千万不要急，先把这些基本的过一遍，力求理解，再去刷题。这些知识点，我上面已经给你们推荐了对应的书籍和视频了，就不继续说了。 所以你们千万别指望以为自己把这些思想学完之后刷题会很牛，只有多刷题，只有多动手实践，你的灵敏度才会提高起来。 总结下： 提高数据结构与算法没啥捷径，最好的捷径就是多刷题。但是，刷题的前提是你要先学会一些基本的数据结构与算法思想。 如何刷题？如何对待一道算法题？ 我觉得，在做题的时候，一定要追求完美，千万不要把一道题做出来之后，提交通过，然后就赶紧下一道。我认为这意义不大，因为一道题的解法太多了，有些解法态粗糙了，我们应该要寻找最优的方法。 算法能力的提升和做题的数量是有一定的关系，但并不是线性关系。也就是说，在做题的时候，要力求一题多解，如果自己实在想不出来其他办法了，可以去看看别人是怎么做的，千万不要觉得模仿别人的做法是件丢人的事。 我做题的时候，我一看到一道题，可能第一想法就是用很粗糙的方式做，因为很多题采用暴力法都会很容易做，就是时间复杂度很高。之后，我就会慢慢思考，看看有没其他方法来降低时间复杂度或空间复杂度。最后，我会去看一下别人的做法，当然，并不是每道题都会这样执行。 衡量一道算法题的好坏无非就是时间复杂度和空间复杂度，所以我们要力求完美，就要把这两个降到最低，令他们相辅相成。 我举道例题吧： 问题： 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？ 这道题我在以前的分章分析过，不懂的可以先看下之前写的：递归与动态规划---基础篇1 方法1：：暴力递归 这道题不难，或许你会采取下面的做法： 这种做法的时间复杂度很高，指数级别了。但是如果你提交之后侥幸通过了，然后你就接着下一道题了，那么你就要好好想想了。 方法二：空间换时间 力求完美，我们可以考虑用空间换时间：这道题如何你去仔细想一想，会发现有很多是重复执行了。所以可以采取下面的方法： 这样，可以大大缩短时间。也就是说，当一道题你做了之后，发现时间复杂度很高，那么可以考虑下，是否有更好的方法，是否可以用空间换时间。 方法三：斐波那契数列 实际上，我们可以把空间复杂度弄的更小，不需要HashMap来保存状态： 我弄这道题给你们看，并不是在教你们这道题怎么做，而是有以下目的： 1、在刷题的时候，我们要力求完美。 2、我想不到这些方法啊，怎么办？那么你就可以去看别人的做法，之后，遇到类似的题，你就会更有思路，更知道往哪个方向想。 3、可以从简单暴力入手做一道题，在考虑空间与时间之间的衡量，一点点去优化。 什么叫舒适区？在刷题的时候，可能有一类题是你比较懂的，你每次一看就有思路，然后半个小时就撸好代码，提交代码，然后通过了，然后，哇，又多刷了一道题，心里很舒服。 但是，记住，前期你可以多刷这种题练手，提升自己的乐趣，但，我还是建议你慢慢跳出舒适区，去做一些自己不擅长的题，并且找段时间一直刷这种题。例如，我觉得我在递归方面的题还是挺强的， 但是，我对动态规划的题，很菜，每次都要想好久，每次遇到这种题都有点害怕，没什么信心。不过有段时间我觉得只刷动态规划的题，直接在 leetcode 选定专题，连续做了七八十道，刚开始很难受， 后来就慢慢知道了套路了，一道题从两三个小时最后缩到半小时，简单的十几分钟就搞定。感觉自己对这类型的题也不惧怕的。 所以，建议你，一定要学好跳出自己的舒适区。 我一般是在leetcode和牛客网刷题，感觉挺不错，题目难度不是很大。 在牛客网那里，我主要刷剑指Offer,不过那里也有个在线刷leetcode，不过里面的题量比较少。牛客网刷题有个非常方便的地方就是有个讨论区，那里会有很多大佬分享他们的解题方法，不用我们去百度找题解。所以你做完后，实在想不出，可以很方便着去看别人是怎么做的。 至于leetcode，也是大部分题目官方都有给出答案，也是个不错的刷题网站。你们可以两个挑选一个，或者两个都刷。 当然，还有其他刷题的网站，不过，其他网站没刷过，不大清除如何。 至于leetcode，有中文版和英文版，个人建议英文版，英文版里面有各种大佬的解法分析。 leetcode有中文版 英文版 根据自己的兴趣选。 说实话，有些题在你没看别人的解法前，你好不知道有这么美妙优雅的解法，看了之后，卧槽，居然还可以这样。而我们在刷题的过程中，就要不断累积这些技巧，当你累计多了，你就会形成一种 神经反应，一下子就想到了某种方法。解题技巧很多，例如数组下标法、位图法、双指针等等，我自己也分享过一篇总结一些算法技巧的文章。给你举个例子吧，有时候有些技巧真让你大喊“卧槽”。 这道题可能很多人会用一个哈希表来存储，每次存储的时候，记录 某个数出现的次数，最后再遍历哈希表，看看哪个数只出现了一次。这种方法的时间复杂度为 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 异或之后就等于它本身。就问这个解法牛不牛逼？所以代码如下 时间复杂度为 O(n)，空间复杂度为 O(1)，而且看起来很牛逼。 如果让你求解 m 的 n 次方，并且不能使用系统自带的 pow 函数，你会怎么做呢？这还不简单，连续让 n 个 m 相乘就行了，代码如下： 不过你要是这样做的话，我只能呵呵，时间复杂度为 O(n) 了，怕是小学生都会！如果让你用位运算来做，你会怎么做呢？ 我举个例子吧，例如 n = 13，则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为: m^1101 = m^0001 * m^0100 * m^1000。 我们可以通过 & 1和 >>1 来逐位读取 1101，为1时将该位代表的乘数累乘到最终结果。直接看代码吧，反而容易理解： 时间复杂度近为 O(logn)，而且看起来很牛逼。 推荐阅读：一些常用的算法技巧总结 例如在刷题的时候，我们要学会巧用双指针、数组下标法、位运算等等技巧来解决问题，可能会有意想不到的效果。我给你再找点我之前写文章的一些例子吧： 分享一道解法巧妙的算法题 【算法技巧】位运算装逼指南 这是个长期累积的过程，我自己也精彩在我的公众号里分享一些解题的文章，感兴趣的可以关注我的公众号：帅地玩编程。 前面我主要是说了我平时都是怎么学习算法的。在数据结构方法，我只是列举了你们一定要学习链表和树(二叉堆)，但这是最基本的，刷题之前要掌握的，对于数据结构，我列举下一些比较重要的： 1、链表（如单向链表、双向链表）。 2、树（如二叉树、平衡树、红黑树）。 3、图（如最短路径的几种算法）。 4、队列、栈、矩阵。 对于这些，自己一定要动手实现一遍。你可以看书，也可以看视频，新手可以先看视频，不过前期可以看视频，之后我建议是一定要看书。 例如对于平衡树，可能你跟着书本的代码实现之后，过阵子你就忘记，不过这不要紧，虽然你忘记了，但是如果你之前用代码实现过，理解过，那么当你再次看到的时候，会很快就记起来，很快就知道思路,而且你的抽象能力等等会在不知不觉中提升起来。之后再学习红黑树啊，什么数据结构啊，都会学的很快。 动手去做，动手去做，动手去做。重要的话说三遍。 千万不要找了一堆资源，订好了学习计划，我要留到某某天就来去做..... 千万不要这样，而是当你激情来的时候，就马上去干，千万不要留到某个放假日啊什么鬼了，很多这种想法的人，最后会啥也没做的。 也不要觉得要学习的有好多啊，不知道从哪学习起。我上面说了，可以先学习最基本的，然后刷题，刷题是一个需要长期坚持的事情，一年，两年。在刷题的过程中，可以穿插和学习其他数据结构。 