学习路径：

阶段一：算法入门

• 我们需要熟悉各种数据结构的特点和用法，学习不同算法的原理、流程、用途和效率等方面的内容。

阶段二：刷算法题

• 建议从热门题目开刷，先积累至少 100 道题目，熟悉主流的算法问题。初次刷题时，“知识遗忘”可能是一个挑战，但请放心，这是很正常的。我们可以按照“艾宾浩斯遗忘曲线”来复习题目，通常在进行 3～5 轮的重复后，就能将其牢记在心。

阶段三：搭建知识体系

数据结构和算法

线性表

• 数组
• 链表
  • 单链表
  • 双向链表
  • 循环链表
  • 双向循环链表
  • 静态链表
• 栈
  • 顺序栈
  • 链式栈
• 队列
  • 普通队列
  • 双端队列
  • 阻塞队列
  • 并发队列
  • 阻塞并发队列

树

labuladong hello-algo

排序算法

• 定义：
  • 排序算法（sorting algorithm）用于对一组数据按照特定顺序进行排列。
  • 通过排序算法得到有序数据，通常能够被更高效地查找、分析和处理。

排序算法评价维度：

搜索

• 定义：
  • 搜索算法（searching algorithm）用于在数据结构（例如数组、链表、树或图）中搜索一个或一组满足特定条件的元素

分类：

• 暴力搜索
• 自适应搜索

暴力搜索：

• 思路：遍历数据结构的每个元素
• 遍历策略：
  • 线性搜索：适用于数组和链表
  • 广度、深度优先搜索：适用于树和图
• 优缺点：
  • 优点：简单且通用性好，无须对数据做预处理和借助额外的数据结构
  • 缺点：时间复杂度为$O(n)$

二分查找

定义：

• 二分查找（binary search）是一种基于分治策略的高效搜索算法。
• 它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

具体操作：

1. 先初始化指针 $i = 0$ 和 $j = n - 1$ ，分别指向数组首元素和尾元素，代表搜索区间 $[0, n - 1]$
2. 计算中点索引 $m = \lfloor {(i + j) / 2} \rfloor$ （其中 $\lfloor \: \rfloor$ 表示向下取整操作）
3. 判断 nums[m] 和 target 的大小关系，分为以下三种情况：
   1. 当 nums[m] < target 时，说明 target 在区间 $[m + 1, j]$ 中，因此执行 $i = m + 1$ 。
   2. 当 nums[m] > target 时，说明 target 在区间 $[i, m - 1]$ 中，因此执行 $j = m - 1$ 。
   3. 当 nums[m] = target 时，说明找到 target ，因此返回索引 $m$ 。
4. 重复2、3步骤，一直未找到元素，则搜索区间缩小为空。此时返回 $-1$ 。
5. 注意项：由于 $i$ 和 $j$ 都是 int 类型，因此 $i + j$ 可能会超出 int 类型的取值范围。为了避免大数越界，我们通常采用公式 $m = \lfloor {i + (j - i) / 2} \rfloor$ 来计算中点

作用：

• 用于树、图的遍历

广度优先：

• 广度优先遍历通常借助队列来实现。队列遵循先进先出的规则，而广度优先遍历则遵循逐层推进的规则
• 代码实现（树）：

  /* 层序遍历 */
  func levelOrder(root *TreeNode) []any {
      // 初始化队列，加入根节点
      queue := list.New()
      queue.PushBack(root)
      // 初始化一个切片，用于保存遍历序列
      nums := make([]any, 0)
      for queue.Len() > 0 {
          // 队列出队
          node := queue.Remove(queue.Front()).(*TreeNode)
          // 保存节点值
          nums = append(nums, node.Val)
          if node.Left != nil {
              // 左子节点入队
              queue.PushBack(node.Left)
          }
          if node.Right != nil {
              // 右子节点入队
              queue.PushBack(node.Right)
          }
      }
      return nums
  }

搜索树查找

• 直接使用搜索树的节点有序、节点大小关系等特性
• 本质思想根二分查找一致，通过有序的先验条件，快速排除1/2、1/M的节点，M为树的阶数

过程：

• 基于搜索树搜索：
  • 二叉搜索树：比较target和节点值大小；小于节点，继续找左子树，大于节点，继续找右子树；相等则找到，或者访问到叶子节点也未找到。
  • B树：比较target和节点值大小；根据值所在区间，到对应子树继续查找；如果节点中有根target相等，则可以在该节点找到target信息，或者访问到叶子节点也未找到。
  • B+树：比较非叶子节点和target，根据值所在区间，到对应子树继续查找；因为只有叶子节点存数据，一直要找到叶子节点，才能找到target的具体信息

一、什么是递归？

利用了函数栈实现

1. 递归是一种非常高效、简洁的编码技巧，一种应用非常广泛的算法，比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。
2. 方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。
3. 基本上，所有的递归问题都可以用递推公式来表示，比如

    f(n) = f(n-1) + 1; 
    f(n) = f(n-1) + f(n-2);
    f(n) = n*f(n-1);

计数、桶、基数

桶排序（Bucket Sort）：

• 思想：它通过设置一些具有有限数量、大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并

• 稳定排序、非原地排序，需要借助k个桶和n个元素的数组

• 非比较排序算法

• 算法流程：条件 一个长度为 $n$ 的数组，其元素是范围 $[0, 1)$ 内的浮点数

  1. 初始化 $k$ 个桶，将 $n$ 个元素分配到 $k$ 个桶中。
  2. 对每个桶分别执行排序（这里采用编程语言的内置排序函数）。
  3. 按照桶从小到大的顺序合并结果。

• 桶排序的优化：

  • 将元素均匀分配到各个桶中，时间复杂度趋近于$O(n)$。可以借助值的概率分布。

• 图解：

• 代码：

  /* 桶排序 */
  func bucketSort(nums []float64) {
      // 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
      k := len(nums) / 2
      buckets := make([][]float64, k)
      for i := 0; i < k; i++ {
          buckets[i] = make([]float64, 0)
      }
      // 1. 将数组元素分配到各个桶中
      for _, num := range nums {
          // 输入数据范围为 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
          i := int(num * float64(k))
          // 将 num 添加进桶 i
          buckets[i] = append(buckets[i], num)
      }
      // 2. 对各个桶执行排序
      for i := 0; i < k; i++ {
          // 使用内置切片排序函数，也可以替换成其他排序算法
          sort.Float64s(buckets[i])
      }
      // 3. 遍历桶合并结果
      i := 0
      for _, bucket := range buckets {
          for _, num := range bucket {
              nums[i] = num
              i++
          }
      }
  }