大厂机考——各算法与数据结构详解

哈希

​​学科领域​​：计算机科学、密码学、数据结构
​​定义​​：通过哈希函数将任意长度的输入映射为固定长度的输出（哈希值），用于快速查找和数据完整性验证。常见结构包括哈希表（如HashMap）和哈希算法（如SHA-256）。
​​应用​​：密码存储（如加盐哈希）、数据库索引、缓存系统、区块链（验证交易）。
​​联系​​：与数组结合形成哈希表，常与链表结合解决哈希冲突（链地址法）。
案例：以循环遍历算法为例，考虑双循环嵌套算法和哈希表算法

哈希表算法：

class Solution(object):def twoSum(self, nums, target):# 创建一个空的哈希表（字典），用于存储 {数值: 索引} 的键值对hash_map = {}  # 使用 enumerate 函数遍历数组 nums，同时获取元素的索引 i 和元素值 numfor i, num in enumerate(nums):# 计算当前元素 num 与目标值 target 的差值，这个差值被称为补数complement = target - num# 检查补数是否已经存在于哈希表中# 这样做可以确保不会重复使用同一个元素if complement in hash_map:# 如果补数存在于哈希表中，说明已经找到了两个数的和等于目标值# 返回补数在哈希表中对应的索引和当前元素的索引return [hash_map[complement], i]# 将当前元素及其索引存入哈希表中# 这样后续遍历到其他元素时，如果其补数是当前元素，就可以通过哈希表快速找到当前元素的索引hash_map[num] = i# 如果遍历完整个数组都没有找到满足条件的两个数，返回一个空列表return []

双指针

​​学科领域​​：算法设计与优化
​​定义​​：利用两个指针（通常起始位置不同）在数组或链表中协同遍历，降低时间复杂度。分为同向（快慢指针）和反向（左右指针）两种模式。
​​应用​​：有序数组去重、两数之和、链表环检测。
​​联系​​：常与滑动窗口结合处理子数组问题，如最小覆盖子串。

滑动窗口

学科领域​​：算法优化
​​定义​​：通过动态调整窗口的左右边界，在固定或可变窗口内高效处理连续子序列问题，时间复杂度通常为O(n)。
​​应用​​：最长无重复子串、子数组最大和、频率统计（如字母异位词）。
​​联系​​：基于双指针实现，常用于字符串和数组问题。

子串

​​学科领域​​：字符串算法
​​定义​​：字符串中连续字符组成的序列。处理子串问题常需高效匹配或统计，如KMP算法优化匹配过程。
​​应用​​：文本搜索、DNA序列比对、数据压缩（如Huffman编码）。
​​联系​​：与哈希结合用于模式匹配（如Rabin-Karp算法），与动态规划结合求解最长公共子序列。

普通数组

学科领域​​：数据结构基础
​​定义​​：内存中连续存储的线性结构，支持随机访问。分为静态数组（固定大小）和动态数组（如Python列表）。
​​应用​​：矩阵存储、排序算法（如快速排序）、数据缓存。
​​联系​​：作为其他结构的基础，链表和树常转化为数组实现（如堆的数组表示）。

矩阵

​​学科领域​​：线性代数、图像处理
​​定义​​：二维数组，常用于表示网格数据或数学变换。特殊操作包括转置、旋转（如顺时针90度）。
​​应用​​：图像处理（像素操作）、图论中的邻接矩阵、动态规划中的状态表（如路径计数）。
​​联系​​：与图论结合分析网络结构，与动态规划结合处理多维问题。

链表

​​学科领域​​：数据结构
​​定义​​：通过指针连接的非连续节点序列，分为单链表、双向链表和循环链表。优势在于动态插入/删除。
​​应用​​：LRU缓存实现、多项式表示、操作系统进程调度。
​​联系​​：与哈希结合实现链地址法，与双指针结合检测环或反转链表。

二叉树

​​学科领域​​：数据结构、算法
​​定义​​：每个节点最多有两个子节点的树结构，包括二叉搜索树（BST）、平衡树（如AVL）。
​​应用​​：数据库索引（B树）、哈夫曼编码、表达式解析（语法树）。
​​联系​​：与图论中的树结构相通，遍历算法（DFS/BFS）为图算法基础。

图论

​​学科领域​​：离散数学、计算机科学
​​定义​​：研究顶点（节点）和边（关系）构成的网络结构，分为有向图、无向图、加权图等。
​​应用​​：社交网络分析、路径规划（Dijkstra算法）、拓扑排序（任务调度）。
​​联系​​：与动态规划结合解决最短路径问题，与回溯结合处理图的遍历。

回溯

​​学科领域​​：算法设计
​​定义​​：通过试错法穷举所有可能解，剪枝无效路径。本质是深度优先搜索（DFS）的优化。
​​应用​​：N皇后问题、数独求解、组合排列生成。
​​联系​​：与动态规划互补，后者记录子问题解避免重复计算。

二分查找

​​学科领域​​：算法优化
​​定义​​：在有序序列中通过折半缩小搜索范围，时间复杂度O(log n)。
​​应用​​：有序数组查找、数值分析（求根）、资源分配优化。
​​联系​​：与双指针结合实现旋转数组查找，与分治法思想相通。

栈

​​学科领域​​：数据结构
​​定义​​：后进先出（LIFO）的线性结构，支持压栈（push）和弹栈（pop）操作。
​​应用​​：函数调用栈、括号匹配、表达式求值（逆波兰式）。
​​联系​​：与递归算法关联，DFS非递归实现依赖栈结构。

堆

​​学科领域​​：数据结构
​​定义​​：完全二叉树实现的优先级队列，分为最大堆（父节点值最大）和最小堆。
​​应用​​：堆排序、Top K问题（如频率统计）、Dijkstra算法优化。
​​联系​​：与贪心算法结合选择局部最优解，如合并K个有序链表。

贪心算法

​​学科领域​​：算法设计
​​定义​​：每一步选择当前最优解，期望全局最优。需满足贪心选择性质和最优子结构。
​​应用​​：霍夫曼编码、活动选择问题、最小生成树（Prim/Kruskal算法）。
​​联系​​：与动态规划对比，贪心无回溯但可能无法达到全局最优。

动态规划

学科领域​​：运筹学、算法设计
​​定义​​：通过保存子问题解避免重复计算，需满足最优子结构和重叠子问题。
​​应用​​：背包问题、最长公共子序列（LCS）、股票买卖策略。
​​联系​​：与分治法类似，但DP子问题相互依赖；常以表格形式存储状态。

多维动态规划

​​学科领域​​：算法扩展
​​定义​​：状态变量涉及多个维度的DP，如二维背包问题或网格路径问题。
​​应用​​：图像处理（编辑距离）、三维路径规划、资源分配优化。
​​联系​​：基础DP的扩展，空间复杂度较高，常需滚动数组优化。

学科领域与联系总结​​

​​核心学科​​：计算机科学（数据结构与算法）、应用数学（图论、优化）。
​​交叉应用​​：动态规划与图论结合解决路径问题，哈希与密码学结合保障数据安全。
​​技术演进​​：从基础结构（数组/链表）到高级算法（DP/贪心），体现从存储到优化的递进。
​​优化互补​​：如回溯通过剪枝减少搜索空间，而DP通过记忆化避免重复计算，两者在不同场景下互补。
通过理解这些概念的定义、应用及关联，可以更灵活地选择合适方法解决复杂问题。例如，处理字符串匹配时可能联合滑动窗口与哈希；优化路径规划时需结合图论和动态规划。