版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434750
详细代码可以fork下Github上leetcode项目,不定期更新。
题目摘自leetcode:
思路:
没想到它居然是一道BFS题,从边界开始求,用一个优先队列来记录边界处的最小高度,从最小高度开始求水的体积。直观上来看,因为最低的边界cell,一定藏不住水,而其他地方都比它高,所以从它开始遍历里面的cell,水一定不会流出边界外。
而如果遇到更高的cell时,那么自然也不会藏水,就继续从队列中找最低的cell开始重复上述工作。
代码如下:
private class Cell{
int row;
int col;
int height;
public Cell(int row, int col, int height){
this.row = row;
this.col = col;
this.height = height;
}
}
public int trapRainWater(int[][] heightMap) {
int row = heightMap.length;
if (row <= 2) return 0;
int col = heightMap[0].length;
if (col <= 2) return 0;
int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
PriorityQueue<Cell> queue = new PriorityQueue<>(1,new Comparator<Cell>(){
@Override
public int compare(Cell o1, Cell o2) {
return o1.height - o2.height;
}
});
boolean[][] visited = new boolean[row][col];
for (int i = 0; i < row; i++){
visited[i][0] = true;
visited[i][col-1] = true;
queue.offer(new Cell(i, 0, heightMap[i][0]));
queue.offer(new Cell(i, col-1, heightMap[i][col-1]));
}
for (int i = 0; i < col; i++){
visited[0][i] = true;
visited[row-1][i] = true;
queue.offer(new Cell(0, i, heightMap[0][i]));
queue.offer(new Cell(row-1, i, heightMap[row-1][i]));
}
int area = 0;
while (!queue.isEmpty()){
Cell cell = queue.poll();
for (int[] d : dir){
int nrow = cell.row + d[0];
int ncol = cell.col + d[1];
if (nrow >=0 && nrow < row && ncol >= 0 && ncol < col && !visited[nrow][ncol]){
visited[nrow][ncol] = true;
area += Math.max(0, cell.height-heightMap[nrow][ncol]);
queue.offer(new Cell(nrow, ncol, Math.max(heightMap[nrow][ncol], cell.height)));
}
}
}
return area;
}
思路:
这道题,看上去很复杂实则思路很简单。把该问题归简为求最长路径,如果有了这最长路径,那么所求的结点一定是这条最长路径的中间结点。(一个或者两个)
那么问题来了,如何求最长路径呢,用BFS,思想和拓扑排序类似,首先找到叶子结点,叶子结点一定是最外围的那些点。然后把周围的叶子结点进行删除,而删除时,保持速度一致,所以它是典型的BFS,直到最后只剩下两个结点。
代码如下:
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return Collections.singletonList(0);
List<Set<Integer>> adj = new ArrayList<>(n);
for (int i = 0; i < n; ++i) adj.add(new HashSet<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; ++i)
if (adj.get(i).size() == 1) leaves.add(i);
while (n > 2) {
n -= leaves.size();
List<Integer> newLeaves = new ArrayList<>();
for (int i : leaves) {
int j = adj.get(i).iterator().next();
adj.get(j).remove(i);
if (adj.get(j).size() == 1) newLeaves.add(j);
}
leaves = newLeaves;
}
return leaves;
}
此处邻接链表的表示比较特殊,用了HashSet,这在删除时带来了极大的方便,直接根据OBJ删,如果使用List,需要封装一个Node方法,否则List的remove方法无法区分OBJ还是INDEX.
思路:
反着来就好了,不能围住的原因只有一个,”O”在边界上。其他情况均能被围起来,所以我们从刚开始的边界找寻”O”,然后使用BFS,把所有与边界相连的”O”全部找到,并设立一个标志位,最后走一遍更新即可。
代码如下:
public void solve(char[][] board) {
int row = board.length;
if (row == 0) return;
int col = board[0].length;
if (col == 0) return;
Queue<int[]> queue = new LinkedList<>();
boolean[][] canNotTurn = new boolean[row][col];
for (int i = 0; i < row; i++) {
if (board[i][0] == 'O') {
queue.offer(new int[] { i, 0 });
canNotTurn[i][0] = true;
}
if (board[i][col - 1] == 'O') {
queue.offer(new int[] { i, col - 1 });
canNotTurn[i][col-1] = true;
}
}
for (int j = 1; j < col - 1; j++) {
if (board[0][j] == 'O') {
queue.offer(new int[] { 0, j });
canNotTurn[0][j] = true;
}
if (board[row - 1][j] == 'O') {
queue.offer(new int[] { row - 1, j });
canNotTurn[row-1][j] = true;
}
}
int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
while(!queue.isEmpty()){
int[] curr = queue.poll();
for (int[] d : dir){
int nrow = curr[0] + d[0];
int ncol = curr[1] + d[1];
if (nrow >= 0 && nrow < row && ncol >= 0 && ncol < col && board[nrow][ncol] == 'O' && !canNotTurn[nrow][ncol]){
queue.offer(new int[]{nrow, ncol});
canNotTurn[nrow][ncol] = true;
}
}
}
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (!canNotTurn[i][j] && board[i][j] == 'O'){
board[i][j] = 'X';
}
}
}
}