Running Noob

• Fork/Join：线程池的实现，体现是分治思想，适用于能够进行任务拆分的 CPU 密集型运算，用于并行计算。

  • 任务拆分：将一个大任务拆分为算法上相同的小任务，直至不能拆分可以直接求解。跟递归相关的一些计算，如归并排序、斐波那契数列都可以用分治思想进行求解。

  • Fork/Join 在分治的基础上加入了多线程，把每个任务的分解和合并交给不同的线程来完成，提升了运算效率。

  • ForkJoin 使用 ForkJoinPool 来启动，ForkJoinPool 是一个特殊的线程池，默认会创建与 CPU 核心数大小相同的线程池。

  • 如果要得到任务的返回值，那么任务就继承 RecursiveTask，否则可以选择继承 RecursiveAction。

• 摩尔投票在以下场景中十分有效：

  • 从一组数据中找到出现次数超过半数的数据。
  • 从一组数据中找到出现次数超过三分之一的数据。
  • ……

  空间复杂度仅为 O(1)。

• 由于在大厂笔试中多次出现等差数列的相关问题，所以在这里专门记录等差数列相关的笔试题，包括：
  • 判断能否形成等差数列
  • 最长等差数列
  • 等差数列划分

• 最小生成树
  • prim 算法
  • kruskal 算法

• 并查集可以解决什么问题：连通性问题。
  • 可以将两个元素添加到同一个集合中。
  • 可以判断两个元素在不在同一个集合中。