← 返回学习路线

SYSTEM

进阶

八股二、进阶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 变大顶堆)。