算法思想:
- 枚举:列出所有的点进行处理。-开始前可以先排除不可能的点。
- 递归:函数调用自身。-每次处理的方式一样,只是数据不一样,可以用递归。
- 二分法:每一次比较,将原来的数据缩小一半,然后重复,直到找到数据或查找失败。
- 分治:将问题分解成几个小问题,分别解决,再将结果合并。
- 动态规划:保存计算后的状态,下次计算的时候使用,不用重新计算。
- 深度优先搜索:一直往下找
- 广度优先搜索:先找附近的
- 贪心算法:在对问题求解时,总是做出在当前看来是最好的选择。
- 回溯法:像枚举的一样搜索,搜索过程中尝试寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。
详解:
-
枚举
逐个处理
应用:冒泡排序、插入排序、选择排序
递归
应用: 快速排序、归并排序
// 阶乘
function factorial(n) {
if (n == 1) {return 1;}
return n * factorial(n-1);
}
factorial(4); // 24
调用函数时,自身还未结束就去调用另一个函数时,会将自身状态保存到系统栈中,直到最后一次调用结束,然后出栈。
-
二分法
数据得是有序的
应用:快速排序、二分查找、
分治
问题:有8枚硬币,其中有一个是假的,假的比真的轻。现在给你一个天平秤,如何用最少的次数找出假币?
答:3次。拆分成两半,第一次 4 = 4 。第二次2 = 2。第三次 1 = 1
应用:快速排序、归并排序、桶排序-
动态规划
建模思路:- 最优子结构:原问题分解成小问题
- 状态:将小问题的结果保存起来
- 状态转换:根据已知结果推出未知
-
深度优先搜索
用栈辅助实现
-
广度优先搜索
用队列辅助实现
-
动态规划
问题:从A到C费用最少路径?
解: 从A中出发,2是当前最好的选择,所以A > B > C
-
回溯法