数据结构与算法

关于数据结构与算法的思维导图，涵盖了复杂度分析、二叉树、动态规划、排序、递归、二分查找、线性结构，希望这份思维导图都会对你有所帮助。

数据结构与算法

• 复杂度分析
  • 表示随着数据规模的变化算法在时间和空间两个维度上的性能，使用 O() 表示，括号内的数值越低越好
  • 时间复杂度
    • 运算过程与数据规模的关系
    • 比如算法有一个循环说明所有数据都要被遍历一遍则事件复杂度为 O(n)
    • 如果是两层循环则所有的数据需要遍历两边则时间复杂度为 O（n^2）
  • 空间复杂度
    • 主要看为了解决问题额外引入的数据结构与测试集数据规模的关系
    • 引入常量基的遍历则空间复杂度为 O(1)
    • 引入和数据规模一样的数据结构，比如集合，这空间复杂度为 O(n)
  • 鱼和熊掌不可兼得，时间和空间亦是如此，通常会牺牲空间换取事件，或者牺牲时间获取空间
• 二叉树
  • 二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。
  • 二叉树的遍历
    • 前序遍历 root -> root.left -> root.right
    • 中序遍历:root.left -> root -> root.right
    • 后序遍历：root.left -> root.right -> root
    • 可以看到 X 序以 root 节点位置决定的，root 在前就是前序，在中间就是中序……而子节点的顺序都是从左到右
    • 层遍历
      • 逐层遍历是一种广度优先算法
      • 广度优先搜索是一种广泛在树和图中运用的遍历搜索算法
      • 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推
      • Leetcode 题目
  • 使用递归解决问题
    • 自顶向上：前序遍历解决问题
      • 判断条件
        • 你能确定一些参数，从该节点自身解决出发寻找答案吗？
        • 你可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗？
        • 都需要一个全局变量或者反复传递的参数存储中间结果
      • 路径总和
    • 自底向下：后续遍历解决
      • 判断条件
        • 对于树中的任意一个节点，如果你知道它子节点的答案，你能计算出该节点的答案吗？
      • 二叉树的最大深度
  • 还原二叉树
    • 如果是同一二叉树所有 [左子树集合] 和 [右子数集合] 的长度是相等的
      • 前序遍历：根节点 [左子树集合] [右子数集合]
      • 后序遍历：[左子树集合] [右子树集合] 根节点
      • 用于确定根节点
      • 中序遍历：[左子树集合] 根节点 [右子树集合] ： 根据根节点位置确定左右边界
      • 这是解题的关键，同这些关系推导出递归公式
    • 使用 Map 存储中序遍历的结果，快速定位根节点的位置从而明确左右边界
      • key ： 节点的值
      • value：节点在数组的索引
    • 从中序与后序遍历序列构造二叉树
      • 粉色 = 左子树、红色 = 根节点、绿色 = 右子树
        • is: inorderStart
        • ri = rootIndex
        • ie = inorderEnd
        • ps = postorderStart
        • pe = postorderEnd
    • 从前序与中序遍历序列构造二叉树
• 动态规划
  • 动态规划的核心思想是利用最优子结构和重叠子问题性质对穷举法进行优化，通过将中间结果保存在数组中，实现用空间来换取时间交换，实现程序的快速运行。
  • 特征
    • 重叠子问题
    • 最优子结构
• 排序
  • 比较类排序
    • 交换排序
      • 冒泡排序
        • 算法描述
          • 比较相邻的元素。如果第一个比第二个大，就交换它们两个
          • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
          • 针对所有的元素重复以上的步骤，除了最后一个；
          • 重复步骤1~3，直到排序完成。
    • 插入排序
    • 选择排序
      • 简单选择排序
        • 算法描述
    • 归并排序
  • 非比较类排序
• 递归
  • 当有疑问的时候写下递归公式
  • 只要有可能，就应用记忆化
  • 当堆栈溢出时，尾递归可能会有所帮助。
    • 尾递归通过消除递归带来的堆栈开销，优化了算法的空间复杂度
    • 与非尾递归相比，尾部递归更容易阅读和理解。
• 二分查找
  • 二分查找是一种在每次比较之后将查找空间一分为二的算法。有序是二分查找的先决条件。每次需要查找集合中的索引或元素时，都应该考虑二分查找。如果集合是无序的，我们可以总是在应用二分查找之前先对其进行排序。
  • 二分查找是必考题目，一定要达到信手拈来的程度
  • 模板1：在严格有序数组中寻找一个数，或者插入一个数
    • public int search(int[] nums, int target) { int pivot, left = 0, right = nums.length - 1; while (left pivot = left + (right - left) / 2; if (nums[pivot] == target) { return pivot; } if (nums[pivot] left = pivot + 1; } else { right = pivot - 1; } } return -1; }
    • 题目：x 的平方根
      • 思路还是二分查找，通过不断二分压缩样本空间寻找 val^2 最接近 x 的值
      • 注意寻找的是平方数最近接 x 的 mid
    • 题目：搜索螺旋数组
      • 使用常规二分插查找的 mid 分割数组，判断分割后的两部分那部分有序，使用有序的部分确定二分查找的边界
      • 注意判断 targe 是否在区间内的判断
    • 区分语法
      • 初始条件：left = 0, right = length-1
      • 终止时：left > right
      • 向左查找：right = mid-1
      • 向右查找：left = mid+1
    • 关键属性
      • 查找条件可以在不与元素的两侧进行比较的情况下确定
      • 不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。
      • 循环结束时候 left = right + 1 将返回 target 右邻居下标
  • 模板2：在严格有序数组中找到某个数第一次出现的位置或寻找第一个大于等于某个数的位置
    • 区分语法
      • 初始条件：left = 0, right = length
      • 终止时：left == right
      • 向左查找：right = mid
      • 向右查找：left = mid+1
    • 关键属性
      • 查找条件需要访问元素的直接右邻居。此时 right = length - 1
      • 需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。
      • 循环结束时候 left = right 将返回 target 的坐标
  • 模板3：在选严格递增后严格递减的数组中寻找最大值（不常见，用于解决特定题型）
• 线性结构
  • 数组
    • Top K 问题
      • 解题思路就是排序，最简单的办法就是上图的使用 API 搞定，当然面试的时候这么写时过不了的
      • 使用 PriorityQueue 有限队列
        • 优先级队列会对数据进行排序，小的在头大的在尾
        • 代码也很简单：时间和空间都是 O(n)
      • 此题考查的是排序算法，只有手写排序才能迎合了面试官考点
    • 删除排序数组中的重复项
      • 体验是排序数据。基本思路是双指针，关键是启始值为 1 使用当前值比较后一个 -> num[i] != num[i-1] .时间O(n),空间O(1)
    • 删除排序数组中的重复项 II
      • 此题比上一题难，允许存在两个相同元素，体验依旧是排序数组。想到的还是双指针，但是实现难度不小
      • 更牛逼的解题方式：比较大小，LeetCode 总站上大佬就是牛逼.时间O(n),空间O(1)
      • 据此得出删除排序数组中的k个重复项目标
    • 颜色分类- 荷兰国旗问题
    • 合并两个有序数组
      • 正着不行，咱反着来。从尾部遍历.时间O(n),空间O(1)