Map of Highest Peak
给一个数组, 里边是哪里有水, 哪里是陆地, 求最大的height的地图, 满足每个格子之间最多差1.
这个题用单源bfs做, 会超时
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
class Solution { int[][] dirs = { {0,1}, {0,-1}, {-1,0}, {1,0} }; int n; int m; public int[][] highestPeak(int[][] isWater) { n = isWater.length; m = isWater[0].length; List<int[]> points = new ArrayList<>(); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(isWater[i][j] == 1){ isWater[i][j] = 0; points.add(new int[]{i,j}); } else{ isWater[i][j] = -1; } } } for(int[] p : points){ bfs(isWater, p[0], p[1]); } return isWater; } public void bfs(int[][] isWater, int x, int y){ Queue<int[]> q = new LinkedList<>(); q.add(new int[]{x,y}); while(!q.isEmpty()){ int[] cur = q.poll(); for(int[] d : dirs){ int newX = d[0] + cur[0]; int newY = d[1] + cur[1]; if(newX < 0 || newY < 0 || newX >= n || newY >= m || isWater[newX][newY] == 0) continue; if(isWater[newX][newY] == -1){ isWater[newX][newY] = isWater[cur[0]][cur[1]] + 1; q.add(new int[]{newX, newY}); }else{ if(isWater[cur[0]][cur[1]] + 1 == isWater[newX][newY] || isWater[cur[0]][cur[1]] == isWater[newX][newY]) continue; else{ isWater[newX][newY] = Math.min(isWater[cur[0]][cur[1]] + 1, isWater[newX][newY]); q.add(new int[]{newX, newY}); } } } } } } |
感觉用了多源也卡的要死, 虽然过了,但是速度不是很快
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
class Solution { int[][] dirs = { {0,1}, {0,-1}, {-1,0}, {1,0} }; int n; int m; public int[][] highestPeak(int[][] isWater) { n = isWater.length; m = isWater[0].length; Set<String> set = new HashSet<>(); Queue<int[]> q = new LinkedList<>(); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(isWater[i][j] == 1){ isWater[i][j] = 0; q.add(new int[]{i, j}); set.add(i+"|"+j); } } } while(!q.isEmpty()){ int[] cur = q.poll(); for(int[] d : dirs){ int newX = d[0] + cur[0]; int newY = d[1] + cur[1]; if(newX < 0 || newY < 0 || newX >= n || newY >= m || set.contains(newX+"|"+newY)) continue; isWater[newX][newY] = isWater[cur[0]][cur[1]] + 1; q.add(new int[]{newX, newY}); set.add(newX+"|"+newY); } } return isWater; } } |