← 返回首页 ❓ 面试题库
📑 本篇章节导航 (共14章,点击直达)
一、数组与链表二、栈与队列三、哈希表四、二叉树五、二叉搜索树(BST)六、排序算法七、二分查找八、动态规划九、贪心算法十、回溯算法十一、图论基础十二、字符串十三、高频设计题十四、复杂度分析

title: 数据结构与算法

tags: [算法, 数据结构, LeetCode, 2026高频]

created: 2026-05-31


数据结构与算法 — 20K后端必考专题

20K Java后端面试的算法要求:LeetCode中等难度、能手写、能分析复杂度、能关联实际场景。
不是ACM竞赛级别,但也不能只会CRUD。

一、数组与链表

Q001. 如何实现一个LRU缓存?要求get和put都是O(1)

难度:★★★★☆

答案要点:

Q002. 反转链表(迭代和递归两种方式)

难度:★★☆☆☆

答案要点:

Q003. 合并两个有序链表

难度:★★☆☆☆

答案要点:

Q004. 如何检测链表中是否有环?找出环的入口节点

难度:★★★☆☆

答案要点:

Q005. 删除链表的倒数第N个节点

难度:★★★☆☆

答案要点:

Q006. 两数之和(返回数组中两个数的下标,使它们的和等于目标值)

难度:★★☆☆☆

答案要点:


二、栈与队列

Q007. 有效的括号(判断括号字符串是否合法)

难度:★★☆☆☆

答案要点:

Q008. 实现一个最小栈(push/pop/getMin都是O(1))

难度:★★★☆☆

答案要点:

Q009. 用栈实现队列(两个栈模拟FIFO)

难度:★★★☆☆

答案要点:

Q010. 滑动窗口最大值

难度:★★★★☆

答案要点:


三、哈希表

Q011. 三数之和(找出数组中和为0的三元组,要求不重复)

难度:★★★★☆

答案要点:

Q012. 字母异位词分组(将字符串数组按字母异位词分组)

难度:★★★☆☆

答案要点:

Q013. Top-K频繁元素(返回数组中出现频率前K高的元素)

难度:★★★☆☆

答案要点:

Q014. 最长连续序列(在未排序数组中找最长连续元素序列的长度,要求O(n))

难度:★★★★☆

答案要点:


四、二叉树

Q015. 二叉树的层序遍历(逐层从左到右输出)

难度:★★☆☆☆

答案要点:

Q016. 二叉树的最大深度

难度:★☆☆☆☆

答案要点:

Q017. 翻转二叉树(镜像翻转)

难度:★★☆☆☆

答案要点:

Q018. 二叉树的最近公共祖先

难度:★★★★☆

答案要点:

Q019. 二叉树的序列化与反序列化

难度:★★★★☆

答案要点:


五、二叉搜索树(BST)

Q020. 验证一棵二叉树是否是合法的BST

难度:★★★☆☆

答案要点:

Q021. BST中第K小的元素

难度:★★★☆☆

答案要点:

Q022. BST中范围搜索(给定范围[low, high],返回所有满足条件的节点值)

难度:★★★☆☆

答案要点:


六、排序算法

Q023. 快速排序的原理和实现?最坏情况如何避免?

难度:★★★★☆

答案要点:

Q024. 归并排序的原理?为什么它是稳定排序?

难度:★★★★☆

答案要点:

Q025. 堆排序的原理?如何用堆实现Top-K?

难度:★★★★☆

答案要点:

Q026. Java中Arrays.sort()和Collections.sort()分别用什么排序算法?

难度:★★★☆☆

答案要点:


七、二分查找

Q027. 标准二分查找及其变体(查找第一个/最后一个等于目标的位置)

难度:★★★☆☆

答案要点:

Q028. 搜索旋转排序数组(无重复元素)

难度:★★★★☆

答案要点:

Q029. 在排序数组中查找元素的第一个和最后一个位置

难度:★★★☆☆

答案要点:


八、动态规划

Q030. 爬楼梯(每次可以爬1或2阶,到达第n阶有多少种方法)

难度:★★☆☆☆

答案要点:

Q031. 0-1背包问题(N个物品,容量为W的背包,求最大价值)

难度:★★★★☆

答案要点:

Q032. 最长递增子序列(LIS)

难度:★★★★☆

答案要点:

Q033. 买卖股票的最佳时机(含多种变体)

难度:★★★★☆

答案要点:


九、贪心算法

Q034. 跳跃游戏(判断能否到达最后一个位置 / 最少跳跃次数)

难度:★★★☆☆

答案要点:

Q035. 无重叠区间(最少删除多少个区间使剩余区间不重叠) / 会议室问题

难度:★★★★☆

答案要点:

Q036. 分发糖果(每个孩子至少一颗,评分高的比相邻孩子多)

难度:★★★★☆

答案要点:


十、回溯算法

Q037. 全排列(给定不重复的数组,返回所有排列)

难度:★★★☆☆

答案要点:

Q038. N皇后问题

难度:★★★★★

答案要点:

Q039. 组合总和(候选数组中找出所有和为target的组合,可重复选取)

难度:★★★☆☆

答案要点:


十一、图论基础

Q040. 图的BFS和DFS遍历

难度:★★★☆☆

答案要点:

Q041. 拓扑排序(课程表问题:能否完成所有课程)

难度:★★★★☆

答案要点:

Q042. Dijkstra最短路径算法

难度:★★★★☆

答案要点:


十二、字符串

Q043. KMP算法(字符串匹配,在主串中查找模式串)

难度:★★★★★

答案要点:

Q044. 最长公共前缀

难度:★★☆☆☆

答案要点:

Q045. 字符串反转(反转字符串、反转单词顺序)

难度:★★☆☆☆

答案要点:


十三、高频设计题

Q046. 实现LFU缓存(最不经常使用)

难度:★★★★★

答案要点:

Q047. 实现数据流的中位数查找(MedianFinder)

难度:★★★★☆

答案要点:

Q048. 实现Trie前缀树(insert/search/startsWith)

难度:★★★★☆

答案要点:


十四、复杂度分析

Q049. 常见排序算法的时间/空间复杂度和稳定性对比

难度:★★★☆☆

答案要点:

算法最好平均最坏空间稳定性
冒泡O(n)O(n²)O(n²)O(1)稳定
快排O(nlogn)O(nlogn)O(n²)O(logn)不稳定
归并O(nlogn)O(nlogn)O(nlogn)O(n)稳定
堆排O(nlogn)O(nlogn)O(nlogn)O(1)不稳定
TimSortO(n)O(nlogn)O(nlogn)O(n)稳定

Q050. 什么是均摊分析?以ArrayList和HashMap为例说明

难度:★★★★☆

答案要点: