算法基础04-DFS、BFS、贪心算法、二分查找

[venaissance]

深度优先搜索DFS、广度优先搜索BFS

比较

• 拿谚语打比方的话，深度优先搜索对应“打破砂锅问到底”、”不撞南墙不回头“；广度优先搜索对应“广撒网，多敛鱼”
• 两者没有绝对的优劣之分，只是适用场景不同
• 当解决方案离树根不远或搜索深度可变时，BFS通常更好，因为只需搜索所有数据中的一部分。另外BFS的一个重要优点是它可以用于找到无权图（有权图用Dijkstra算法，贪心思想）中任意两个节点之间的最短路径（不能使用DFS）
• 如果树比较宽而且深度有限，DFS可能是更优选项，因为DFS比BSF更节省空间，另外由于使用递归，DFS更好写（BFS必须手动维护队列）

时间复杂度

都是O(n)

空间复杂度

都是O(n)

经典题目

1. LeetCode 102题，二叉树的层序遍历

   思路：

   1. DFS，深度优先，用level记录当前层，如果当前层记录完毕就return，结果数组用level索引当前层，结果数组容量小于等于level就扩容，再DFS递归到下一层
   2. BFS，广度优先，用队列先进先出的特性，先确定当前层的节点数量，遍历当前层，把当前层的下一层所有节点入队，当前层节点出队并放到一个临时数组，再添加到结果

   DFS-Java

   class 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-Java

   class 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)

经典题目

1. LeetCode 69 题，x的平方根

   思路：

   1. 二分查找，因为y=x^2在x正半轴单调递增，且存在上下界1和x，所以可以使用二分查找逼近

   2. 牛顿迭代法，利用切线逼近，公式为 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;
          }
      }

贪心算法

本质

贪心的本质是通过每一步的局部最优，期望实现全局最优的一种算法思想。关键在于局部最优是否真的能实现全局最优。如果能实现，那么贪心算法基本上就是问题的最优解。

经典例题

1. LeetCode 55题，跳跃游戏

   思路：

   1. 倒序贪心，看最后能不能到达第一个点
   2. 正序贪心，如果某个点可以跳到最后，那么它左边的点一定可以

   倒序贪心

   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;
       }
   }