BFS算法框架

BFS是广度优先搜索，其核心思想是把一些问题抽象成图，从一个点开始，向四周扩散。BFS通常是用来解决最短路的问题，问题的本质就是让你在一副“图”中找到从起点 start 到终点 target 的最近距离。
比如：

  1. 走迷宫，有的格子是围墙不能走（限制条件），从起点到终点的最短距离是多少？
  2. 两个单词，要求通过替换某些字母，把其中一个变成另一个，每次只能替换一个字母，最少要替换几次？
  3. 求二叉树最小深度和高度 111. 二叉树的最小深度
  4. 转盘锁，每次波动一个位置，把一个密码变成目标密码，并且有些密码是死亡密码不能经过它，问最小的旋转次数752. 打开转盘锁
  5. 连连看游戏，消除两个方块的条件不仅是图案相同，还要保证两个方块之间的最短连线不能多于两个拐点。

BFS 算法框架

  1. // 计算从起点 start 到终点 target 的最近距离
  2. int BFS(Node start, Node target) {
  3.     queue<Node> q; // 核心数据结构
  4.     unordered_set<Node> visited; // 避免走回头路
  5.     q.push(start); // 将起点加入队列
  6.     visited.insert(start);//起点已经访问过了
  7.     int step = 0; // 记录扩散的步数
  9.     while ( !q.empty() ) {
  10.         int sz = q.size();
  11.         /* 将当前队列中的所有节点向四周扩散 */
  12.         for (int i = 0; i < sz; i++) {
  13.             Node cur = q.front();
  14.             q.pop();
  15.             /* 划重点：这里判断是否到达终点 */
  16.             if (cur == target)
  17.                 return step;
  19.             if (满足限制条件) continue;//根据题目的限制条件，有些分支需要跳过
  21.             /* 将 cur 的相邻节点加入队列 */
  22.             for (Node x : cur.adj())
  23.                 if (x not in visited) {
  24.                     q.push(x);
  25.                     visited.insert(x);
  26.                 }
  27.         }
  28.         /* 划重点：更新步数在这里 */
  29.         step++;
  30.     }
  31.     return step;
  32. }

队列q 是BFS 的核心数据结构；cur.adj()泛指cur相邻的节点，比如说二维数组中，cur上下左右四面的位置就是相邻节点；visited的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要visited。

二分搜索框架

我作了首诗，保你闭着眼睛也能写对二分查找

寻找一个数（基本的二分搜索)

  1. int binary_search(int[] nums, int target) {
  2.     int left = 0, right = nums.length - 1; 
  3.     while(left <= right) {
  4.         int mid = left + (right - left) / 2;
  5.         if (nums[mid] < target) {
  6.             left = mid + 1;
  7.         } else if (nums[mid] > target) {
  8.             right = mid - 1; 
  9.         } else if(nums[mid] == target) {
  10.             // 直接返回
  11.             return mid;
  12.         }
  13.     }
  14.     // 直接返回
  15.     return -1;
  16. }

寻找左侧边界的二分搜索

  1. int left_bound(int[] nums, int target) {
  2.     int left = 0, right = nums.length - 1;
  3.     while (left <= right) {
  4.         int mid = left + (right - left) / 2;
  5.         if (nums[mid] < target) {
  6.             left = mid + 1;
  7.         } else if (nums[mid] > target) {
  8.             right = mid - 1;
  9.         } else if (nums[mid] == target) {
  10.             // 别返回，锁定左侧边界
  11.             right = mid - 1;
  12.         }
  13.     }
  14.     // 最后要检查 left 越界的情况
  15.     if (left >= nums.length || nums[left] != target)
  16.         return -1;
  17.     return left;
  18. }

寻找右侧边界的二分搜索

  1. int right_bound(int[] nums, int target) {
  2.     int left = 0, right = nums.length - 1;
  3.     while (left <= right) {
  4.         int mid = left + (right - left) / 2;
  5.         if (nums[mid] < target) {
  6.             left = mid + 1;
  7.         } else if (nums[mid] > target) {
  8.             right = mid - 1;
  9.         } else if (nums[mid] == target) {
  10.             // 别返回，锁定右侧边界
  11.             left = mid + 1;
  12.         }
  13.     }
  14.     // 最后要检查 right 越界的情况
  15.     if (right < 0 || nums[right] != target)
  16.         return -1;
  17.     return right;
  18. }

动态规划解题套路框架

回溯算法解题套路框架

解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
1、**路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
回溯算法的框架：**

  1. result = []
  2. def backtrack(路径, 选择列表):
  3.     if 满足结束条件:
  4.         result.add(路径)
  5.         return
  6.     for 选择 in 选择列表:
  7.         做选择
  8.         backtrack(路径, 选择列表)
  9.         撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」。
写backtrack函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。
其实想想看，回溯算法和动态规划是不是有点像呢？动态规划的三个需要明确的点就是「状态」「选择」和「base case」，是不是就对应着走过的「路径」，当前的「选择列表」和「结束条件」？
某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。而今天的两个问题，都没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的。
例子：

  1. 46. 全排列 47. 全排列 II

  2. 51. N皇后**

    滑动窗口算法

    1. /* 滑动窗口算法框架 */
    2. void slidingWindow(string s, string t) {//在s中寻找满足条件的t
    3.  unordered_map<char, int> need, window;
    4.  for (char c : t) need[c]++;
    6.  int left = 0, right = 0;
    7.  int valid = 0; 
    8.  while (right < s.size()) {
    9.      // c 是将移入窗口的字符
    10.      char c = s[right];
    11.      // 右移窗口
    12.      right++;
    13.      // 进行窗口内数据的一系列更新，【根据情况更改】,如
    14.      if (need.count(c)) {
    15.              window[c]++;
    16.              if (window[c] == need[c]) valid++;
    17.       }
    18.      ......
    20.      // 判断左侧窗口是否要收缩
    21.      while (window needs shrink) {
    22.          // d 是将移出窗口的字符
    23.          char d = s[left];
    24.          // 左移窗口
    25.          left++;
    26.          // 进行窗口内数据的一系列更新，【根据情况更改】,如
    27.          if (need.count(d)) {
    28.              if(window[d] == need[d]) valid--;
    29.              window[d]--;
    30.           }
    31.          ......
    32.      }
    33.  }
    34. }

    例子：

  3. 76. 最小覆盖子串

  4. 567. 字符串的排列
  5. 438. 找到字符串中所有字母异位词
  6. 3. 无重复字符的最长子串

参考

公众号：【labuladong】 ，文章链接 — 列表形式目录