参考链接：https://zhuanlan.zhihu.com/p/74472146

1. 图的基本知识

  • 图的概念

图：由节点（顶点）和连接每对节点的边所构成的图形。
image.png

  • 图的分类
    • 按节点之间的连接程度，给两节点连接的边进行加权，可分为加权图和非加权图

image.png

  • 按节点之间的传递方向，可分为有向图和无向图

image.png

  • 按是否连通（在图中任意两个节点，都可以找到路径将它们连接），可分为连通图和非连通图

image.png

  • 图的搜索方式（根据搜索顺序不同）
    • 广度优先搜索：根据离起点的距离，按照由远及近的顺序对各节点进行搜索。
    • 深度优先搜索：沿着一条路径不断往下搜索直到不能继续为止，然后再折返，开始搜索下一条路径。

  • 图的最短路径问题：要在两个节点的所有路径中，找到一条所经过的边的权重总和最小的路径。相关算法有：“贝尔曼-福特算法”，“狄克斯特拉算法”和“A* 算法”三种。

    2. 广度优先搜索（BFS - Broad First Search）

    广度优先搜索中，保存一个存放候补节点的队列（先进先出），对先进入队列的节点进行优先搜索。
    image.png
    广度优先搜索：可以判断两个节点是否存在路径，还可以找出两个节点间的最短路径（非加权图）。

    3. 深度优先搜索（DFS - Deep First Search）

    深度优先搜索中，保存候补节点的是栈（先进后出），最先进入栈的候补节点最后搜索。
    image.png
    深度优先搜索：可以判断图是否为连通图。

    4. 利用广度/深度优先搜索的扩展题

    给定有n个节点的树，有以下几个特征：

    • 任意两个节点之间有且只有一条路径
    • 树中共有n-1条不同的边
    • 叶子节点的度为1，非叶子节点的度至少为2
    • 树的高度由根节点到叶子结点的最大距离决定

要找到最小高度树的根节点列表。
结论：

  • 设dist[x][y]表示从节点 x 到节点 y 的距离，假设树中距离最长的两个节点为（x, y）,它们之间的距离为maxdist = dist[x][y]，则可以推出以任意节点构成的树最小高度一定为 minheight = maxdist / 2，且最小高度树的根节点一定在节点 x 到节点 y 的最长路径上。
  • 假设 x 到 y 的最长路径的 m 个节点依次是：p1 -> p2 -> … -> pm，最长路径的长度为 m - 1，那么
    • 如果 m 为偶数，此时最小高度树的根节点为 算法知识汇总 - 图7或者算法知识汇总 - 图8，且此时最小的高度为 m / 2；
    • 如果 m 为奇数，此时最小高度树的根节点为算法知识汇总 - 图9，且此时最小的高度为 m - 1 / 2；

  • 如何找出树中路径最长的两个叶子节点呢，可以采用广度优先搜索或者深度优先搜索算法去找。

    • 以任意节点 p 为初始点，利用广度优先搜索或者深度优先搜索找到以 p 为起点的最长路径的终点 x
    • 已节点 x 出发，找到以 x 为起点的最长路径的终点 y
    • 那么，x 到 y 之间的路径即为图中的最长路径，找到最长路径的中间节点即为根节点。

      5. N叉树的层序遍历

      层序遍历：从左到右，逐层遍历。
      image.png
      层序遍历的题目，一般采用广度优先搜索（BFS），BFS的核心是构建双端队列，判断队列不为空的情况下，取出队列头部的元素，根据条件在尾部添加元素。 ```java public List> levelOrder(Node root) { List> ans = new ArrayList<>(); // 创建一个双端数组 Deque d = new ArrayDeque<>(); if (root != null) {
      1. // 在双端队列尾部插入一个元素
      2. d.addLast(root);
      } // 队列不为空时持续取值 while (!d.isEmpty()) {
      1. // 获取队列的元素个数
      2. int size = d.size();
      3. List<Integer> list = new ArrayList<>();
      4. // 取出队列中前size个元素
      5. while (size-- > 0) { // 先取值再做减法运算
      6.     Node t = d.pollFirst();
      7.     // 将当前节点的子节点加入到队列中
      8.     for (Node node : t.children) {
      9.         d.addLast(node);
      10.     }
      11.     // 将节点t的值加入到list中
      12.     list.add(t.val);
      13. }
      14. // 将list添加到ans
      15. ans.add(list);
      } return ans; }

    class Node { // 节点元素的值 public int val; // 子节点列表 public List children;

    public Node() {}

    public Node(int _val) {

    1.    val = _val;

    }

    public Node(int _val, List _children) {

    1.    val = _val;
    2.    children = _children;

    } } ```

    6. 字典序

    题目：给你一个整数n，按字典序返回范围[1, n]内的所有整数。
    对于任何一个整数number，它的下一个字典序整数对应下边的规则：

  • 如果 number 10 <= n，那么 number 10 为 number 的下一个字典序整数；

  • 如果 number % 10 = 9 或者 number + 1 > n，那么说明末尾的数位已经搜索完成，退回上一位，即 number = number / 10，然后继续判断直到 number % 10 != 9 且 number + 1 <= n 为止，那么 number + 1是下一个字典序整数。

    7. 前缀和

    前缀和定义：给定一个数列算法知识汇总 - 图11，A 的前缀和的数列 S 的通项公式为：算法知识汇总 - 图12
    A = [4,5,6,7]
    prefixSum = [4,9,15,22]

    8. 位运算

    | 位运算符 | 运算法则 | 常用场景 | | —- | —- | —- | | 按位与：& | 相同位的两个数字都为1，结果为1；若有一个不为1，结果为0。
    真真为真，真假为假，假假为假 | a & 1：取 a 的二进制数的最末位，用于判断 a 是奇数还是偶数 | | 按位或：| | 相同位只要一个为1，结果为1。
    真真为真，真假为真，假假为假 | a | 1：强制将 a 的二进制数最末位变成1。
    (a | 1) - 1 ：强行将 a 变成最接近的偶数 | | 按位异或：^ | 相同位不同结果为1；相同结果为0。
    真真为假，真假为真，假假为假 | 两次异或同一个数，结果不变。
    (a ^ b) ^ b = a | | 按位取反：~ | 二进制数中0和1全部取反 | 需要注意无符号取反还是有符号取反 | | 左移：<< | a << b ：a 转为二进制后左移 b 位（在后面添 b 个0） | a 乘以 2 的 b 次方 | | 带符号右移：>> | a >> b：a 转为二进制右移 b 位（去掉末 b 位） | a 除以 2 的 b 次方（取整）
    用于二分查找、堆的插入操作等 | | 无符号右移：>>> | | |

9. 滑动窗口

滑动窗口是一种基于双指针的思想，两个指针指向的元素之间形成一个窗口。
窗口的形成：

  1. 初始时，左右指针left、right都指向数组索引为0的位置
  2. 开始遍历数组元素，当右指针的位置超过数组长度时结束循环，否则向右移动右指针，更新窗口内的区间位置；
  3. 当窗口内的区间数据满足要求时，移动右指针，直到不满足要求为止，保持右指针，向右移动左指针，直到满足要求，停止移动
  4. 执行第2步

image.png
image.png
使用场景：获取满足条件的连续子数组等
题目：给定一个正整数数组 nums 和一个整数 k，请返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

  1.     public int numSubarrayProductLessThanK(int[] nums, int k) {
  2.         int left = 0, right = 0, ans = 0, mul = 1, length = nums.length;
  3.         if (k <= 1) {
  4.             return 0;
  5.         }
  6.         while (right < length) {
  7.             mul *= nums[right];
  8.             while (mul >= k) {
  9.                 mul /= nums[left];
  10.                 left++;
  11.             }
  12.             ans += right - left + 1;
  13.             right++;
  14.         }
  15.         return ans;
  16.     }