编辑“︁常见算法面试题”︁

{{DISPLAYTITLE:常见算法面试题}}

== 简介 ==
'''算法面试题'''是技术面试中用于评估候选人编程能力、逻辑思维和问题解决技巧的核心环节。这类问题通常涉及[[数据结构]]操作、[[算法]]设计、时间复杂度优化等关键概念，常见于互联网企业（如FAANG）和顶级科技公司的招聘流程。本节将系统介绍高频算法面试题型、解题框架及实战技巧。

== 题型分类 ==
=== 1. 数组与字符串 ===
{{Main|数组|字符串}}
* '''典型问题'''：两数之和、最长无重复子串、旋转矩阵
* '''考察重点'''：双指针、滑动窗口、边界条件处理

<syntaxhighlight lang="python">
# 示例：两数之和（LeetCode 1）
def two_sum(nums, target):
    hashmap = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hashmap:
            return [hashmap[complement], i]
        hashmap[num] = i
    return []

# 输入输出示例
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # 输出: [0, 1]
</syntaxhighlight>

=== 2. 链表操作 ===
{{Main|链表}}
* '''典型问题'''：反转链表、环形链表检测、合并K个有序链表
* '''技巧'''：虚拟头节点、快慢指针、递归

<mermaid>
graph LR
    A[1] --> B[2]
    B --> C[3]
    C --> D[4]
    D -->|原指针| A
</mermaid>
环形链表检测可通过Floyd判圈算法实现：

<syntaxhighlight lang="java">
// Java实现环形链表检测（LeetCode 141）
public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}
</syntaxhighlight>

=== 3. 树与图 ===
{{Main|二叉树|图论}}
* '''高频问题'''：二叉树遍历、最近公共祖先、拓扑排序
* '''解法模式'''：DFS/BFS、分治法、Union-Find

<math>
\text{二叉树节点数计算公式：} N = 1 + N_{\text{left}} + N_{\text{right}}
</math>

=== 4. 动态规划 ===
{{Main|动态规划}}
* '''经典问题'''：背包问题、最长递增子序列、编辑距离
* '''关键步骤'''：状态定义、转移方程、初始化

<syntaxhighlight lang="cpp">
// C++解决斐波那契数列（记忆化递归）
int fib(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}
</syntaxhighlight>

== 解题方法论 ==
=== 四步解题法 ===
# '''理解题意'''：明确输入输出格式及边界条件
# '''暴力解法'''：先给出最直观的解决方案
# '''优化分析'''：识别重复计算或冗余操作
# '''代码实现'''：选择合适的数据结构进行优化

=== 复杂度分析 ===
{| class="wikitable"
|+ 常见时间复杂度对比
! 复杂度 !! 示例算法 !! 适用场景

| <math>O(1)</math> || 哈希查找 || 常量操作
|-
| <math>O(\log n)</math> || 二分查找 || 有序数据
|-
| <math>O(n)</math> || 线性扫描 || 遍历需求
|-
| <math>O(n^2)</math> || 冒泡排序 || 小规模数据
|}

== 实战案例 ==
=== 案例：设计LRU缓存 ===
'''问题描述'''：实现一个基于LRU（最近最少使用）策略的缓存系统，要求<code>get</code>和<code>put</code>操作均为<math>O(1)</math>时间复杂度。

'''解决方案'''：
* 哈希表 + 双向链表
* 链表维护访问顺序，哈希表实现快速查找

<syntaxhighlight lang="python">
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        node = self.cache.get(key)
        if not node: return -1
        self._move_to_head(node)
        return node.value
</syntaxhighlight>

== 常见陷阱 ==
* '''Off-by-one错误'''：循环边界处理不当
* '''整数溢出'''：未考虑32位整数限制
* '''浅拷贝问题'''：对象引用传递导致的修改
* '''尾递归优化'''：语言特性支持差异

== 进阶建议 ==
* '''系统训练'''：建议完成LeetCode精选150题
* '''模式识别'''：总结常见题型模板（如回溯框架）
* '''模拟面试'''：使用Pramp等平台进行实战演练
* '''论文延伸'''：阅读《算法导论》相关章节

{{算法学习路径导航}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:算法竞赛与面试]]