常言道「算法才是编程的灵魂」,不管是Java,python,还是PHP,都跨不过算法这个门
王国维先生在《人间词话》中写道:古今之成大事业、大学问者,必经过三种境界:“昨夜西风凋碧树。独上高楼,望尽天涯路。”此第一境也。“衣带渐宽终不悔,为伊消得人憔悴。”此第二境也。“众里寻他千百度,蓦然回首,那人却在,灯火阑珊处。”此第三境也。算法的学习之道也是如此。
从一个算法萌新入门,第一步便在于打牢根基。推荐阅读书籍:
1.《算法第4版》-RobertSedgewick
适合初学者入门
2.《大话数据结构》-程杰3.《算法图解》-AdityaBhargava
《大话数据结构》和《算法图解》这两本书的特点是有趣、易理解,也非常适合初学者。
4.《数据结构和算法分析-C语言描述》-MarkAllenWeiss
需要有一定C语言基础
进阶:
1.《编程珠玑》-JonBentley
本书讨论了程序设计人员面对一系列的实践问题以及处理问题的措施(处理计划的代码以C/C++言语编写)。书当选取了许多具有典型意义的复杂编程和算法问题,并论述和总结了许多共同精妙的设计准绳、考虑和处理问题的办法以及适用的程序设计技巧。
2.《算法导论》-Cormen,T.H.
《算法导论》的特点是全面,它是一本算法的百科全书,着重在于开阔算法视野,适合有一定算法基础后再去学习。
1.常用的数据结构:数组、字符串、链表、树(如二叉树)等
2.常用的算法:分治、贪心、穷举、动态规划、回溯、二分算法、深度优先搜索等
可搭配力扣的题目进行练习
70.爬楼梯
动态规划算法的经典题目,通过此题目可以了解状态、边界条件、状态转移方程等基本概念。
112.路径总和
深度优先算法的入门题目,递归实现和迭代实现都不难,可以学习到深度优先算法的层层嵌套搜索、找到答案或到达边界停止的基本解题思路。
35.搜索插入位置
二分算法的典型题目,使用二分算法的解题模板可以轻松解决,二分算法的算法思想清晰明确,一通百通。
169.求众数
944.删列造序
这是一道贪心算法的简单题目,贪心算法理解简单,上手容易,适合作为初学者掌握的第一个算法。
学习算法理论如同阅读了一本武功秘籍,然而仅仅掌握理论是不够的,接下来就要进入到实际练习阶段。
在这个阶段,可以尝试练习力扣上的中等题目,中等题目基本上也只会使用一种算法,加上一些特殊的限制,好比让你在学习了直拳的理论后衍生出左勾拳和右勾拳。推荐练习题目有:
1048.最长字符串链
分析题目可知,要求出答案必须遍历所有可能的词链,动态规划算法在其中起备忘录的作用,用于记录已经算过的答案,减少计算次数。
47.全排列II
这道题是46.全排列的加强版,全排列I的题目是:给定一个没有重复数字的序列,返回其所有可能的全排列。使用深度优先搜索算法即可解决。本题在其基础上加强了难度,有两种方法可解。第一种方法最简单,直接用全排列I的答案去重即可,第二种方法是先将数组排序,全排列时遇到重复数字则跳过,这样的剪枝优化可以减少遍历次数,提高算法效率。
40.组合总和II
深度优先搜索算法衍生出来的回溯算法,同样用到47题的剪枝优化思想:相同数字只允许递归第一个。
89.格雷编码
动态规划算法的实际应用之一。
79.单词搜索
深度优先搜索的中级应用,使用单独数组标记已使用过的元素,这也是DFS中较为常见的做法,难点在于将标记数组复原的时机,需要反复练习,熟练掌握。
当你把每一类算法的中等题目刷起来得心应手时,不妨开始尝试困难题目的练习。困难题目总是融合两种或两种以上算法,或是加深难度的经典算法,如二维甚至三维动态规划。练习困难题目好比同时用上左勾拳和扫堂腿,不仅让思维酣畅淋漓,在每次AC之后还会带来无与伦比的成就感。推荐练习题目有:
679.24点游戏
只有4张牌,且只能执行4种操作。即使所有运算符都不进行交换,最多也只有12*6*2*4*4*4=9216种可能性,这使得我们可以尝试所有这些可能,如果用深度优先搜索算法则需要费一番功夫。
124.二叉树中的最大路径和
首先,考虑实现一个简化的函数:计算每个节点及其子树对路径和的最大贡献。再考虑第二点:最大路径不一定包括根节点。这意味着我们在每一步都检查哪种选择更好:是继续当前路径或者以当前节点作为最高节点计算新的路径。
410.分割数组的最大值
二分算法和贪心算法的综合练习,仔细分析可知其单调关系:数组和的最大值越小,分组数越大。并且数组和的范围是可以确定的。根据此特性,可以将题目转换为:当子数组的和最大为maxSum时,至少需要分多少组,能否在最多m组的限制范围内完成分割。在每次分割时,采用贪心策略,尽可能多的放置元素,直到一组放不下,再另起一组。如果满足分割条件,记录当前值,利用二分法,缩小子数组总和。否则扩大子数组总和,直到找到最佳答案。
动图演示如下:
希尔排序算法较为晦涩难懂,而且并不是最优的排序算法,现在已经被后来的快速排序算法给淘汰了。然而不可否认希尔对排序算法的演进具有开创性贡献,在攀越算法高峰的路上,每一步都走得战战兢兢,我们只有铭记这些伟大的引路人,以此激励自己不断前行。
我给大家整理了一个学习计划,可以保存下图进行学习:
现在网上有很多资源、博客、论坛可供我们更方便地学习知识片段。然而这种类似兵来将挡、水来土掩般的学习方法虽然有用,却并不特别的好。这里推荐大家在网上寻找一些系统的学习教程,以帮助自己由浅入深,一路成长。
力扣将TopInterviewQuestions里比较新的题目按照类别进行了整理,以供大家按模块练习。
最后呢,这里希望各位小伙伴们都能够学有所成,这里呢准备了些福利给大家。
这个图书学习路径出自,leecode全站第一的人之手。什么?看书枯燥?来看视频课程吧。
课程目标:深入掌握java高级数据结构,写出高品质代码,突破技术瓶颈