在 Devin 中试用 DeepWiki 处理私有仓库
DeepWiki

kdn251/面试

菜单

算法参考

相关源文件

本页面全面概述了 Interviews 仓库中实现的算法。它涵盖了基本的算法范式、它们的实现以及时间复杂度分析。有关这些算法操作的数据结构，请参阅数据结构参考。

目的与范围

算法参考是针对编程面试中常用算法的技术指南。它侧重于

  1. 算法分类和选择策略
  2. 时间和空间复杂度分析
  3. 实现模式和示例
  4. 不同问题类型中常用的算法范式

来源： README.md188-286

算法分类

本仓库中的算法按范式和技术进行组织。下图展示了主要的算法分类

算法范式层次结构

来源： README.md188-286

时间与空间复杂度

算法效率主要通过时间和空间复杂度分析来衡量。该仓库提供了带有文档复杂度的实现，以帮助工程师为特定问题选择合适的算法。

常见时间复杂度类别

时间复杂度比较表

复杂性姓名示例算法
O(1)常量哈希表操作，栈/队列操作
O(log n)对数级二分查找，BST操作
O(n)线性级线性查找，数组遍历
O(n log n)线性对数高效排序（快速排序，归并排序）
O(n²)平方级简单排序（冒泡，插入，选择）
O(2ⁿ)指数级递归斐波那契数列，幂集生成
O(n!)阶乘排列，暴力旅行推销员问题

来源： README.md330-353

排序算法

排序算法以特定顺序（通常是升序或降序）排列元素。该仓库实现了几种具有不同性能特点的关键排序算法。

关键排序算法

快速排序

  • 稳定性: 否
  • 时间复杂度:
    • 最佳情况: O(n log n)
    • 最差情况: O(n²)
    • 平均情况: O(n log n)
  • 方法: 选择一个枢轴元素并围绕它划分数组

归并排序

  • 稳定性: 是
  • 时间复杂度:
    • 最佳/最差/平均情况: O(n log n)
  • 方法: 将数组分成两半，分别排序，然后合并它们

桶排序

  • 时间复杂度:
    • 最佳情况: Ω(n+k)
    • 最差情况: O(n²)
    • 平均情况: Θ(n+k)
  • 方法: 将元素分配到桶中，对每个桶进行排序，然后连接起来

基数排序

  • 时间复杂度:
    • 最佳/最差/平均情况: O(nk)
  • 方法: 通过处理单个数字或字符来排序元素

来源： README.md192-228

图算法

图算法解决与顶点（节点）和边相关的问题。该仓库包含了遍历、最短路径和最小生成树算法的实现。

图遍历

深度优先搜索（DFS）

  • 时间复杂度: O(|V| + |E|)
  • 方法: 在回溯之前尽可能深入地探索每个分支
  • 实现: 使用栈（通常通过递归隐式实现）

广度优先搜索 (BFS)

  • 时间复杂度: O(|V| + |E|)
  • 方法: 首先探索邻居节点，然后移动到下一层
  • 实现: 使用队列

拓扑排序

  • 时间复杂度: O(|V| + |E|)
  • 方法: 对顶点进行线性排序，使得对于每条边 (u,v)，u 都在 v 之前
  • 应用: 任务调度，依赖解析

来源： README.md232-241 README.md245-248

最短路径算法

Dijkstra 算法

  • 时间复杂度: O(|V|²)
  • 方法: 查找图中从源点到所有其他节点的最短路径
  • 限制: 无法处理负权边

Bellman-Ford 算法

  • 时间复杂度:
    • 最佳情况：O(|E|)
    • 最坏情况：O(|V||E|)
  • 方法: 计算从源点到所有其他节点的最短路径
  • 优点: 可以处理带有负权边的图

Floyd-Warshall 算法

  • 时间复杂度: O(|V|³)
  • 方法: 查找所有节点对之间的最短路径
  • 特点: 动态规划方法

来源： README.md250-273

最小生成树算法

普里姆算法

  • 时间复杂度: O(|V|²)
  • 方法: 每次添加一条边，从任意顶点开始构建最小生成树（MST）
  • 实现: 使用优先队列

克鲁斯卡尔算法

  • 时间复杂度：O(|E|log|V|)
  • 方法: 按边权递增顺序添加边，跳过那些会形成环的边
  • 实现: 使用并查集数据结构

来源： README.md275-287

动态规划

动态规划（DP）通过将复杂问题分解为更简单的子问题来解决它们。它存储子问题的结果，以避免重复计算。

示例：打家劫舍问题

问题：你计划沿着一条街抢劫房屋。每间房屋都藏有一定数量的钱，但由于安全系统，你不能抢劫相邻的房屋。找出你可以抢劫的最大金额。

解决方案方法

  • 状态定义: dp[i] = 抢劫到第 i 间房屋为止可以获得的最大金额
  • 递推关系: dp[i] = max(dp[i-2] + nums[i], dp[i-1])
    • 要么抢劫当前房屋（并获取到第 i-2 间房屋为止的最大值），或者
    • 跳过当前房屋（并获取到第 i-1 间房屋为止的最大值）

实现

完整解决方案可在代码库中的多个实现中找到

来源： leetcode/dynamic-programming/HouseRobber.java1-26 company/airbnb/HouseRobber.java1-26 company/linkedin/HouseRobber.java1-26

贪心算法

贪心算法在每一步都做出局部最优选择，旨在找到全局最优。它们效率高但并非总能保证找到最优解。

主要特点

  1. 最优子结构: 一个最优解包含其子问题的最优解
  2. 贪心选择性质: 通过做出局部最优选择可以构建一个全局最优解

示例：找零问题

  • 问题: 给定不同面额的硬币和一个目标金额，找出所需的最少硬币数量
  • 方法: 重复选择不超过剩余金额的最大面额硬币
  • 对于硬币 {1, 5, 10, 25} 和目标金额 41
    • 开始时使用 0 枚硬币，剩余金额 = 41
    • 取 25¢：使用 1 枚硬币，剩余金额 = 16
    • 取 10¢：使用 2 枚硬币，剩余金额 = 6
    • 取 5¢：使用 3 枚硬币，剩余金额 = 1
    • 取 1¢：使用 4 枚硬币，剩余金额 = 0

来源： README.md290-307

回溯

回溯算法是一种通过逐步构建候选解并在确定某个候选解无法导出有效解时放弃它的方法，以找到计算问题的所有（或部分）解的算法。

常见回溯问题

  • 排列: 查找元素的所有可能排列
  • 组合: 查找元素的所有可能组合
  • 子集和: 查找和为目标值的子集
  • N皇后: 在 N×N 棋盘上放置 N 个皇后，使其互不攻击

实现模式

backtrack(candidate):
    if candidate is a complete solution:
        add to list of solutions
        return
    
    for next_candidate in all possible next candidates:
        if next_candidate is valid:
            add next_candidate to current solution
            backtrack(next_candidate)
            remove next_candidate from current solution

来源： README.md398-401

位操作

位操作涉及在位级别应用运算，以更高效地执行任务。该仓库包含了技术面试中常用的位操作。

常见位操作

  • 测试第 k 位: s & (1 << k)
  • 设置第 k 位: s |= (1 << k)
  • 关闭第 k 位: s &= ~(1 << k)
  • 翻转第 k 位: s ^= (1 << k)
  • 乘以 2ⁿ: s << n
  • 除以 2ⁿ: s >> n
  • 交集: s & t
  • 并集: s | t
  • 集合差集: s & ~t
  • 提取最低设置位: s & (-s)
  • 提取最低未设置位: ~s & (s + 1)
  • 交换值
    x ^= y;
y ^= x;
x ^= y;

来源： README.md309-328

二分查找能高效地在排序数组中找到目标值。它通过重复地将搜索空间一分为二来工作。

主要特点

  • 时间复杂度: O(log n)
  • 空间复杂度: 迭代实现为 O(1)，递归实现为 O(log n)
  • 要求: 集合必须是已排序的

应用程序

  • 在排序数组中搜索
  • 查找插入点
  • 对排序数据进行范围查询
  • 数学函数中的求根

来源： README.md402-407

分治法

分治算法将问题分解为更小的子问题，独立解决它们，然后将结果合并。

主要特点

  • 问题被划分为不重叠的子问题
  • 子问题独立解决
  • 子问题的解被组合起来形成最终解

常见算法

  • 归并排序: 将数组一分为二，对两半排序，然后合并
  • 快速排序: 围绕枢轴划分数组，然后对分区进行排序
  • 二分查找: 将搜索空间一分为二，每次淘汰一半
  • Strassen 矩阵乘法: 减少递归调用次数

来源： README.md434-436

结论

本参考资料概述了 Interviews 仓库中实现的核心算法。有关特定算法类别的更详细解释，请参阅以下页面

在准备技术面试时，理解这些算法范式及其实现对于高效解决复杂问题至关重要。