文章目录
- 1. 01 矩阵(542)
- 2. 飞地的数量(1020)
- 3. 地图分析(1162)
- 4. 地图中的最高点(1765)
1. 01 矩阵(542)
题目描述:
算法原理:
这题会想到能不能遍历每一个格子中的元素,然后挨个的去进行单源最短路径的操作,但是题目中指出要得到的矩阵是每个格子中的元素到最近的0的距离,那么我们完全可以从矩阵中的0出发,设置距离的矩阵,以一种类似于FloodFill算法的方法来更新记录从0走了多少步的距离矩阵,具体看代码。
代码如下:
class Solution {public int[][] updateMatrix(int[][] mat) {int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };int m = mat.length;int n = mat[0].length;int[][] dis = new int[m][n];Queue<int[]> q = new LinkedList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (mat[i][j] == 0) {dis[i][j] = 0;q.add(new int[] { i, j });} else {dis[i][j] = -1;}}}while (!q.isEmpty()) {int[] temp = q.poll();int a = temp[0], b = temp[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 && dis[x][y] == -1) {dis[x][y] = dis[a][b] + 1;q.add(new int[] { x, y });}}}return dis;}
}
题目链接
2. 飞地的数量(1020)
题目描述:
算法原理:
和上题思想类似,上题是从终点0出发,这题是从终点的边界1元素出发去不断的发散,直至队列为空,此时还没有被遍历到的元素1就是走不出去的。
代码如下:
class Solution {public int numEnclaves(int[][] grid) {int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };int m = grid.length, n = grid[0].length;boolean[][] vis = new boolean[m][n];Queue<int[]> queue = new LinkedList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {if (grid[i][j] == 1) {vis[i][j] = true;queue.add(new int[] { i, j });}}}}while (!queue.isEmpty()) {int[] temp = queue.poll();int a = temp[0], b = temp[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 && !vis[x][y] && grid[x][y] == 1) {vis[x][y] = true;queue.add(new int[] { x, y });}}}int ret = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1 && !vis[i][j]) {ret++;}}}return ret;}
}
题目链接
3. 地图分析(1162)
题目描述:
算法原理:
这题就是第一题的换一种问法,做法和第一题一致。
代码如下:
class Solution {public int maxDistance(int[][] grid) {int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };int m = grid.length;int n = grid[0].length;int[][] dis = new int[m][n];Queue<int[]> q = new LinkedList<>();boolean flg1 = false;boolean flg2 = false;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {dis[i][j] = -1;}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {flg1 = true;q.add(new int[] { i, j });dis[i][j] = 0;} else {flg2 = true;}}}if (!(flg1 && flg2)) {return -1;}while (!q.isEmpty()) {int[] temp = q.poll();int a = temp[0], b = temp[1];for (int i = 0; i < 4; i++) {int x = a + dx[i];int y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && dis[x][y] == -1) {dis[x][y] = dis[a][b] + 1;q.add(new int[] { x, y });}}}int ret = Integer.MIN_VALUE;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {ret = Math.max(ret, dis[i][j]);}}}return ret;}
}
题目链接
4. 地图中的最高点(1765)
题目描述:
算法原理:
做法同前三题类似,但是就是需要意识到前面的做法就能够得到最高,因为我们从水域开始周围的高度完全可以赋为0但是我们用了一个小贪心就是每次高度差都是1体现在我们代码中就是类似于前面的距离+1。
代码如下:
class Solution {public int[][] highestPeak(int[][] isWater) {int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };int m = isWater.length;int n = isWater[0].length;int[][] ret = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {ret[i][j] = -1;}}Queue<int[]> q = new LinkedList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (isWater[i][j] == 1) {q.add(new int[] { i, j });ret[i][j] = 0;}}}while (!q.isEmpty()) {int[] temp = q.poll();int a = temp[0], b = temp[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 && ret[x][y] == -1) {ret[x][y] = ret[a][b] + 1;q.add(new int[] { x, y });}}}return ret;}
}
题目链接