深度优先搜索DFS、广度优先搜索BFS
比较
拿谚语打比方的话,深度优先搜索可以比作打破砂锅问到底、不撞南墙不回头;广度优先搜索则对应广撒网,多敛鱼两者没有绝对的优劣之分,只是适用场景不同当解决方案离树根不远或搜索深度可变时,BFS通常更好,因为只需搜索所有数据中的一部分。另外BFS的一个重要优点是它可以用于找到无权图(有权图用Dijkstra算法,贪心思想)中任意两个节点之间的最短路径(不能使用DFS)如果树比较宽而且深度有限,DFS可能是更优选项,因为DFS比BSF更节省空间,另外由于使用递归,DFS更好写(BFS必须手动维护队列)时间复杂度
都是O(n)
空间复杂度
都是O(n)
经典题目
LeetCode 102题,二叉树的层序遍历思路:DFS,深度优先,用level记录当前层,如果当前层记录完毕就return,结果数组用level索引当前层,结果数组容量小于等于level就扩容,再DFS递归到下一层BFS,广度优先,用队列先进先出的特性,先确定当前层的节点数量,遍历当前层,把当前层的下一层所有节点入队,当前层节点出队并放到一个临时数组,再添加到结果
// DFS-Java
// BFS-Java
二分查找
本质
二分查找的本质是在一组单调、有上下界、可索引的数据中搜索目标值,三大条件缺一不可。
时间复杂度
O(logN)
空间复杂度
O(1)
经典题目
LeetCode 69 题,x的平方根思路:二分查找,因为y=x^2在x正半轴单调递增,且存在上下界1和x,所以可以使用二分查找逼近牛顿迭代法,利用切线逼近,公式为 x = (x + a/x) / 2
// 二分查找
// 牛顿迭代法
贪心算法
本质
贪心的本质是通过每一步的局部最优,期望实现全局最优的一种算法思想。关键在于局部最优是否真的能实现全局最优。如果能实现,那么贪心算法基本上就是问题的最优解。
经典例题
LeetCode 55题,跳跃游戏思路:倒序贪心,看最后能不能到达第一个点正序贪心,如果某个点可以跳到最后,那么它左边的点一定可以
// 倒序贪心
// 正序贪心