数据结构与算法 面试题

数据结构与算法 面试涵盖内容

数据结构与算法 面试题示例

• 在数组中找到两个数，使其和等于目标值（并分析复杂度）。
  好回答应覆盖

  • 哈希表优化到O(n)
  • 暴力O(n^2)不可取
  • 处理重复元素

  查看范例答案

  两数之和的最优解使用哈希表（Python中的字典），将遍历过的元素值及其索引存入哈希表，对每个当前元素检查目标值减当前值是否在表中，若存在则返回两个索引。时间复杂度O(n)，空间复杂度O(n)。暴力双循环O(n^2)效率低，面试中应避免使用。注意：数组可能有重复元素，但题目通常只返回一对解，哈希表可以正确处理。常见陷阱是未考虑同一个元素不能重复使用，通过先检查再存入可以避免。

  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 []

• 检测链表中的环。
  好回答应覆盖

  • 快慢指针法（Floyd判环）
  • 空间复杂度O(1)
  • 哈希表法空间O(n)

  查看范例答案

  检测链表环的经典方法是快慢指针（Floyd's Cycle Detection）：慢指针每次移动一步，快指针每次移动两步。如果存在环，快慢指针最终会在环内相遇；如果快指针到达链表末尾（None），则无环。时间复杂度O(n)，空间复杂度O(1)。另一种方法是哈希表记录访问过的节点，但空间复杂度O(n)不优。常见陷阱：快指针移动两步时需确保fast和fast.next不为None，否则会报错。

  class ListNode:
      def __init__(self, x):
          self.val = x
          self.next = None
  
  def has_cycle(head):
      if not head or not head.next:
          return False
      slow = head
      fast = head.next
      while slow != fast:
          if not fast or not fast.next:
              return False
          slow = slow.next
          fast = fast.next.next
      return True

• 找到不含重复字符的最长子串。
  好回答应覆盖

  • 滑动窗口（双指针）
  • 用哈希集合维护字符
  • O(n)时间，O(字符集)空间

  查看范例答案

  寻找无重复字符的最长子串使用滑动窗口技术：左指针left和右指针right，用哈希集合记录窗口内的字符。右指针逐步右移，若遇到重复字符，则左指针右移并同时从集合中移除字符，直到无重复。每次更新最大长度。时间复杂度O(n)，空间复杂度O(min(n,字符集大小))，字符集通常为ASCII 128或Unicode。常见误区：忘记更新窗口内的字符集合，或未在移动左指针时移除字符。

  def length_of_longest_substring(s: str) -> int:
      char_set = set()
      left = 0
      max_len = 0
      for right in range(len(s)):
          # 如果字符重复，移动左指针直到无重复
          while s[right] in char_set:
              char_set.remove(s[left])
              left += 1
          char_set.add(s[right])
          max_len = max(max_len, right - left + 1)
      return max_len

• 对二叉树进行层序遍历（BFS）。
  好回答应覆盖

  • BFS用队列实现
  • 按层遍历，记录层级
  • O(n)时间，O(n)空间

  查看范例答案

  二叉树的层序遍历使用广度优先搜索（BFS），核心数据结构是队列。初始化时将根节点入队，然后循环：每次取出当前层的所有节点（根据队列长度），将它们的值加入当前层结果列表，同时将子节点（先左后右）入队。最后将当前层列表加入最终结果。时间复杂度O(n)，空间复杂度O(n)（最坏情况下队列存储最后一层节点数）。常见陷阱：忘记处理空树，应返回空列表。

  from collections import deque
  
  def level_order(root):
      if not root:
          return []
      result = []
      queue = deque([root])
      while queue:
          level_size = len(queue)
          current_level = []
          for _ in range(level_size):
              node = queue.popleft()
              current_level.append(node.val)
              if node.left:
                  queue.append(node.left)
              if node.right:
                  queue.append(node.right)
          result.append(current_level)
      return result
  
  # 假设TreeNode类有val, left, right属性

• 网格中的岛屿数量（BFS/DFS）。
  好回答应覆盖

  • DFS或BFS标记已访问
  • 每发现一个'1'即增加岛屿数并遍历整个岛屿
  • 空间O(mn)递归栈或队列

  查看范例答案

  计算网格中岛屿数量使用DFS或BFS遍历。遍历每个格子，若为'1'且未被访问，则将其设为已访问（如改为'0'），并递归或迭代地访问其上下左右相邻的'1'，直到整个岛屿被标记。每次启动一个DFS/BFS意味着新岛屿，计数加一。时间复杂度O(m*n)，空间复杂度最坏O(m*n)（递归栈深度或队列长度）。常见陷阱：忘记处理边界情况（网格为空）或网格为'0'/'1'字符而非整数。

  def num_islands(grid):
      if not grid:
          return 0
      rows, cols = len(grid), len(grid[0])
      count = 0
      def dfs(r, c):
          # 边界条件或已为水
          if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
              return
          # 标记为已访问（沉岛）
          grid[r][c] = '0'
          # 递归访问四个方向
          dfs(r-1, c)
          dfs(r+1, c)
          dfs(r, c-1)
          dfs(r, c+1)
      for i in range(rows):
          for j in range(cols):
              if grid[i][j] == '1':
                  count += 1
                  dfs(i, j)  # 沉没整个岛屿
      return count

• 爬楼梯/零钱兑换（基础动态规划）。
  好回答应覆盖

  • 状态转移方程 dp[i]=min(dp[i-coin]+1)
  • 完全背包问题
  • O(amount * coins)时间，O(amount)空间

  查看范例答案

  零钱兑换（完全背包）求最少硬币数：dp[i]表示凑成金额i所需的最少硬币数，初始dp[0]=0，其余为amount+1（不可能）。遍历每个硬币coin，对于金额从coin到amount，更新dp[i]=min(dp[i], dp[i-coin]+1)。最终若dp[amount]仍为初始值则返回-1，否则返回dp[amount]。时间复杂度O(amount * coins)，空间复杂度O(amount)。常见陷阱：未处理无限硬币的重复使用（完全背包需正序遍历金额）。也可用BFS，但DP更简洁。

  def coin_change(coins, amount):
      # dp[i] 表示凑成金额 i 的最少硬币数
      dp = [amount + 1] * (amount + 1)
      dp[0] = 0
      for coin in coins:
          # 完全背包：正序遍历金额
          for i in range(coin, amount + 1):
              dp[i] = min(dp[i], dp[i - coin] + 1)
      return dp[amount] if dp[amount] != amount + 1 else -1

如何准备

• 学习模式而非具体问题——大多数题目对应少数几个模板。
• 始终说明时间和空间复杂度，如果是暴力解法，则寻找更优方法。
• 编码前先解释你的计划，最后用小例子测试。
• 练习在白板或没有自动补全的纯文本编辑器中编写无 Bug 的代码。

常见问题