时空复杂度

思想

模拟、枚举、递归（递归转迭代）、贪心★、分治、倍增

查找

二分查找★

  • 简单版

    1. int bs(int[] arr, int l, int r, int target) { // 找到最靠近target且>=target的index
    2.   while (l < r) {
    3.       int mid = (r - l) / 2 + l;
    4.       if (arr[mid] < target) {
    5.           l = mid + 1;
    6.       } else  {
    7.           r = mid;
    8.       }
    9.   }
    10.   return l;
    11. }

  • 完整版

    1. int findBoundary(int[] nums, int target, int direction) {
    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
    7.               left = mid + 1;
    8.           } else if (nums[mid] > target) {
    9.               // 更新right
    10.               right = mid - 1;
    11.           } else if (nums[mid] == target) {
    12.               if (direction == 0) {
    13.                   // 找左边界，收缩右边界
    14.                   right = mid - 1;
    15.               } else {
    16.                   // 找右边界，收缩左边界
    17.                   left = mid + 1;
    18.               }
    19.           }
    20.       }
    21.       if (direction == 0) {
    22.           if (left >= nums.length || nums[left] != target)
    23.               return -1;
    24.           return left;
    25.       } else {
    26.           if (right < 0 || nums[right] != target)
    27.               return -1;
    28.           return right;
    29.       }
    30. }

    快速选择★

    解决数组第K大元素的问题

搜索

这里指在树和图中搜索，综合应用枚举、贪心、回溯、递归、剪枝等思想

DFS★

判出口（终点、越界）->剪枝->扩展->标记->递归->还原

  1. /*
  2.  * Return true if there is a path from cur to target.
  3.  */
  4. boolean DFS(Node cur, Node target, Set<Node> visited) {
  5.     return true if cur is target;
  6.     for (next : each neighbor of cur) {
  7.         if (next is not in visited) {
  8.             add next to visted;
  9.             return true if DFS(next, target, visited) == true;
  10.         }
  11.     }
  12.     return false;
  13. }

BFS★

  • 如果不需要确定当前遍历到了哪一层

    1. queue.push(root)
    2. while queue 不空：
    3.   cur = queue.pop()
    4.   for 节点 in cur的所有相邻节点：
    5.       if 该节点有效且未访问过：
    6.           queue.push(该节点)

  • 如果要确定当前遍历到了哪一层

    level表示二叉树遍历到哪一层或者图走了几步、size表示在当前层有多少个元素

  1. queue.push(root)
  2. level = 0
  3. while queue 不空：
  4.     size = queue.size()
  5.     while (size --) {
  6.         cur = queue.pop()
  7.         for 节点 in cur的所有相邻节点：
  8.             if 该节点有效且未被访问过：
  9.                 queue.push(该节点)
  10.     }
  11.     level ++;

回溯★

常用于找到所有可能路径的题

  • 模板要素
    • 路径集<路径<选择>>的含义？
    • 结束条件是什么？
    • 如何枚举选择？
    • 选择如何符合要求？

  • 模板

    1. List<List<Integer>> 路径集 = new ArrayList<>();
    2. private void backtrack(路径, 选择or选择列表) {
    3.   if(满足结束条件) {
    4.       路径集.add(路径); // 深拷贝
    5.       return;
    6.   }
    7.   for (选择: 选择列表) {
    8.       if(选择符合要求) {
    9.           路径.add(选择); // 做选择
    10.           backtrack(路径, 新选择or新选择列表); // 对新的未探索区域递归
    11.           路径.remove(路径.size() - 1); // 撤销选择
    12.       }
    13.   }
    14. }

    记忆化

    搜索过程中需要记忆某些状态便于后续复用

  • 思路

    • 定义状态/状态数组和状态表示含义
    • 函数f判断状态是否满足条件执行后续搜索逻辑
    • f的逻辑：更新过状态，则直接返回；没更新过状态，则更新

      A*

      启发式搜索

参考https://zhuanlan.zhihu.com/p/108344917

  1. * 初始化open_set和close_set；
  2. * 将起点加入open_set中，并设置优先级为0（优先级最高）；
  3. * 如果open_set不为空，则从open_set中选取优先级最高的节点n：
  4.     * 如果节点n为终点，则：
  5.         * 从终点开始逐步追踪parent节点，一直达到起点；
  6.         * 返回找到的结果路径，算法结束；
  7.     * 如果节点n不是终点，则：
  8.         * 将节点n从open_set中删除，并加入close_set中；
  9.         * 遍历节点n所有的邻近节点：
  10.             * 如果邻近节点m在close_set中，则：
  11.                 * 跳过，选取下一个邻近节点
  12.             * 如果邻近节点m在open_set中，则：
  13.                 * 判断节点n到节点m的 F(n) + cost[n,m] 值是否 < 节点m的 F(m) 。来尝试更新该点，重新设置f值和父节点等数据
  14.             * 如果邻近节点m也不在open_set中，则：
  15.                 * 设置节点m的parent为节点n
  16.                 * 计算节点m的优先级
  17.                 * 将节点m加入open_set中

排序★

算法 - 图1

简单排序

插入

冒泡

分治排序

快速

  1. void QuickSort(int arr, int left, int right) {
  2.     if(left >= right)
  3.         return;
  4.     int i = left, j = right, pivot = arr[left];
  5.     while(i < j) {
  6.                 while(i<j && arr[j] >= pivot) j--;
  7.             arr[i] = arr[j];
  8.         while(i<j && arr[i] <= pivot) i++;
  9.             arr[j] = arr[i];
  10.         }
  11.     arr[i] = pivot;
  12.     QuickSort(arr, left, i - 1);
  13.     QuickSort(arr, i + 1, right);
  14. }

归并

树形排序

选择

堆

分配排序

桶

基数

双指针★

查找子字符串

滑动窗口★

  • 求最大窗口大小（for版本）

    1. int  maxLen = 0; // 窗口最大值
    2. int sum = 0; // 当前状态
    3. for(int l = 0, r = 0; r < arr.length; r++) {
    4.   sum += arr[r]; // 根据加入右指针更新状态
    5.   if (sum <= maxCost) { // 满足约束
    6.       maxLen = Math.max(maxLen, r - l + 1); // 更新窗口最大值
    7.   } else { // 不满足约束
    8.       sum -= arr[l]; // 根据去除左指针更新状态
    9.       l++; // 左指针右移
    10.   }
    11. }
    12. return maxLen;

  • 求最大窗口大小（双while版本）

    • 模板1

      1. while(r < n){
      2. UPDATE STATE(r)
      3. while(WRONG){
      4.    UPDATE STATE(l)
      5.    l++
      6. }
      7. MAXORMIN(ans)
      8. r++
      9. }

    • 模板2

      1. int l = 0, r = 0, sum = 0, maxLen = 0; // 初始化左右指针，状态值，窗口大小
      2. while (r < n) { // 右指针不越界
      3. sum += arr[r]; // 根据加入右指针更新状态
      4. while(sum > maxCost) { // 不符合约束条件
      5.    sum -= arr[l]; // 根据去除左指针更新状态
      6.    l++; // 左指针右移
      7. }
      8. maxLen = Math.max(maxLen, r - l + 1); // 更新窗口最大值
      9. r++; // 右指针右移
      10. }
      11. return maxLen;

    • 模板3

      1. int l = 0, r = 0, sum = 0, maxLen = 0; // 初始化左右指针，状态值，窗口大小
      2. while (r < n) { // 右指针不越界
      3. sum += arr[r]; // 根据加入右指针更新状态
      4. r++; // 右指针右移
      5. while(sum > maxCost) { // 不符合约束条件
      6.    sum -= arr[l]; // 根据去除左指针更新状态
      7.    l++; // 左指针右移
      8. }
      9. maxLen = Math.max(maxLen, r - l); // 更新窗口最大值（注意区别）
      10. }
      11. return maxLen;

  • 窗口不需要减小

    1. int l = 0, r = 0, sum = 0;
    2. for(; r < n; r++) {
    3.   if(sum + arr[r] > maxCost) { // 不满足约束，左右指针同时移动
    4.       sum += arr[r] - arr[l]; // 更新状态
    5.       l++;
    6.   } else { // 满足约束，右指针移动
    7.       sum += arr[r]; // 更新状态
    8.   }
    9. }
    10. return r - l;

  • 复杂样板

    1. public String minWindow(String s, String t) {
    2.   int left = 0, right = 0; // 滑动窗口前后指针
    3.   int min = Integer.MAX_VALUE; // 最小子串的长度
    4.   int start = 0, end = 0; // 最小子串的左右位置
    5.   int count = 0; // 相同字符的个数
    7.   Map<Character, Integer> tMap = new HashMap<>(); // target串的字符计数（目标）
    8.   Map<Character, Integer> sMap = new HashMap<>(); // source串的字符计数（窗口）
    10.   // 初始化target串的字符计数
    11.   for (int i = 0; i < t.length(); ++i) {
    12.       tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
    13.   }
    15.   while (right < s.length()) {
    16.       char c = s.charAt(right);
    17.       // 更新窗口状态
    18.       if (tMap.containsKey(c)) { // 是所求字符
    19.           sMap.put(c, sMap.getOrDefault(c, 0) + 1); // 存字符进窗口
    20.           if (tMap.get(c).compareTo(sMap.get(c)) == 0) { // 看是不是该字符达标
    21.               count++;
    22.           }
    23.       }
    24.       right++; // 右滑动扩大
    25.       while (count == tMap.size()) {
    26.           // 满足条件，更新最值
    27.           if (min > right - left) {
    28.               end = right;
    29.               start = left;
    30.               min = right - left;
    31.           }
    32.           char d = s.charAt(left);
    33.           // 更新窗口状态
    34.           if (tMap.containsKey(d)) {
    35.               sMap.put(d, sMap.get(d) - 1);
    36.               if (tMap.get(d) > sMap.get(d)) {
    37.                   count--;
    38.               }
    39.           }
    40.           left++; //左滑动缩小
    41.       }
    42.   }
    43.   return min == Integer.MIN_VALUE ? "" : s.substring(start, end);
    44. }

    快慢指针★

    动态规划

    通用思考模板

  • 状态定义：一维还是二维？

  • 转移方程：有几种状态？状态之间依赖关系？
  • 初始条件
  • 结果表示

  • 是否可以采用优化：滚动数组/滚动变量

    计数问题

    线性DP

  • 最长公共/上升子序列

  • 公共子串

    树状DP

    背包DP

  • 定义：i表示物品编号，j表示容量（不超过容量j / 容量恰好是j），质量为w，价值为v

  • 朴素方程：f[i][j]=max(f[i-1][j],f[i-1][j-kw[i]]+kv[i])
  • 一维优化：f[j]=max(f[j],f[j-w[i]]+v[i]) 【容量维度从小到大遍历】 遍历物品{遍历容量{}}

背包分类

  • 01背包：每个元素最多选取一次
    • 解法：外循环nums,内循环target,target倒序且target>=nums[i];
  • 完全背包（排列数）：每个元素可以重复选择
    • 解法：外循环nums,内循环target,target正序且target>=nums[i];
  • 组合背包：背包中的物品要考虑顺序
    • 解法：外循环target,内循环nums,target正序且target>=nums[i];
  • 分组背包问题：不止一个背包，需要遍历每个背包
    • 解法：外循环背包bags,内部两层循环根据题目的要求转化为以上三种背包类型的模板

问题分类：

  • 求解最值
    • 解法：dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);
  • 求解存在（存在… 满足…）
    • 解法：dp[i] = dp[i] || dp[i-num];

  • 求解组合（所有满足…的组合（数））

    • 解法：dp[i] += dp[i-num];

      区间DP

  • 区间最值问题（RMQ）

    ST表

  • 矩阵连乘

  • 石子合并

    数位DP

  • 数字游戏

    状压DP

    倍增

  • 旅行商问题

    数学

    高精度计算

    位运算★

    计算几何

    扫描线

    排列组合★

    集合与离散数学

    概率论

    数论

    判断质数★

    线性代数

    论证

    博弈

    判断先手处于“必胜态”还是“必败态”
    2类的思考方式：

  • 经验分析：见过类似的题目，猜一个性质，然后去证明该性质是否可推广。

  • 状态分析：根据题目给定的规则是判断「胜利」还是「失败」来决定优先分析「必胜态」还是「必败态」时具有何种性质，然后证明性质是否可推广。

    最大公约数gcd★

    1. public int gcd(int x, int y) {
    2.   return y > 0 ? gcd(y, x % y) : x;
    3. }

    最小公倍数lcm

    摩尔投票法★

    求中位数/众数

多数投票算法(Boyer-Moore Algorithm)

快速幂★

递归思想

参考资料