20K Java+AI 岗位高频考点 — 算法是大厂面试的必考环节,后端面试常考数组、链表、树、排序、二分、动态规划。覆盖高频LeetCode题型、Java集合源码分析、时间空间复杂度、解题套路。
大O表示法:描述算法运行时间/空间随输入规模的增长趋势
常见复杂度(从小到大):
O(1) 哈希查找
O(logN) 二分查找
O(N) 线性遍历
O(NlogN) 排序(快排/归并)
O(N²) 冒泡/选择排序
O(2^N) 暴力子集
O(N!) 全排列
分析技巧:
- 看循环层数:单层O(N),双层O(N²)
- 看递归深度:树高logN → O(logN)
- 看分支数:每层分2支 → O(2^N)
空间复杂度:
- 原地操作:O(1)
- 辅助数组:O(N)
- 递归栈:O(深度)
- Map/Set:O(N)
// LeetCode #1 两数之和
// 给定数组和target,找两个数之和等于target的索引
// 时间O(N) 空间O(N)
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[0];
}
// 核心:HashMap一遍扫描,空间换时间
// LeetCode #15 三数之和
// 时间O(N²) 空间O(1)(不计返回结果)
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(List.of(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
// 核心:排序+双指针,固定一个数,剩下两个用双指针
// LeetCode #3 无重复字符的最长子串
// 滑动窗口 时间O(N) 空间O(字符集)
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>();
int maxLen = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (window.containsKey(c)) {
left = Math.max(left, window.get(c) + 1);
}
window.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// 核心:滑动窗口+HashMap记录字符最新位置
// LeetCode #206 反转链表
// 迭代 时间O(N) 空间O(1)
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// 递归 时间O(N) 空间O(N)
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
// 1. 检测环(快慢指针)
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
// 2. 合并两个有序链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
tail.next = l1 != null ? l1 : l2;
return dummy.next;
}
// 3. 找中间节点(快慢指针)
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 前序(根→左→右)
public List<Integer> preorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return result;
}
// 中序(左→根→右):BST得到有序序列
public List<Integer> inorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) { stack.push(curr); curr = curr.left; }
curr = stack.pop();
result.add(curr.val);
curr = curr.right;
}
return result;
}
// 层序(BFS)
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}
BST性质:左子树 < 根 < 右子树
中序遍历BST = 有序序列
常见操作时间复杂度:O(H)(H=树高)
- 平衡BST:H = logN
- 退化BST:H = N(退化为链表)
Java中:
TreeMap = 红黑树(自平衡BST)
TreeSet = 红黑树
红黑树性质:
1. 节点是红色或黑色
2. 根是黑色
3. 叶子(nil)是黑色
4. 红色节点的子节点是黑色
5. 从任一节点到叶子的路径含相同数量黑色节点
HashMap JDK8+:链表长度≥8 → 树化为红黑树
红黑树长度≤6 → 退化为链表
| 算法 | 平均 | 最差 | 空间 | 稳定 |
|------|------|------|------|------|
| 冒泡 | O(N²) | O(N²) | O(1) | 是 |
| 选择 | O(N²) | O(N²) | O(1) | 否 |
| 插入 | O(N²) | O(N²) | O(1) | 是 |
| 快排 | O(NlogN) | O(N²) | O(logN) | 否 |
| 归并 | O(NlogN) | O(NlogN) | O(N) | 是 |
| 堆排 | O(NlogN) | O(NlogN) | O(1) | 否 |
| 计数 | O(N+K) | O(N+K) | O(K) | 是 |
| 基数 | O(N×K) | O(N×K) | O(N+K) | 是 |
面试重点:
1. 快排:平均最快,实际应用最广
2. 归并:稳定排序,适合链表和外部排序
3. 堆排:原地排序,适合Top-K问题
Java中:
Arrays.sort() → 基本类型用双轴快排,对象用TimSort(归并+插入)
Collections.sort() → TimSort
public void quickSort(int[] nums, int lo, int hi) {
if (lo >= hi) return;
int pivot = partition(nums, lo, hi);
quickSort(nums, lo, pivot - 1);
quickSort(nums, pivot + 1, hi);
}
private int partition(int[] nums, int lo, int hi) {
int pivot = nums[hi];
int i = lo;
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, hi);
return i;
}
// 优化:随机选择pivot避免最坏情况
// Java Arrays.sort用双轴快排(Dual-Pivot Quicksort)
// 标准二分(找目标值)
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // 防溢出
if (nums[mid] == target) return mid;
else if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// 找左边界(第一个>=target)
public int lowerBound(int[] nums, int target) {
int lo = 0, hi = nums.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
// 应用:旋转数组查找、搜索插入位置、求平方根
DP解题四步:
1. 定义状态:dp[i]代表什么
2. 状态转移:dp[i] = f(dp[i-1], ...)
3. 初始条件:dp[0] = ?
4. 计算顺序:从小到大
经典题目:
1. 爬楼梯:dp[i] = dp[i-1] + dp[i-2]
2. 最长递增子序列:dp[i] = max(dp[j]+1) for j<i, nums[j]<nums[i]
3. 0-1背包:dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi]+vi)
4. 最长公共子序列:dp[i][j] = dp[i-1][j-1]+1 if s1[i]==s2[j]
5. 编辑距离:dp[i][j] = min(插入,删除,替换)
// LeetCode #70 爬楼梯
public int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2;
for (int i = 3; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// LeetCode #300 最长递增子序列
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
// 方法一:小顶堆(适合大数据量/流式数据)
public int[] topK(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int num : nums) {
heap.offer(num);
if (heap.size() > k) heap.poll(); // 弹出最小的
}
return heap.stream().mapToInt(i -> i).toArray();
}
// 方法二:快速选择(平均O(N))
public int findKthLargest(int[] nums, int k) {
k = nums.length - k; // 第K大 = 第(N-K)小
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int pivot = partition(nums, lo, hi);
if (pivot < k) lo = pivot + 1;
else if (pivot > k) hi = pivot - 1;
else break;
}
return nums[k];
}
JDK 1.8 HashMap:
数组 + 链表 + 红黑树
put流程:
1. hash(key) → 扰动函数(h ^ h>>>16)减少碰撞
2. (n-1) & hash → 定位桶(n为2的幂次方)
3. 桶为空 → 直接放入
4. 桶不为空:
a. key相等 → 覆盖
b. 红黑树 → 树插入
c. 链表 → 尾插(JDK7头插会死循环)
链表长度≥8且数组≥64 → 树化
5. 检查扩容:size > threshold → resize()
扩容(resize):
- 新数组 = 旧数组 × 2
- 元素重新hash分布(高位0留在原位,高位1移到新位置)
- 默认初始容量16,负载因子0.75
- threshold = capacity × loadFactor
为什么容量是2的幂?
(n-1) & hash 等价于 hash % n(位运算更快)
| 维度 | ArrayList | LinkedList |
|------|-----------|-----------|
| 底层 | 动态数组 | 双向链表 |
| 随机访问 | O(1) | O(N) |
| 头部插入 | O(N) | O(1) |
| 尾部插入 | 均摊O(1) | O(1) |
| 内存 | 连续 | 分散(指针开销) |
| 缓存 | 友好 | 不友好 |
ArrayList扩容:
- 默认容量10
- 扩容1.5倍(newCapacity = old + old>>1)
- Arrays.copyOf复制
面试结论:99%场景用ArrayList
LeetCode Hot 100 + 面试高频200
题型优先级(后端面试):
1. 数组/字符串:双指针、滑动窗口
2. 链表:反转、合并、环
3. 树:遍历、BST、DFS/BFS
4. 二分查找:标准模板、变体
5. 排序:快排、归并
6. 动态规划:背包、子序列
7. 图:DFS、BFS、拓扑排序
8. 堆:Top-K、中位数
刷题节奏:
- 每个类型先做3-5道基础题
- 总结模板/套路
- 再做变体和hard
- 面试前集中复习Hot100
面试技巧:
- 先说思路(不急着写代码)
- 说清时间空间复杂度
- 考虑边界条件(null/空/1个元素)
- 先暴力解法再优化
数组三技巧:双指针(两端逼近)、滑动窗口(子串子数组)、前缀和(区间求和)
>
链表三套路:快慢指针(环/中点)、dummy节点(头插)、递归(反转)
>
树三遍历:前中后(DFS递归/栈)、层序(BFS队列)
>
DP四步:定义状态→转移方程→初始条件→计算顺序