计算机算法

发表于 2024-12-28 更新于 2025-02-26 分类于算法阅读次数：

本文字数： 2.1k 阅读时长 ≈ 8 分钟

前言

这些东西，没有什么特别好的办法，只能不断练习与理解

测试代码仓库：https://github.com/nimbusking/CoreJavaSample

相关知识点

以下是关于 计算机算法 的高频面试题总结，涵盖 排序算法、数据结构、动态规划、搜索算法 等核心知识点，帮助快速掌握关键题型与解题思路：

一、排序算法

快速排序

原理：分治思想，选取基准元素，将数组分为左右两部分（左边≤基准，右边≥基准），递归排序。
时间复杂度：平均 O(n log n)，最坏 O(n²)（已排序数组）。

代码实现：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

归并排序

原理：分治思想，将数组分为两半，分别排序后合并。
时间复杂度：稳定 O(n log n)，空间复杂度 O(n)。

合并代码：

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:] or right[j:])
    return result

堆排序
- 原理：构建最大堆，交换堆顶与末尾元素，调整堆结构。
- 时间复杂度：O(n log n)，空间复杂度 O(1)。

二、数据结构

链表

反转链表：迭代或递归实现。

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

检测环：快慢指针法（Floyd判圈算法）。

二叉树
- 层次遍历：使用队列实现 BFS。
- 验证二叉搜索树（BST）：中序遍历递增或递归检查节点范围。

哈希表

两数之和：用哈希表存储遍历过的值及其索引。

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
    return []

三、动态规划（DP）

爬楼梯
- 问题：每次爬 1 或 2 阶，到第 n 阶有多少种方法？
- 状态转移方程：dp[i] = dp[i-1] + dp[i-2]，空间优化为 O(1)。
最长递增子序列（LIS）
- 定义：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。
- 优化：二分查找维护单调递增序列，时间复杂度 O(n log n)。
背包问题
- 0-1 背包：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)，空间优化为一维数组。

四、搜索算法

二分查找

模板：

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

变种：查找左边界/右边界（如 bisect_left）。

DFS 与 BFS

DFS 代码框架（递归）：

def dfs(node):
    if not node:
        return
    # 处理当前节点
    dfs(node.left)
    dfs(node.right)

BFS 代码框架（队列）：

from collections import deque
def bfs(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        # 处理当前节点
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

五、高频进阶问题

LRU 缓存机制
- 实现：哈希表 + 双向链表，保证 O(1) 的 get 和 put 操作。
接雨水
- 双指针法：左右指针向中间移动，计算每个位置的积水量。
合并区间
- 排序后合并：按区间起点排序，依次合并重叠区间。
字符串解码
- 栈实现：处理嵌套括号，保存当前字符串和重复次数。

六、时间与空间复杂度分析

常见时间复杂度对比

算法平均时间复杂度

冒泡排序 O(n²)

快速排序 O(n log n)

归并排序 O(n log n)

二分查找 O(log n)

动态规划（一维DP） O(n)
空间复杂度优化
- 滚动数组：将二维 DP 压缩为一维（如背包问题）。
- 尾递归优化：减少递归调用栈深度（需编译器支持）。

算法	平均时间复杂度
冒泡排序	O(n²)
快速排序	O(n log n)
归并排序	O(n log n)
二分查找	O(log n)
动态规划（一维DP）	O(n)

七、代码陷阱与技巧

数组越界：在处理二分查找或双指针时，注意循环终止条件。
指针操作：链表问题中，使用哑节点（Dummy Node）简化头节点处理。
递归终止条件：树或动态规划问题中必须明确基线条件。

八、扩展练习

Top K 问题
- 解法：堆排序（O(n log k)）或快速选择算法（O(n)）。
最小编辑距离
- 状态定义：dp[i][j] 表示将 word1 前 i 个字符转换为 word2 前 j 个字符的最小操作数。
岛屿数量
- DFS/BFS 遍历：将访问过的陆地标记为水，避免重复计数。

分类刷题（LeeCode）

一、数组与字符串

两数之和（LeetCode 1）
- 关键点：哈希表优化查找，时间复杂度 O(n)。
三数之和（LeetCode 15）
- 关键点：排序 + 双指针，去重逻辑。
最长无重复子串（LeetCode 3）
- 关键点：滑动窗口 + 哈希表记录位置。
接雨水（LeetCode 42）
- 关键点：双指针/动态规划，计算每个位置的左右最大高度。
字符串反转/变形（如反转单词顺序、Z字形变换）
- 关键点：原地操作或分块处理。

二、链表

反转链表（LeetCode 206）
- 关键点：迭代（三指针）或递归。
链表中环的检测（LeetCode 141）
- 关键点：快慢指针（Floyd判圈法）。
合并两个有序链表（LeetCode 21）
- 关键点：虚拟头节点简化操作。
删除链表的倒数第N个节点（LeetCode 19）
- 关键点：快慢指针定位前驱节点。
链表排序（LeetCode 148）
- 关键点：归并排序（递归或迭代实现）。

三、栈与队列

有效的括号（LeetCode 20）
- 关键点：栈的匹配与哈希表映射。
最小栈（LeetCode 155）
- 关键点：辅助栈记录最小值。
用队列实现栈/用栈实现队列（LeetCode 232/225）
- 关键点：双队列或双栈倒序。

四、树与二叉树

二叉树遍历（前序/中序/后序/层序）
- 关键点：递归与非递归实现（栈或队列）。
二叉树的最大深度（LeetCode 104）
- 关键点：递归分治或层序遍历。
验证二叉搜索树（BST）（LeetCode 98）
- 关键点：中序遍历递增或递归传递上下界。
二叉树的最近公共祖先（LCA）（LeetCode 236）
- 关键点：递归回溯查找左右子树。
平衡二叉树/完全二叉树判断
- 关键点：递归检查高度或层序填充特性。

五、动态规划（DP）

爬楼梯（LeetCode 70）
- 关键点：状态转移方程 dp[i] = dp[i-1] + dp[i-2]。
最长递增子序列（LIS）（LeetCode 300）
- 关键点：DP O(n²) 或贪心+二分 O(nlogn)。
背包问题（01背包、完全背包）
- 关键点：状态定义、滚动数组优化。
编辑距离（LeetCode 72）
- 关键点：DP矩阵，三种操作（增删改）。
打家劫舍系列（LeetCode 198/213）
- 关键点：环形数组处理，状态分偷与不偷。

六、回溯算法

全排列（LeetCode 46）
- 关键点：路径标记与撤销选择。
子集/组合（LeetCode 78/77）
- 关键点：剪枝优化避免重复。
N皇后问题（LeetCode 51）
- 关键点：对角线冲突检查。
括号生成（LeetCode 22）
- 关键点：左括号数 ≥ 右括号数。

七、图算法

岛屿数量（LeetCode 200）
- 关键点：DFS/BFS遍历标记。
课程表（拓扑排序，LeetCode 207）
- 关键点：入度表 + 队列。
最短路径（Dijkstra、BFS层数）
- 关键点：权重处理与优先队列。
克隆图（LeetCode 133）
- 关键点：哈希表记录已克隆节点。

八、其他高频题

LRU缓存（LeetCode 146）
- 关键点：哈希表 + 双向链表。
合并区间（LeetCode 56）
- 关键点：排序后贪心合并。
寻找重复数（LeetCode 287）
- 关键点：快慢指针（转化为环形链表问题）。
多数元素（LeetCode 169）
- 关键点：Boyer-Moore投票算法。

九、复杂度与设计题

手写快速排序/归并排序
- 关键点：分治思想与边界处理。
设计Twitter/朋友圈（Feed流）
- 关键点：关注列表 + 多路归并。
海量数据问题（Top K、去重）
- 关键点：分桶、堆、位图法。

准备建议

刷题策略：按算法分类刷题，同类题目总结共性。
代码模板化：如二分查找、DFS/BFS的固定写法。
时间与空间复杂度分析：每道题需明确计算依据。
边界条件：空输入、极值（如整数溢出）需特殊处理。