算法面试题

数据结构

1. 数组和链表的区别

• 数组：
  • 连续内存空间
  • 随机访问 O(1)
  • 插入删除 O(n)
  • 大小固定
• 链表：
  • 非连续内存空间
  • 随机访问 O(n)
  • 插入删除 O(1)
  • 大小动态

2. 栈和队列的特点

• 栈：
  • 后进先出（LIFO）
  • 主要操作：push, pop
  • 应用：函数调用、括号匹配
• 队列：
  • 先进先出（FIFO）
  • 主要操作：enqueue, dequeue
  • 应用：任务调度、消息队列

3. 树的基本概念

• 二叉树：每个节点最多有两个子节点
• 二叉搜索树：左子树值 < 根节点值 < 右子树值
• 平衡二叉树：左右子树高度差不超过 1
• 红黑树：自平衡的二叉搜索树

排序算法

1. 快速排序

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(nlogn)，最坏 O(n²) 空间复杂度：O(logn)

2. 归并排序

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

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:])
    result.extend(right[j:])
    return result

时间复杂度：O(nlogn) 空间复杂度：O(n)

3. 堆排序

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

时间复杂度：O(nlogn) 空间复杂度：O(1)

查找算法

1. 二分查找

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

时间复杂度：O(logn) 空间复杂度：O(1)

2. 广度优先搜索（BFS）

def bfs(graph, start):
    visited = set()
    queue = [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

时间复杂度：O(V + E) 空间复杂度：O(V)

3. 深度优先搜索（DFS）

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

时间复杂度：O(V + E) 空间复杂度：O(V)

动态规划

1. 斐波那契数列

def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

时间复杂度：O(n) 空间复杂度：O(n)

2. 最长公共子序列

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

时间复杂度：O(mn) 空间复杂度：O(mn)

3. 背包问题

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] <= j:
                dp[i][j] = max(dp[i - 1][j], 
                              dp[i - 1][j - weights[i - 1]] + values[i - 1])
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[n][capacity]

时间复杂度：O(nW) 空间复杂度：O(nW)

常见算法题

1. 两数之和

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

2. 反转链表

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

3. 有效的括号

def is_valid(s):
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

学习资源

在线教程

• LeetCode
• 算法导论
• 数据结构与算法分析
• 算法图解

书籍推荐

• 《算法导论》
• 《算法（第4版）》
• 《剑指Offer》
• 《编程之美》

练习平台

• LeetCode
• HackerRank
• Codeforces
• AtCoder