数据结构与算法之——常见面试题及解答3

发表于 分类于 ， 阅读时长 ≈ 1 分钟

一 概述

  • ArrayList 扩容机制？
  • 栈实现队列 & 队列实现栈
  • Trie 树(字典树)
  • 并查集(Union-Find)
  • 图结构相关知识
  • 滑动窗口思想(双指针)
  • 堆(优先队列)
  • 动态规划经典问题
  • 回溯经典题目(组合型)
  • 常见面试题解法对比

二 面试题解答(仅供参考)

2.1 ArrayList 扩容机制？

1
2
3
4
5
6
7
8
9
面试常问： 插入大量数据时性能为何下降？

-默认初始容量是 10。
-每次扩容为原来的 1.5 倍（JDK8 起：newCapacity = oldCapacity + (oldCapacity >> 1)）。

2、容过程会：
-创建新数组；
-将老数据复制过去；
-所以频繁扩容性能很差（建议设置初始容量）。

2.2 栈实现队列 & 队列实现栈

1
2
3
4
5
6
7
8
面试常问：手写实现

1、两个栈实现一个队列（两个 Stack）
-入队：正常 push
-出队：popStack 为空则把 pushStack 中的全部元素倒过去

2、两个队列实现一个栈（两个 Queue）
-push 时将元素加到空队列，并将另一个队列中的全部元素倒进来

2.3 Trie 树(字典树)

1
2
3
4
5
6
7
8
1、典型题目：
-单词前缀统计
-自动补全
-实现 insert(word) / search(word) / startsWith(prefix)

2、结构：
-多叉树（26叉/字母节点）
-每个节点记录是否为单词结尾

2.4 并查集(Union-Find)

1
2
3
4
5
6
7
1、应用场景：
-判断两个元素是否在同一集合（如：朋友圈问题）
-连通块统计（如岛屿数量）

2、优化策略：
-路径压缩（find 时将父节点直接指向根）
-按秩合并（按子树深度合并）

2.5 图结构相关知识

知识点 描述
邻接矩阵 空间 O(n²)，稠密图
邻接表 空间 O(n+e)，稀疏图
BFS 用队列，适合求最短路径
DFS 用栈或递归
拓扑排序 DAG 有向无环图中常用，Kahn算法
Dijkstra 单源最短路径算法，基于优先队列
Floyd / Bellman-Ford 全源最短路径算法

2.6 滑动窗口思想(双指针)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1、常见题型：
-最长不重复子串
-最小覆盖子串（hard）
-滑动窗口最大值（单调队列）

2、常用模板：

int left = 0, right = 0;
while (right < s.length()) {
    window.add(s[right]);
    right++;
    while (window 满足某个条件) {
        window.remove(s[left]);
        left++;
    }
}

2.7 堆(优先队列)

1
2
3
4
5
6
7
8
1、常见考点：
-Top K 高频元素
-合并 K 个有序链表
-堆排序实现

2、Java 使用：
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

2.8 动态规划经典问题

题型 描述
爬楼梯 一维DP：dp[i] = dp[i-1] + dp[i-2]
最大子数组和 Kadane算法
股票买卖 dp[i][j] 表示第 i 天状态 j（持有/未持有）
背包问题 二维或一维压缩 DP
最长上升子序列 LIS O(n²) / O(nlogn)（用二分）

2.9 回溯经典题目(组合型)

题型 描述
全排列 无重复或有重复排列
子集 / 组合 按条件组合元素
N 皇后 符合条件的棋盘状态
单词搜索 网格DFS + visited标记
数独求解 行列宫合法性检查 + 回溯

2.10 常见面试题解法对比

题目 解法1 解法2
两数之和 暴力 O(n²) 哈希表 O(n)
滑动窗口最大值 暴力 单调队列 O(n)
LRU 缓存 HashMap + List LinkedHashMap
最长公共子序列 递归 动态规划
Top K 排序 小根堆 O(nlogk)