专栏首页机器学习入门算法细节系列(19):广度搜索优先

算法细节系列(19):广度搜索优先

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/72313806

算法细节系列(19):广度搜索优先

详细代码可以fork下Github上leetcode项目,不定期更新。

题目摘自leetcode: 1. Leetcode 407: Trapping Rain Water II 2. Leetcode 310: Minimum Height Trees 3. 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';
                }
            }
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 挑战程序竞赛系列(31):4.5剪枝

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 挑战程序竞赛系列(30):3.4矩阵的幂

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • POJ 刷题系列:1083. Moving Tables

    POJ 刷题系列:1083. Moving Tables 传送门:POJ 1083. Moving Tables 题意: 一条走廊,两栏房间。搬运工每次从房价...

    用户1147447
  • AtCoder Beginner Contest 174 A ~ E

    我看有人用指针来做的,其实道理是一样的,就是字符串中所有的R都在左边,然后所有的W都在右边就行了。

    用户7727433
  • POJ 1845-Sumdiv(厉害了这个题)

    Consider two natural numbers A and B. Let S be the sum of all natural divisors o...

    风骨散人Chiam
  • 数独终盘生成的几种方法

    为了完成矩阵的转换,我们需要有可用的数独终盘矩阵作为种子矩阵才行。可以采用如下做法完成:

    孟君
  • LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

    ShenduCC
  • 1089 狼人杀-简单版 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 挑战程序竞赛系列(31):4.5剪枝

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 洛谷P4704 太极剑(乱搞)

    attack

扫码关注云+社区

领取腾讯云代金券