SYSTEM
进阶
src/content/notes/system/进阶.md 二、进阶
2.1 动态规划
DP 的核心是把问题拆成子问题、定义状态、找转移方程、确定边界与遍历顺序。
0-1 背包问题
dp[i][j] 表示前 i 个物品、容量 j 时的最大价值,每个物品选或不选。
// 0-1 背包:空间优化为一维,倒序遍历容量防止重复选取
class Solution {
public int knapsack(int[] weight, int[] value, int capacity) {
int n = weight.length;
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
for (int j = capacity; j >= weight[i]; j--) { // 倒序
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[capacity];
}
}
最长递增子序列(力扣 300)
dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。可再配合二分把整体优化到 O(NlogN)。
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int max = 0;
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
max = Math.max(max, dp[i]);
}
return max;
}
}
买卖股票最佳时机(力扣 121)
dp[i][0] 表示第 i 天不持有的最大利润,dp[i][1] 表示持有的最大利润。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][0] = 0; // 第一天不持有
dp[0][1] = -prices[0]; // 第一天买入
for (int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // 卖出或保持
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]); // 买入或保持
}
return dp[n - 1][0];
}
}
面试题:“DP 的解题步骤是什么?”
第一步明确状态定义(dp 数组每个维度代表什么);第二步写状态转移方程,思考当前状态由哪些前置状态推出;第三步确定边界初值;第四步确定遍历顺序(依赖关系决定从前往后还是从后往前、几维嵌套);第五步举例推导验证。
2.2 图
拓扑排序(BFS / 力扣 207 课程表)
对 DAG 用入度 BFS:入度为 0 的节点入队,每次出队并把后继节点入度减一,为零则入队,最终访问数等于节点数则无环。
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
int[] indegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
for (int[] p : prerequisites) {
graph.get(p[1]).add(p[0]);
indegree[p[0]]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) q.offer(i);
int count = 0;
while (!q.isEmpty()) {
int course = q.poll();
count++;
for (int next : graph.get(course)) {
if (--indegree[next] == 0) q.offer(next);
}
}
return count == numCourses;
}
}
Dijkstra 最短路径(优先队列)
单源最短路径,边权非负。用小顶堆每次取当前距离最小的节点松弛邻居。
class Solution {
public int[] dijkstra(int n, List<int[]>[] graph, int src) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// [节点, 距离],按距离升序
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{src, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int u = cur[0], d = cur[1];
if (d > dist[u]) continue; // 已有更优解,跳过
for (int[] edge : graph[u]) {
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{v, dist[v]});
}
}
}
return dist;
}
}
2.3 堆
TopK 问题(小顶堆,力扣 215 第 K 大)
求第 K 大用小顶堆维护 K 个元素:遍历数把大的塞进堆,堆满后比堆顶小的直接丢,更大的弹出堆顶再入堆,最终堆顶就是第 K 大。
class Solution {
// 力扣 215. 数组中的第 K 个最大元素
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 小顶堆
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) minHeap.poll(); // 维持堆大小为 K
}
return minHeap.peek();
}
}
合并 K 个有序链表(力扣 23)
把每个链表头节点放进小顶堆,每次取最小节点接到结果链,再推入该链的下一个节点。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
for (ListNode node : lists) {
if (node != null) heap.offer(node);
}
ListNode dummy = new ListNode(0), cur = dummy;
while (!heap.isEmpty()) {
ListNode node = heap.poll();
cur.next = node;
cur = cur.next;
if (node.next != null) heap.offer(node.next); // 该链下一个入堆
}
return dummy.next;
}
}
面试题:“求 TopK 用什么数据结构?”
用堆。求前 K 大用小顶堆维护 K 个元素,遍历时只在与堆顶比较后决定是否替换,时间 O(NlogK)、空间 O(K),比全排序 O(NlogN) 更省。海量数据求 TopK 可加分治:每台机器各自求本地 TopK,再合并这些 TopK。Java 中直接用 PriorityQueue(默认小顶堆,加反转 Comparator 变大顶堆)。