程序员必须掌握哪些算法？

APSchmidt · 发表于 2021-7-10 15:17

高赞把数据结构到基础算法都总结得很清楚啦~
想要在学习的过程中加深的对算法的记忆和理解，还是要理论实践两手抓。
这里就介绍几个田纳西大学助理教授奥斯汀·亨利（Austin Z. Henley）推荐的练手项目，其中涉及的算法、要点，下文会加粗。
文本编辑器

不使用GUI框架中内置的文本框组件，要如何搭建支持光标移动、选择、插入和删除操作的文本框？
这个项目中，存在两个主要挑战：

不要小看这些基础的功能，其中有许多细节值得注意。比如当光标位于文本当中，按下向上箭头，光标会移动到何处？
△图源：Austin Z. Henley
如果你觉得这太简单，还有进阶测试：

最后总结一下知识要点：

用于存储文本的数据结构：数组，rope，gap buffer，piece table

文本光标的行为和实现

撤销/重做的设计模式：记忆，命令

分离文本视觉和记忆的抽象

别忘了还有拓展阅读哟：

2D游戏-太空侵略者

即使是最简单的游戏也需要考虑数据结构和设计模式。
在这个项目中，你的任务是从头到尾实现一个定义明确的游戏。最好使用SDL，SFML，PyGame这样的2D图形库。
△图源：Austin Z. Henley
第一步，创建对象移动的效果。
第二步，了解有关游戏循环的所有信息。游戏实际上是在绘图、获取用户输入和处理游戏逻辑之间循环。
第三步，处理用户输入。
第四步，学习如何创建和管理所有游戏对象及其状态。比如如何生成动态数量的敌人。
第五步，学习如何应用游戏的逻辑。子弹头位置何时更新？什么时候会有更多敌人出现在屏幕上？怎么判定敌人被干掉了？游戏何时结束？
甚至，在进阶阶段，你还可以考虑引入AI，来制造更加“智能”的敌人。
编译器-Tiny BASIC

从头开始编写一种非常小的类似于BASIC的语言编译器，然后将其编译为任何其他语言。比如，用Python编写可以输出C#代码的Tiny BASIC编译器。
△图源：Austin Z. Henley
知识点：

词法分析

句法分析

递归下降解析

抽象语法树

语义分析

优化passes

代码生成

迷你操作系统

从这个项目开始，难度就加大了。
操作系统依赖于硬件，因此入门门槛比较高。但这个项目可以帮助你更好地理解计算机底层都发生了什么。
作者亨利推荐了一本免费电子书《使用Rust构建RISC-V操作系统》作为入门教材（地址见文末）。
△图源：Austin Z. Henley
知识点：

交叉编译

Bootloading

BIOS中断

x86模式

内存管理和分页

排程（Scheduling）

文件系统

如果以上四个项目，你都觉得so easy，那么就来尝试一下最后这两个高难度项目吧。
电子表格

电子表格应用程序（如Excel）将文本编辑器和编译器的挑战结合在了一起。
在这个项目中，你需要学会如何在内存中表示单元格内容，并实现用于方程式的编程语言解释器。
电子游戏机模拟器

这是一个操作系统+编译器的二合一挑战项目。
挑战内容是，编写一个虚拟机，让虚拟机可以像真实的CPU和其他硬件组件一样运行。
亨利的建议，是从简单的虚拟控制台入手，比如CHIP-8。
网友建言献策

博客一出，在Hacker News、Reddit上受到了广大码农们的欢迎。
有网友说：

这些项目能让我接触到完全不同的领域和问题，比我日常的工作更能激励我。

并且，网友们纷纷建言献策，又推举出好几个优质上手项目：

所以，这些项目是否激发了你的灵感？
Talk is cheap. Show me the code. 快动手练起来吧~
传送门

博客地址：
http://web.eecs.utk.edu/~azh/blog/challengingprojects.html
Hacker News讨论（内含更多项目推荐）：
https://news.ycombinator.com/item?id=21790779
《使用Rust构建RISC-V操作系统》：
http://osblog.stephenmarz.com/index.html
—完—
@量子位 · 追踪AI技术和产品新动态
深有感触的朋友，欢迎赞同、关注、分享三连&#39;&#39;

RecursiveFrog · 发表于 2021-7-10 15:27

心率算法：

注意：由于最大加班心率是一个基于生理条件的心跳极限的估算值，故实际强度要因人而宜，对于初习者通常可保持在60～65%MHR即可。如果不顾自己的身体条件一味追求高强度加班，则将不利于健康。

https://www.zhihu.com/video/1233050980779790336
代码诚可贵，生命价更高！程序员同行们一定要注意身体，我们一定要熬到国家“1024程序员节”法定节假日那一天呀！！！！！！
正经算法：
2020版数据结构与算法
2020版数据结构与算法（资料网盘）提取码：jkg9
让数据结构不再难懂，让算法不再难写
让数据结构不再难懂，让算法不再难写（资料网盘）提取码：qca8
C语言数据结构培养架构师思维
C语言数据结构培养架构师思维（资料网盘）密码：4wi6
互联网巨头公司面试题目之二叉树数据结构与算法
互联网巨头公司面试题目之二叉树数据结构与算法（资料网盘）提取码：j8i0

jquave · 发表于 2021-7-10 15:37

最重要的是如何找到适用的算法。

比如我最近做的东西是有机物结构式的搜索，用户输入一个结构式，软件从一个巨大的（一亿个已知结构）数据库中返回和用户输入最相似的结构出来。例如我输入

它返回

等。

使用搜索引擎是 Elastic Search（因为我已经搭了一个搜其他属性的）。限时 1s。

mypro334 · 发表于 2021-7-10 15:45

更新：
有很多朋友私信问我Python学习有没有什么好的资料，我给大家找了几门不错的免费课，想学的可以看看。
《Python入门教程》
Python入门教程--Python视频教程-编程语言-CSDN学院《Python初级入门精讲》
Python初级入门精讲--Python视频教程-编程语言-CSDN学院《Python爬虫开发》
Python爬虫开发--Python视频教程-编程语言-CSDN学院《Python实战编程》
Python实战编程--Python视频教程-编程语言-CSDN学院《1小时掌握Python爬虫+高效学习法则》
1小时掌握Python爬虫+高效学习法则--Python视频教程-编程语言-CSDN学院

原回答：
【收藏是点赞的4倍，你们是要闹哪样！】
程序员必须要掌握的十大经典算法
算法一：快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
算法步骤：
1 从数列中挑出一个元素，称为 “基准”（pivot），
2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

算法二：堆排序算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。
算法步骤：
创建一个堆H[0..n-1]
把堆首（最大值）和堆尾互换
3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4. 重复步骤2，直到堆的尺寸为1

算法三：归并排序

归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤：
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

算法四：二分查找算法

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。
搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。

算法五：BFPRT(线性查找算法)

BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂度，五位算法作者做了精妙的处理。

算法步骤：
1. 将n个元素每5个一组，分成n/5(上界)组。
2. 取出每一组的中位数，任意排序方法，比如插入排序。
3. 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。
4. 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。
5. 若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。
终止条件：n=1时，返回的即是i小元素。

算法六：DFS（深度优先搜索）

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

深度优先遍历图算法步骤：
1. 访问顶点v；
2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
上述描述可能比较抽象，举个实例：
DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。
接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

算法七：BFS(广度优先搜索)

广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

算法步骤：
1. 首先将根节点放入队列中。
2. 从队列中取出第一个节点，并检验它是否为目标。
如果找到目标，则结束搜寻并回传结果。
否则将它所有尚未检验过的直接子节点加入队列中。
3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
4. 重复步骤2。

算法八：Dijkstra算法

戴克斯特拉算法（Dijkstra’s algorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
该算法的输入包含了一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合，而边的权重则由权重函数 w: E → [0, ∞] 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负权重（weight）。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知有 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra算法是目前已知的最快的单源最短路径算法。

算法步骤：
1. 初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值
若存在<v0,vi>，d(V0,Vi)为<v0,vi>弧上的权值
若不存在<v0,vi>，d(V0,Vi)为∞
2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S
3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

算法九：动态规划算法

动态规划（Dynamic programming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

关于动态规划最经典的问题当属背包问题。
算法步骤：
1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

算法十：朴素贝叶斯分类算法

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况下，如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。

朴素贝叶斯分类器依靠精确的自然概率模型，在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法，换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。
_________________________________________________________________________________________
公号：聊聊Python，感兴趣的可以来找我玩，一起来聊聊Python这点事~
作者：lxlmycsdnfree
链接：https://blog.csdn.net/lxlmycsdnfree/article/details/78881146
希望能对你有用

Ylisar · 发表于 2021-7-10 15:46

上大学的时候，老师一直跟我们强调：“算法才是编程的灵魂”，由此可见算法到底有多重要，那么程序员应该要掌握哪些算法呢？
为了让大家有一个清晰的认识，我画了一张脑图，罗列出了个人觉得比较重要的且需要掌握的算法和数据结构，同时还整理对应的学习文章和书籍分享给大家，如果看完觉得有用的话记得双击点个赞哦，下面开始上干货：

1、数据结构

数据结构研究的内容就是如何按一定的逻辑结构，把数据组织起来，一般学习算法都是先从数据结构开始学习，先根据实际问题确定数据结构，然后在数据结构的基础上进行算法设计。
常见的数据结构有：

栈（Stack）：

队列（Queue）：

数组（Array）：

链表（Linked List）：

树（Tree）：

图（Graph）：

堆（Heap）：

散列表（Hash table）：

2、常用基础算法

常用的基础算法包括：分治算法、贪心算法、动态规划算法、二分查找算法和分支界限算法等，下面列举每个算法的详细教程：
五大常用算法之：分治算法
五大常用算法之：贪心算法
五大常用算法之：动态规划算法
五大常用算法之：二分查找算法
五大常用算法之：分支限界法
3、排序算法

排序算法最经典的莫过于八大排序算法了，分别是：插入排序、冒泡排序、选择排序、希尔排序、堆排序、归并排序、快速排序、桶式排序。
排序算法很重要，考试和面试都会考察，而且是必考，我把八大排序算法的原理和代码都整理出来了，看下面这篇文章就够：
谭庆波：八大经典排序算法详解4、搜索算法

搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题解的一种方法。现阶段常用的搜索算法有：枚举算法、深度优先搜索、广度优先搜索、剪枝算法、回溯算法等，以下是详细教程：
搜索算法之：枚举算法
DFS（深度优先搜索）和BFS(广度优先搜索)
搜索算法之：剪枝算法
搜索算法之：回溯算法
5、树与图

树与图相关是知识还是挺多的，而且很重要，想全面了解可以看书，推荐看《图解算法》，后面有下载链接。下面也整理了一些相关文章：
数据结构与算法——图最短路径
数据结构与算法：三十张图弄懂「图的两种遍历方式」
数据结构与算法——最小生成树
几道和「二叉树」有关的算法面试题
关键路径算法详解
大话数据结构-多路查找树（B树）_小地盘的诺克萨斯-CSDN博客_多路查找树
6、优秀的算法书

在这里我也整理了一份由易到难的算法学习书单（附下载链接），希望能对大家在学习算法和找工作有所帮助！
1、《我的第一本算法书》

这本书是京都大学一个计算机教授和朋友联合出品的动画讲解算法的App 所衍生出来的书籍，非常适合新手朋友们。里面没有枯燥的理论和复杂的公式，而是通过大量的步骤图帮助读者加深对数据结构原理和算法执行过程的理解，便于学习和记忆。将本书作为算法入门的第一步，是非常不错的选择。

2、《趣学算法》

本书从算法之美娓娓道来，没有高深的原理，也没有枯燥的公式，通过趣味故事引出算法问题，包含50多个实例及完美图解，结合学生提问，分析算法本质，并给出代码实现的详细过程和运行结果。本书可作为程序员的学习用书，也适合从未有过编程经验但又对算法有强烈兴趣的初学者使用，同时也可作为高等院校计算机、数学及相关专业的师生用书和培训学校的教材。

3、《啊哈！算法》

《啊哈！算法》一切以实际应用为出发点，通过幽默的语言配以可爱的插图来讲解算法。其中涉及的数据结构有栈、队列、链表、树、并查集、堆和图等；涉及的算法有排序、枚举、深度和广度优先搜索、图的遍历，当然还有图论中不可以缺少的四种最短路径算法、两种最小生成树算法、割点与割边算法、二分图的最大匹配算法等。

4、《图解算法》

这是一本像小说一样有趣的算法入门书，示例丰富，图文并茂，以让人容易理解的方式阐释了算法，旨在帮助程序员在日常项目中更好地发挥算法的能量。书中的前三章将帮助你打下基础，带你学习二分查找、大O表示法、两种基本的数据结构以及递归等。余下的篇幅将主要介绍应用广泛的算法。

5、《剑指offer》

这本书大家一定如雷贯耳吧，基本上只要你是程序员就一定会用到这本书，书里面剖析了50个典型的程序员面试题，从基础知识、代码质量、解题思路、优化效率和综合能力五个方面系统整理了影响面试的5个要点，是程序员找工作必备的一本算法书。

6、《算法导论》

这本书真的称得上是算法领域的“圣书”了，如果把它从头到尾看完并且搞明白了，那么恭喜你，年入百万不是梦！

最后

学习算法的过程，是非常好的训练机器程序思维的过程，所以，千万不要被动地记忆，要多辩证地思考，而且一定一定要在看懂之后自己用自己喜欢的编程语言实现一遍，一定要亲自实现一遍呀！！！这一点太重要了。
如果你一直这么坚持做，你会发现，你的编程水平会越来越高，写的代码会越来越艺术，你会不由自主地考虑到很多性能方面的事情，时间复杂度、空间复杂度非常高的垃圾代码出现的次数也就会越来越少。
加油！！！

super1 · 发表于 2021-7-10 15:48

算法是程序的灵魂——编程从本质上来说就是算法加数据结构，而算法是编程思想的核心部分。
当前程序员的岗位划分逐渐细化。对于研发级程序员来说，掌握算法是完成岗位开发任务的基础，而对于应用级程序员来说，掌握算法是进行岗位升级的重要基础。
小编建议程序猿们从以下几个方面审视或提升或入门算法知识结构——
基础部分

关于排序　

关于查找

在应用中可以重点学习：字典类用例、索引类用例和稀疏向量
关于图

关于字符串

以下从在线题库、在线提交程序源代码等维度推荐一些优秀的网站，希望能对题主有所帮助。
一、在线题库
算法学习，本质上是学习一门语言。学习语言的要领在于看、听、说、练。对于新手、进阶的信息安全工作者来说，刷题能够让算法能力得到一个质的飞跃。
1、hackerrank - https://www.hackerrank.com/
面向程序员、Hacker们的社交网络，在算法、数学、SQL、函数式编程、AI等众多不同领域为挑战者们提供了相应的编程题目，用户可直接在线完成挑战。
2、Topcoder - https://www.topcoder.com/
成立于2001年，最早的在线编程竞技平台之一，网站提供了一系列的算法挑战，参赛者可使用代码编辑器直接进行在线作答，比拼获胜者可获得竞赛赞助方提供的奖励。
3、Geeksforgeeks - https://www.geeksforgeeks.org/
Geeksforgeeks涵盖文章、解释和代码解决方案等内容，除了提供基础的编程、算法学习资源外，在“算法和数据结构”主题中，提供测试项目，解题者可以在在线编辑器中进行挑战。
4、codeforces - http://codeforces.com/
此网站是由来自萨拉托夫州立大学Mike Mirzayanov领导的一个团队创立和维护，是一个举办比赛、做题和交流的平台，网站自带blog功能，可以求助/发布题解。
5、lintcode - https://www.lintcode.com/
支持中英双语，汇集了算法、数据结构，人工智能，系统设计等众多领域的题目，网站还会举办编程比赛，很多算法爱好者在这里切磋技艺。
此外：
1、Codewars - https://www.codewars.com/
2、Leetcode（https://leetcode.com/）
3、Github （https://github.com)
4、codehs - https://codehs.com/
5、visualgo - https://visualgo.net/
6、CoderPro - http://coderpro.com.cn/
7、codesignal - https://codesignal.com/
8、CodinGame - https://www.codingame.com/
9、codechef - https://www.codechef.com/
10、v2ex - https://www.v2ex.com/
11、Online Judge - https://acm.sjtu.edu.cn/OnlineJudge/
12、codecademy - https://www.codecademy.com/
13、programmingpraxis - https://programmingpraxis.com/
二、在线提交程序源代码
Online Judge系统最初使用于ACM-ICPC国际大学生程序设计竞赛和OI信息学奥林匹克竞赛中的自动判题和排名，现广泛应用于世界各地高校学生程序设计的训练、参赛队员的训练和选拔、各种程序设计竞赛以及数据结构和算法的学习和作业的自动提交判断中。
1、北大POJ - http://poj.org/
免费的公益性网上程序设计题库，包含3000多道饶有趣味的程序设计题，是个提供编程、算法题目的网站，兼容Pascal、C、C++、Java、Fortran等多种语言。
2、杭电HDU - http://acm.hdu.edu.cn/
杭州电子科技大学的在线评测系统，中国最受欢迎OJ之一，题目数量多，来源广，有很多优质好题。
3、浙大ZOJ - http://acm.zju.edu.cn/onlinejudge/
浙江大学的在线评测系统，国内起步最早的几个OJ之一，题目数量约2000道，打开速度较快。
4、洛谷 - https://www.luogu.org/
创办于2013年，是基于网页形式的信息学在线评测系统，它不仅仅是一个在线测题系统，还拥有强大的社区、在线学习功能。
5、RQNOJ - http://www.rqnoj.cn/
RenqingNet Online Judge，2007年8月上线，集成了题库、测评、讨论、团队、比赛等主体的网络平台，是国内OJ(信息学在线测评)开放平台开发和运行的先导。
其它：
1、大视野在线测评BZOJ - http://www.lydsy.com/JudgeOnline/
2、UOJ - http://uoj.ac/
3、福州大学 - http://acm.fzu.edu.cn/
4、上海交大OJ - http://acm.sjtu.edu.cn/OnlineJudge/
5、中科大OJ - http://acm.ustc.edu.cn/ustcoj/
6、宁波工程学院 - https://ac.2333.moe/
7、波兰SPOJ - http://www.spoj.com/
8、日本JOI - http://www.ioi-jp.org/index.html
9、LIGHTOJ - http://www.lightoj.com/
10、浙江工业大学OJ - http://acm.zjut.edu.cn/
以上，一股脑推荐很多网站，但并不意味着所有的都需要花大量的时间和精力去研究。在算法学习中，首先自己要找出自己的问题总是出在哪里？最薄弱的环节是哪一个？只有发现自身问题，知道如何学习去提升技能，最终才会学以致用。

ChuanXin · 发表于 2021-7-10 15:56

我来缅怀一下当年OI和ACM的日子……题目都在 Welcome To PKU JudgeOnline 上。

初期（校赛及省赛水题难度）:
一.基本算法:

枚举. (poj1753,poj2965)
贪心(poj1328,poj2109,poj2586)
递归和分治法.
递推.
构造法.(poj3295)
模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.图算法:

图的深度优先遍历和广度优先遍历.
最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026)
拓扑排序 (poj1094)
二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
最大流的增广路算法(KM算法). (poj1459,poj3436)

三.数据结构.

串 (poj1035,poj3080,poj1936)
排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
简单并查集的应用.
哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼树(poj3253)
堆
trie树(静态建树、动态建树) (poj2513)

四.简单搜索

深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.动态规划

背包问题. (poj1837,poj1276)
型如下表的简单DP(可参考lrj的书 page149):E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)

六.数学

组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)
数论.1.素数与整除问题2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115)
计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)

七.计算几何学.

几何公式.
叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)(poj1408,poj1584)
凸包. (poj2187,poj1113)

中级（校赛压轴及省赛中等难度）:一.基本算法:

C++的标准模版库的应用. (poj3096,poj3007)
较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)

二.图算法:

差分约束系统的建立和求解. (poj1201,poj2983)
最小费用最大流(poj2516,poj2516,poj2195)
双连通分量(poj2942)
强连通分支及其缩点.(poj2186)
图的割边和割点(poj3352)
最小割模型、网络流规约(poj3308)

三.数据结构.

线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)
静态二叉检索树. (poj2482,poj2352)
树状树组(poj1195,poj3321)
RMQ. (poj3264,poj3368)
并查集的高级应用. (poj1703,2492)
KMP算法. (poj1961,poj2406)

四.搜索

最优化剪枝和可行性剪枝
搜索的技巧和优化 (poj3411,poj1724)
记忆化搜索(poj3373,poj1691)

五.动态规划

较为复杂的动态规划(如动态规划解特别的旅行商TSP问题等)(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
记录状态的动态规划. (POJ3254,poj2411,poj1185)
树型动态规划(poj2057,poj1947,poj2486,poj3140)

六.数学

组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.
数学.1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
计算方法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单谷)的极值.3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)随机化算法(poj3318,poj2454)杂题(poj1870,poj3296,poj3286,poj1095)

七.计算几何学.

坐标离散化.
扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用)(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多边形的内核(半平面交)(poj3130,poj3335)
几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高级（regional中等难度）:一.基本算法要求:

代码快速写成,精简但不失风格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
保证正确性和高效性. poj3434

二.图算法:

度限制最小生成树和第K最短路. (poj1639)
最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最优比率生成树. (poj2728)
最小树形图(poj3164)
次小生成树.
无向图、有向图的最小环

三.数据结构.

trie图的建立和应用. (poj2778)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)
左偏树(可合并堆).后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)

四.搜索

较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)

五.动态规划

四边形不等式理论.
较难的状态DP(poj3133)

六.数学

组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论.
博奕论.1.极大极小过程(poj3317,poj1085)2.Nim问题.

七.计算几何学.

半平面求交(poj3384,poj2540)
可视图的建立(poj2966)
点集最小圆覆盖.
对踵点(poj2079)

八.综合题. (poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

=====================================================================

扯点建议：
如果你不是要死磕acm搞出成绩来的话，多放点心思在数据结构上对以后的帮助会比较大，比如字符串相关的字典树、哈希、自动机、后缀树等等，而对脑力要求较高的比如博弈论和各种花式动态规划（树型DP、集合DP、插头DP等等）就不用太关心了。

btw这些算法和数据结构如果能精通的话，对你以后做数据挖掘和机器学习是有极大帮助的。
广告时间：如果你对以上学习路径有什么困惑，或者你对以下问题感兴趣：

＊为什么面试官都喜欢考程序员基础算法？＊如何高效、系统性地学习算法和数据结构？＊为什么大家普遍觉得动态规划较难理解？＊学算法是否有必要参加 OI / ACM 等算法编程竞赛？＊如何平衡自己在算法、竞赛上和其它方面学习的精力投入？＊学习传统算法对日后工作的帮助具体有多大？＊学习传统算法对学习机器学习的帮助具体有多大？

那么欢迎来到我的知乎 Live：
SimonS 的知乎 Live - 如何快速攻克传统算法和数据结构
SimonS 的知乎 Live - 如何成为当下合格的算法工程师
SimonS 的知乎 Live - 机器学习入门需要哪些数学基础
http://weixin.qq.com/r/ukMSCqjEQPU-rexp9xao (二维码自动识别)

pc8888888 · 发表于 2021-7-10 15:58

好问题。非常同意大佬 @温酒的观点。

第一个算法是：怎么算时薪。

这里我的经验是不要按照 8 小时的工作制来计算，而是按照每个工作日实际的工作时间来计算时薪。要不然在那些 w/l balance 好著称的公司工作计算会有偏差。
举个例子，湾区某大厂小张年薪税前 240k。一年 52 周，平均每周 $4.6k。每周按照规定工作 40 小时，实际上在美国一般真正用于工作的时间有 30 小时/周就已经很忙了。
4.6k / 30 = 153
所以小张的最低时薪应该至少为 $153。注意，还不包括公司给 match 的 401k 以及各种保险。所以综合考虑应该还要更多一点。

第二个算法我认为程序员应该掌握的是确定做一件事的止损点，即在沉没成本大于多少时果断放弃做这件事？
考虑以下几个场景
1）”追“一个妹子，追多久如果还不答应就果断换人？
2）刷题进 dream company，刷到什么程度就去面试自己的 dream company，如果失败立马换其他公司？
3）在当前公司划水到什么时候应当考虑跳槽？
4）房价降/涨到什么时候则考虑买房？

这些都是我们生活中息息相关的事情，我认为掌握这些算法更重要，优先级更高。

c0d3n4m · 发表于 2021-7-10 16:02

前面一些回答，尤其那个3k多赞的，算是知识点罗列吗？找两本书：初等算法+算法设计，把目录贴出来，大概就是这个样子了。
我对此类回答不太满意。我来换一个角度解读下吧。

其实程序员员掌握多少算法并不关键，关键的是能不能理解算法背后深层的理论，以及修练出解题的思路。
就好像排序中的堆排序，本质就是二叉树的应用。
快速排序、希尔排序等本质都是分治法的思路。
等等
见的多了就会发现，很多算法面向解决的问题明明相差很大，但底层实现都是非常类似；而又有些算法面向的问题很类似，而底层实现又相差巨大。

现实世界的需求是千变万化的，即使你掌握再多的算法也不可能直接照搬某个算法去解决你面对的问题。
关键的是要通过学习算法过程中整理出解决问题的思路。例如面对高性能的需求附带一些个性化的情况时，是用hash表解决，还是用二叉树，选择哪种具体的实现以及一些细节处的处理。
因此在现实环境中，严格按照某种算法定义使用算法的情况很少见，大多都是变种。甚至多种算法拼凑组合。
而为什么能产生这么多算法，这么多变种算法的原因，其实也是因为很多人在面对自己的需求时照搬经典算法解决不了问题，所以修改或优化了算法，才产生了变种算法甚至新算法。

所以，学习算法不要单纯去记忆算法的定义和实现代码，关键是要学会其中的思路。

这个跟写代码学习设计模式、架构模式等的情况是一样的。真正严格匹配某种模式的情况很少，都是杂合。
关键是掌握其中的本质。就好像武功中的，看山还是山，看水还是水。无招胜有着的境界。

欢迎点赞和评论。

量子计算9 · 发表于 2021-7-10 16:05

经常有小伙伴吐槽：面试造航母，工作拧螺丝。面试中各种花式手撕算法题，到了实际工作却沦为CRUD boy。不过现在随便面个试，都少不了出几道算法题，该刷题还是得刷。
所以针对面试算法，结合九章算法的学习刷题路线，我们整理了面试高频考到的算法与数据结构，大家有需要自取~
算法部分包括：复杂度理论基础，双指针算法、排序算法、二分法、宽度优先搜索、递归、遍历、分治、深度优先搜索、记忆化搜索、动态规划。
数据结构包括：栈、队列、链表、数组、哈希表、二叉树、堆、并查集、字典树。
掌握这些算法和数据结构，基本可以应付90%以上的面试算法题。至于如何学习？除了算法书外，我还推荐来LintCode刷题，这里送上各种算法的常考题和经典题，搭配《九章算法班》食用更佳~
另外在周末的首节直播分享中，将会送出算法面试精选100题，刷题100道胜过别人刷300道，有兴趣的同学可以来看看！
双指针算法
最长无重复字符的子串
装最多水的容器
接雨水
有效回文串
带环链表 II
排序算法
摆动排序
构造队列
Nuts 和 Bolts 的问题
第k大元素
无序数组K小元素
逆序对
区间和的个数
二分法
寻找旋转排序数组中的最小值
搜索旋转排序数组
对x开根
两个整数相除
寻找峰值
宽度优先搜索
单词接龙
岛屿的个数
二叉树的层次遍历
克隆图
二叉树的锯齿形层次遍历
二叉树的右视图
递归
生成括号
格雷编码
平衡二叉树
电话号码的字母组合
全排列
二叉树中的最大路径和
遍历
买卖股票的最佳时机 III
最大子数组 II
二叉树的层次遍历
二叉树的前序遍历
二叉树的后序遍历
二叉树的所有路径
二叉树的层次遍历 II
分治法
两个排序数组的中位数
合并k个排序链表
平衡二叉树
二叉树中的最大路径和
验证二叉查找树
深度优先搜索
二叉树的最小深度
插入五
克隆图
单词接龙 II
分割回文串
N皇后问题
动态规划
最大的假期天数
爬楼梯关注问题
正则表达式匹配
打劫房屋
单词拆分 I
乘积最大子序列
解码方法关注问题
编辑距离

		自动登录	找回密码
密码			立即注册

程序员必须掌握哪些算法？

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源