当前位置:   article > 正文

专业技能篇--算法

专业技能篇--算法


前言

这篇简单理解一些常见的算法。如果面试的时候问到相关的算法,能够应付一二。


经典算法思想总结

一、贪心算法

思想:贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法策略。

步骤:

  • 定义问题:确定问题是否适合使用贪心算法,即问题具有贪心选择性质。
  • 选择标准:确定贪心选择的标准,即在每一步选择中如何判断“最好”或“最优”。
  • 执行贪心策略:按照贪心选择标准,逐步做出选择,直到问题解决。
  • 评估结果:分析结果,确定是否满足问题的要求,以及是否是最优解。

贪心算法的优点是实现简单,执行速度快,对于某些问题能够快速得到一个足够好的解决方案。但它的缺点是可能无法保证得到全局最优解,只适用于特定问题。


二、动态规划

思想:动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的。
步骤:

  • 确定 dp 数组(dp table)以及下标的含义
  • 确定递推公式
  • dp 数组如何初始化
  • 确定遍历顺序
  • 举例推导 dp 数组

三、回溯算法

算法思想:回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。其本质就是穷举。

步骤:

  • 针对所给问题,定义问题的解空间,它至少包含问题的一个(最优)解。
  • 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
  • 以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。leetcode

四、分治算法

算法思想:将一个规模为 N 的问题分解为 K 个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。

步骤:

  • 将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
  • 若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
  • 将各个子问题的解合并为原问题的解
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Guff_9hys/article/detail/737862
推荐阅读
相关标签
  

闽ICP备14008679号