国外优秀app设计网站有哪些,网站开发支付宝二维码支付,五棵松网站建设,效果最好h5制作软件目录 地图分析#xff08;medium#xff09;
题目解析
讲解算法原理
编写代码
课程表#xff08;medium#xff09;
题目解析
讲解算法原理
编写代码 地图分析#xff08;medium#xff09;
题目解析
1.题目链接#xff1a;. - 力扣#xff08;LeetCode#…目录 地图分析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(vectorvectorint grid) {int m grid.size(), n grid[0].size();vectorvectorint dist(m, vectorint(n, -1));queuepairint, 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;Queueint[] 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 输⼊numCourses2,prerequisites[[1,0]] 输出true 解释总共有2⻔课程。学习课程1之前你需要完成课程0。这是可能的。 ⽰例2 输⼊numCourses2,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, vectorvectorint p) {unordered_mapint, vectorint edges; // 邻接表 vectorint in(n); // 存储每⼀个结点的⼊度// 1. 建图for(auto e : p){int a e[0], b e[1];edges[b].push_back(a);in[a];}// 2. 拓扑排序 - bfsqueueint 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]; // 统计每⼀个顶点的⼊度MapInteger, ListInteger 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. 拓扑排序QueueInteger 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;}
}
