Appearance
图与贪心
图论和贪心算法是面试中较难的两类问题。图的核心是遍历（DFS/BFS）和拓扑排序；贪心的核心是每步选择局部最优从而得到全局最优。本模块涵盖课程表、腐烂的橘子、买卖股票、跳跃游戏等经典题目。掌握图的表示方法和贪心的适用场景是解题关键。
Q1: 课程表 「🟡 中级」
题目描述：你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi]，表示如果要学习课程 ai 则必须先学习课程 bi。请你判断是否可能完成所有课程的学习？
考察点：拓扑排序、有向无环图(DAG)、BFS/DFS、入度表。
解题思路：
- 方法1：BFS拓扑排序（Kahn算法），入度为0的节点入队，逐个出队并减少邻居入度（时间O(V+E)，空间O(V+E)）- 最优解
- 方法2：DFS，检测是否有环（时间O(V+E)，空间O(V+E)）
代码实现：
java
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 构建邻接表和入度表
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
for (int[] pre : prerequisites) {
adj.get(pre[1]).add(pre[0]); // pre[1] -> pre[0]
inDegree[pre[0]]++;
}
// BFS
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) queue.offer(i);
}
int count = 0;
while (!queue.isEmpty()) {
int curr = queue.poll();
count++;
for (int next : adj.get(curr)) {
inDegree[next]--;
if (inDegree[next] == 0) {
queue.offer(next);
}
}
}
return count == numCourses;
}复杂度分析：时间复杂度 O(V+E)，V为课程数，E为先修关系数；空间复杂度 O(V+E)，邻接表存储。
变体扩展：
- 变体1：课程表II（返回学习顺序）
- 变体2：课程表III（按时间安排）
- 变体3：课程表IV（查询是否为先修）
- 变体4：找到最终的安全状态
Q2: 岛屿数量（图的BFS/DFS） 「🟡 中级」
题目描述：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
考察点：图的遍历、BFS广度优先搜索、DFS深度优先搜索。
解题思路：
- 方法1：DFS，遍历每个格子，遇到陆地则DFS标记所有相连陆地（时间O(mn)，空间O(mn)最坏）
- 方法2：BFS，使用队列进行广度优先搜索（时间O(m*n)，空间O(min(m,n))）- 最优解
- 方法3：并查集
代码实现：
java
// BFS实现
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int count = 0;
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
bfs(grid, i, j, m, n);
count++;
}
}
}
return count;
}
private void bfs(char[][] grid, int i, int j, int m, int n) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
grid[i][j] = '0';
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
for (int[] dir : dirs) {
int x = curr[0] + dir[0];
int y = curr[1] + dir[1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
grid[x][y] = '0';
queue.offer(new int[]{x, y});
}
}
}
}复杂度分析：时间复杂度 O(m*n)，每个格子最多访问一次；空间复杂度 O(min(m,n))，队列最大不超过较短边。
变体扩展：
- 变体1：岛屿的最大面积
- 变体2：腐烂的橘子
- 变体3：被围绕的区域
- 变体4：太平洋大西洋水流问题
Q3: 腐烂的橘子 「🟡 中级」
题目描述：在给定的 m x n 网格 grid 中，每个单元格可以有三个值之一：0 代表空单元格，1 代表新鲜橘子，2 代表腐烂的橘子。每分钟，任何与腐烂的橘子（在4个正方向上）相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
考察点：多源BFS、层序遍历、最短时间计算。
解题思路：
- 方法：多源BFS，初始所有腐烂橘子同时开始扩散，按层序遍历统计分钟数（时间O(mn)，空间O(mn)）- 最优解
代码实现：
java
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int fresh = 0;
// 初始化：统计新鲜橘子数，腐烂橘子入队
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
queue.offer(new int[]{i, j});
} else if (grid[i][j] == 1) {
fresh++;
}
}
}
if (fresh == 0) return 0;
int minutes = 0;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
for (int[] dir : dirs) {
int x = curr[0] + dir[0];
int y = curr[1] + dir[1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
grid[x][y] = 2;
fresh--;
queue.offer(new int[]{x, y});
}
}
}
minutes++;
}
return fresh == 0 ? minutes - 1 : -1;
}复杂度分析：时间复杂度 O(mn)，每个格子最多入队一次；空间复杂度 O(mn)，最坏全是腐烂橘子。
变体扩展：
- 变体1：岛屿数量
- 变体2：01矩阵（最近0的距离）
- 变体3：墙与门
- 变体4：二叉树的层序遍历
Q4: 买卖股票的最佳时机II 「🟡 中级」
题目描述：给你一个整数数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可能会决定购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以购买它，然后在同一天出售。返回你能获得的最大利润。
考察点：贪心算法、峰谷法、动态规划。
解题思路：
- 方法1：动态规划，每天有持有/不持有两种状态（时间O(n)，空间O(n)可优化到O(1)）
- 方法2：贪心，只要后一天比前一天贵就赚差价（时间O(n)，空间O(1)）- 最优解
代码实现：
java
public int maxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}复杂度分析：时间复杂度 O(n)，遍历一次价格数组；空间复杂度 O(1)。
变体扩展：
- 变体1：买卖股票的最佳时机（只能买卖一次）
- 变体2：买卖股票的最佳时机III（最多两次交易）
- 变体3：买卖股票的最佳时机IV（最多k次交易）
- 变体4：最佳买卖股票时机含冷冻期
- 变体5：买卖股票的最佳时机含手续费
Q5: 跳跃游戏 「🟡 中级」
题目描述：给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
考察点：贪心算法、最远可达位置、动态规划。
解题思路：
- 方法1：动态规划（时间O(n²)，空间O(n)）
- 方法2：贪心，维护最远可达位置（时间O(n)，空间O(1)）- 最优解
代码实现：
java
public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) return false; // 到不了当前位置
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) return true;
}
return true;
}复杂度分析：时间复杂度 O(n)，遍历一次数组；空间复杂度 O(1)。
变体扩展：
- 变体1：跳跃游戏II（最少跳跃次数）
- 变体2：跳跃游戏III（是否可达0）
- 变体3：跳跃游戏IV（同值可跳）
- 变体4：跳跃游戏V（有高度限制）
Q6: 分发饼干 「🟢 初级」
题目描述：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
考察点：贪心算法、排序、双指针。
解题思路：
- 方法：排序 + 贪心，用最小的饼干满足胃口最小的孩子（时间O(nlogn + mlogm)，空间O(1)或O(logn)排序栈空间）- 最优解
代码实现：
java
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i = 0, j = 0;
int count = 0;
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) {
count++;
i++;
j++;
} else {
j++; // 饼干太小，换大饼干
}
}
return count;
}复杂度分析：时间复杂度 O(nlogn + mlogm)，排序为主；空间复杂度 O(1)（忽略排序的栈空间）。
变体扩展：
- 变体1：柠檬水找零
- 变体2：用最少数量的箭引爆气球
- 变体3：无重叠区间
- 变体4：划分字母区间