算法细节系列（19）：广度搜索优先
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434750
算法细节系列（19）：广度搜索优先
详细代码可以fork下Github上leetcode项目，不定期更新。
题目摘自leetcode：
- Leetcode 407: Trapping Rain Water II
- Leetcode 310: Minimum Height Trees
- Leetcode 130: Surrounded Regions
Leetcode 407 Trapping Rain Water II
思路：
没想到它居然是一道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;
}Leetcode 310 Minimum Height Trees
思路：
这道题，看上去很复杂实则思路很简单。把该问题归简为求最长路径，如果有了这最长路径，那么所求的结点一定是这条最长路径的中间结点。（一个或者两个）
那么问题来了，如何求最长路径呢，用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.
Leetcode 130 Surrounded Regions
思路：
反着来就好了，不能围住的原因只有一个，”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';
}
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年05月16日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录