算法数据结构面试题
整理算法和数据结构的面试题，涵盖常见算法题和数据结构题，包含详细的答案和解析。
📋 题目分类
🎯 一、数据结构
1. 数组和链表的区别？
答案：
区别对比：
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存结构 | 连续内存 | 非连续内存 |
| 随机访问 | O(1) | O(n) |
| 插入删除 | O(n) | O(1) |
| 内存占用 | 固定大小 | 动态大小 |
2. 二叉树的遍历方式？
答案：
二叉树遍历方式：
- 前序遍历：根 -> 左 -> 右
- 中序遍历：左 -> 根 -> 右
- 后序遍历：左 -> 右 -> 根
- 层序遍历：按层遍历
代码实现：
java
// 前序遍历
public void preOrder(TreeNode root) {
if (root == null) return;
System.out.println(root.val);
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历
public void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
System.out.println(root.val);
inOrder(root.right);
}
// 后序遍历
public void postOrder(TreeNode root) {
if (root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.println(root.val);
}🎯 二、算法
3. 常见的排序算法有哪些？时间复杂度是多少？
答案：
常见排序算法：
| 算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
4. 快速排序的原理？
答案：
快速排序原理：
- 选择基准：选择一个基准元素（pivot）
- 分区：将数组分为两部分，小于基准的在左边，大于基准的在右边
- 递归：递归处理左右两部分
代码实现：
java
public void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
private int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}5. 动态规划的核心思想？
答案：
动态规划核心思想：
- 最优子结构：问题的最优解包含子问题的最优解
- 重叠子问题：子问题会被重复计算
- 状态转移方程：找到状态之间的转移关系
经典问题：
- 背包问题
- 最长公共子序列
- 最长递增子序列
- 编辑距离
🎯 三、LeetCode经典题
6. 两数之和（LeetCode 1）
题目：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
解法：
java
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{};
}时间复杂度： O(n)
空间复杂度： O(n)
7. 反转链表（LeetCode 206）
题目：
反转一个单链表。
解法：
java
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}时间复杂度： O(n)
空间复杂度： O(1)
📖 学习资源
视频教程
书籍推荐
- 《算法导论》 - Thomas H. Cormen
- 《数据结构与算法分析》 - Mark Allen Weiss
网站资源
✅ 学习检查清单
- [ ] 已掌握常见数据结构
- [ ] 已掌握常见算法
- [ ] 已练习LeetCode经典题
- [ ] 已总结解题思路
- [ ] 已提升算法能力