深度优先搜索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-Javaclass Solution {public List<List<Integer>> res = new LinkedList<>();public List<List<Integer>> levelOrder(TreeNode root) {dfs(0, root);return res;}private void dfs(int level, TreeNode root){if(root == null) return;if(res.size() <= level){res.add(new LinkedList<>());}res.get(level).add(root.val);dfs(level+1, root.left);dfs(level+1, root.right);}}
// BFS-Javaclass Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new LinkedList<>();Queue<TreeNode> queue = new LinkedList<>();if(root == null) return res;queue.add(root);while(!queue.isEmpty()){int level = queue.size();List<Integer> tempList = new LinkedList<>();for(int i = 0; i < level; i++){if(queue.peek().left != null) queue.add(queue.peek().left);if(queue.peek().right != null) queue.add(queue.peek().right);tempList.add(queue.poll().val);}res.add(tempList);}return res;}}
二分查找
本质
二分查找的本质是在一组单调、有上下界、可索引的数据中搜索目标值，三大条件缺一不可。
时间复杂度
O(logN)
空间复杂度
O(1)
经典题目
LeetCode 69 题，x的平方根思路：二分查找，因为y=x^2在x正半轴单调递增，且存在上下界1和x，所以可以使用二分查找逼近牛顿迭代法，利用切线逼近，公式为 x = (x + a/x) / 2
// 二分查找class Solution {public int mySqrt(int x) {if(x == 0 || x == 1) return x;long left = 1, right = x, mid = 1;while(left <= right){mid = left + (right - left) / 2;if(mid * mid > x){right = mid - 1;} else {left = mid + 1;}}return (int) right;}}
// 牛顿迭代法class Solution {public int mySqrt(int x) {long r = x;while (r * r > x) {r = (r + x / r) / 2;}return (int)r;}}
贪心算法
本质
贪心的本质是通过每一步的局部最优，期望实现全局最优的一种算法思想。关键在于局部最优是否真的能实现全局最优。如果能实现，那么贪心算法基本上就是问题的最优解。
经典例题
LeetCode 55题，跳跃游戏思路：倒序贪心，看最后能不能到达第一个点正序贪心，如果某个点可以跳到最后，那么它左边的点一定可以
// 倒序贪心class Solution {public boolean canJump(int[] nums) {if (nums == null) return false;int endReachable = nums.length - 1;for (int i = nums.length - 1; i >= 0; i--){if(nums[i] + i >= endReachable){endReachable = i;}}return endReachable == 0;}}
// 正序贪心class Solution {public boolean canJump(int[] nums) {int maxPos = 0;for (int i = 0; i < nums.length; i++){if(i > maxLen) return false;maxPos = Math.max(maxPos, nums[i] + i);if(maxPos >= nums.length-1) break;}return true;}}
深度搜索和广度搜索领接表实现_算法基础04-深度优先搜索 广度优先搜索 二分查找 贪心算法...
