算法在程序中扮演着非常重要的角色,有人将数据结构比喻为程序的骨架,将算法比喻为程序的灵魂,这一点也不为过。正是因为这一点,很多朋友都立志要学好算法,但是我常常看到各种抱怨,比如“看了半年《算法》这本书,才看了几十页”,再比如“四年了,还是没有啃完《算法导论》”。出现这种情况的主要原因有两个:
人们设计各种算法的目的是解决现实中的问题,虽然各种算法的实现五花八门,但是设计算法却有一些通用的方法或思想(也有的资料将其称为算法设计模式)。归纳起来,这些常见的算法设计方法有迭代法、穷举搜索法、分支界限法(剪枝法)、递推法、递归法、回溯法、分治法、贪婪法和动态规划法等。
本专栏选择了 35 个简单且实用的算法实例,这些算法实例基本覆盖了各种算法比赛中经常出现的题目以及生活中常见的算法实现。每个算法实现都将讲解的侧重点放在各种算法的设计方法在算法中的体现,通过一个个算法例子,来引导大家掌握常见的算法设计思想。
除此之外,在算法实现的过程中,还会详细介绍针对各个问题的建模过程,使读者能够举一反三,学会如何将文字描述的问题抽象为算法能够使用的数据模型。总之,本专栏的目的不是学会这些算法,而是通过学习这些算法的实现,掌握算法设计的方法,以后遇到类似的问题,可以自己设计并实现解决问题的算法。
本专栏前半部分根据常见的算法题目,重点介绍迭代、穷举和动态规划三个主题,三个主题共计 18 个算法实例,基本上涵盖了上述所有算法设计方法和思想的应用。后半部分则通过 24 个有趣的算法实现,让大家理解算法的重要性,但重点仍然是各种算法设计思想的应用和如何设计适用于算法的数据模型。
本专栏的目的是培养大家解决实际问题的能力,每篇介绍一个算法问题,通过对这个问题的分析和解决,锻炼大家针对问题设计数据模型,并应用合适的算法思想设计出解决问题的算法实现的能力。 本专栏分为七大部分,共计 49 篇。
这部分内容包含 7 篇,第 1 篇为算法基础内容,介绍了将问题抽象成数据建模的常用方法;第 2 ~ 6 篇介绍了 5 种常用的算法设计思想(模式),分析了各种算法模式的特点和使用时需要注意的要点,每种模式都用一到两个具体的算法做示例;第 7 篇介绍了一些基础算法和技巧,比如排序、单链表逆序和用数组存储树等小算法,作为本专栏开始之前的热身或开胃菜。
这部分内容通过 3 个在数学领域常用的数值分析方法,介绍了迭代思想在算法设计中的应用,还包括如何将数学公式或文字描述的递推关系转化为数据模型的方法。
这部分内容包含 9 篇,前 7 篇通过 7 个不同的算法实例,介绍了几种常见的穷举方法,比如线性数字类问题的穷举方法、树形空间的穷举方法、棋盘类游戏的常用穷举方法以及复杂问题的多重穷举和组合穷举方法,重点介绍了如何设计与穷举算法相适应的数据模型,以及用合理的数据模型简化算法实现的技巧。后两篇分别介绍了如何理解和设计递归函数,以及算法中浮点数处理的一些经验。
这部分内容包含 8 篇,第 1 篇介绍了动态规划算法的常用设计思想和方法,后面 7 篇分别介绍了 7 个有趣的算法,其中有一些是算法比赛中出现过的题目,还有一些是动态规划的典型问题,既有简单的线性(一维)动态规划和二维动态规划问题,也有凸多边形的三角剖分、矩阵链乘这样的热点问题。
动态规划最重要的是划分阶段和确定状态(确定递推关系式),通过这些例子,可以了解如何建立问题对应的数据模型以及建立在数据模型上的递推关系式。掌握这些方法,再遇到动态规划类的问题时,就不会束手无策了。
图论既是各种算法比赛中出题的“重灾区”,也是现实生活中很多有趣算法的理论基础,这部分内容选了 6 个有趣的算法,包括二分图的最大匹配、图的排序和关键路径、欧拉图、最大流等经典问题,讲解的重点仍然是各种算法设计的思想和建立数据模型。
这部分内容包含 8 篇,介绍了一些游戏中常用的有趣味算法,包括决策树、博弈树和行为树的搜索算法,涉及的内容包括穷举、递归和分支界限法等算法思想的应用。这些算法都是非常经典的,掌握这些算法思想,将有助于读者开阔思维、提升代码能力。
这部分内容介绍了 6 个算法,都是一些名声远扬的公开算法,不需要重新设计,学习这些算法的关键是如何根据实际的问题建立数据模型,然后套用算法解决问题。每种算法都有具体的实例,通过这些例子与算法原理相结合,不仅有助于理解算法,还可以了解到将这些算法应用到实践中常用的建模方法。
王晓华,毕业于华中科技大学,著有《算法的乐趣》一书。目前就职于中兴通讯,任职开发经理和资深软件工程师,主要工作是嵌入式通讯软件开发。精通 C 和 C++ 开发语言,以及算法设计、面向对象的软件设计和重构、测试驱动开发、敏捷与过程改进、Windows 内核文件系统、汇编语言、软件破解与保护、网络安全。
《算法设计实战 50 讲》展示有趣的问题、启发有趣的思路、归纳有趣的解法,是一门有趣的专栏。
——王益,百度美研 T10 架构师,百度深度学习系统 PaddlePaddle 的技术负责人
《算法设计实战 50 讲》是真正在训练读者解决问题的能力,而解决问题的能力,正是任何一家公司所需人才的最核心的技能。
——黄鑫(飞林沙),极光推送首席科学家
订购本专栏可获得专属海报(在 GitChat 服务号领取),分享专属海报每成功邀请一位好友购买,即可获得 25% 的返现奖励,多邀多得,上不封顶,立即提现。
提现流程:在 GitChat 服务号中点击「我-我的邀请-提现」。
购买本专栏后,服务号会自动弹出入群二维码和暗号。如果你没有收到那就先关注微信服务号「GitChat」,或者加我们图上的小助手微信进行咨询。(入群方式可查看第 3 篇文末说明)。
当前内容版权归码字科技所有并授权显示,盗版必究。阅读原文