【优选算法】（第四十五篇）

目录

地图分析（medium）

题目解析

讲解算法原理

编写代码

课程表（medium）

题目解析

讲解算法原理

编写代码

---

地图分析（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

你现在⼿⾥有⼀份⼤⼩为 n x n 的⽹格 grid ，上⾯的每个单元格都⽤ 0 和 1 标记好了。其中 0 代表海洋， 1 代表陆地。
请你找出⼀个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最⼤的，并返回该距离。如果⽹格上只有陆地或者海洋，请返回 -1 。
我们这⾥说的距离是「曼哈顿距离」（ManhattanDistance）： (x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

⽰例1：

输⼊：grid=[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋单元格(1,1)和所有陆地单元格之间的距离都达到最⼤，最⼤距离为2。
⽰例2：

输⼊：grid=[[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释：
海洋单元格(2,2)和所有陆地单元格之间的距离都达到最⼤，最⼤距离为4。
提⽰：
◦ n == grid.length
◦ n == grid[i].length
◦ 1 <= n <= 100
◦ grid[i][j] 不是 0 就是 1

讲解算法原理

解法：
算法思路：
01矩阵的变型题，直接⽤多源bfs解决即可。

编写代码

c++算法代码：

class Solution
{int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};
public:int maxDistance(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dist(m, vector<int>(n, -1));queue<pair<int, int>> q;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(grid[i][j]){dist[i][j] = 0;q.push({i, j});}int ret = -1;while(q.size()){auto [a, b] = q.front(); q.pop();for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1){dist[x][y] = dist[a][b] + 1;q.push({x, y});ret = max(ret, dist[x][y]);}}}return ret;}
};

java算法代码：

class Solution
{int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};public int maxDistance(int[][] grid) {int m = grid.length, n = grid[0].length;int[][] dist = new int[m][n];for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)dist[i][j] = -1;Queue<int[]> q = new LinkedList<>();for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(grid[i][j] == 1){dist[i][j] = 0;q.add(new int[]{i, j});}int ret = -1;while(!q.isEmpty()){int[] t = q.poll();int a = t[0], b = t[1];for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1){dist[x][y] = dist[a][b] + 1;q.add(new int[]{x, y});ret = Math.max(ret, dist[x][y]);}}}return ret;}
}

课程表（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

你这个学期必须选修 numCourses ⻔课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要⼀些先修课程。先修课程按数组 prerequisites 给出，其中
prerequisites[i] = [a(i), b(i)] ，表⽰如果要学习课程 a(i) 则必须先学习课程
b(i) ()。
◦ 例如，先修课程对 [0, 1] 表⽰：想要学习课程 0 ，你需要先完成课程 1 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
⽰例1：
输⼊：numCourses=2,prerequisites=[[1,0]]
输出：true
解释：总共有2⻔课程。学习课程1之前，你需要完成课程0。这是可能的。
⽰例2：
输⼊：numCourses=2,prerequisites=[[1,0],[0,1]]
输出：false
解释：总共有2⻔课程。学习课程1之前，你需要先完成课程0；并且学习课程0之前，你还应先完成课程1。这是不可能的。

提⽰：
◦ 1 <= numCourses <= 2000
◦ 0 <= prerequisites.length <= 5000
◦ prerequisites[i].length == 2
◦ 0 <= a(i), b(i) < numCourses
◦ prerequisites[i] 中的所有课程对互不相同

讲解算法原理

解法：
算法思路：
原问题可以转换成⼀个拓扑排序问题。
⽤BFS解决拓扑排序即可。
拓扑排序流程：
a. 将所有⼊度为0的点加⼊到队列中；
b. 当队列不空的时候，⼀直循环：
i. 取出队头元素；
ii. 将于队头元素相连的顶点的⼊度-1；
iii. 然后判断是否减成0,。如果减成0，就加⼊到队列中。

编写代码

c++算法代码：

class Solution
{
public:bool canFinish(int n, vector<vector<int>>& p) {unordered_map<int, vector<int>> edges; // 邻接表 vector<int> in(n); // 存储每⼀个结点的⼊度// 1. 建图for(auto& e : p){int a = e[0], b = e[1];edges[b].push_back(a);in[a]++;}// 2. 拓扑排序 - bfsqueue<int> q;// 把所有⼊度为 0 的点加⼊到队列中for(int i = 0; i < n; i++){if(in[i] == 0) q.push(i);}// 层序遍历while(!q.empty()){int t = q.front();q.pop();// 修改相连的边for(int e : edges[t]){in[e]--;if(in[e] == 0) q.push(e);}}// 3. 判断是否有环for(int i : in) if(i)return false;return true;}
};

java算法代码：

class Solution
{public boolean canFinish(int n, int[][] p) {// 1. 准备⼯作int[] in = new int[n]; // 统计每⼀个顶点的⼊度Map<Integer, List<Integer>> edges = new HashMap<>(); // 邻接表存图 // 2. 建图for(int i = 0; i < p.length; i++){int a = p[i][0], b = p[i][1]; // b -> aif(!edges.containsKey(b)){edges.put(b, new ArrayList<>());}edges.get(b).add(a);in[a]++;}// 3. 拓扑排序Queue<Integer> q = new LinkedList<>();// (1) 先把⼊度为 0 的点，加⼊到队列中for(int i = 0; i < n; i++){if(in[i] == 0) q.add(i);}// (2) bfswhile(!q.isEmpty()){int t = q.poll();for(int a : edges.getOrDefault(t, new ArrayList<>())){in[a]--;if(in[a] == 0) q.add(a);}}// 4. 判断是否有环for(int x : in)if(x != 0) return false;return true;}
}