基础算法:深广度优先遍历及相关题目

基础算法:深广度优先遍历及相关题目,第1张

深度优先遍历

通常采用方法递归实现,主要思路是找到一条路后一头钻到底(符合递归方法中只有触底return后,才会执行后续语句)(堆栈也可实现)

广度优先遍历

通常采用队列辅助实现,主要思路是遇到一个节点后,将其周遭所有符合条件的节点都记录起来,逐个处理。

岛屿数量

岛屿定义:数组由1 0组成,一整片1即为一个岛屿。
深度优先遍历:

public int numIslands(char[][] grid) {
        int res = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    res++;
                }
            }
        }

        return res;
    }

    public void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }

使用递归思路,遍历地图上所有格子,每当遇到一个1数值,深度遍历将其连接的1全部标记(将走过的格子值设置为0即可),后续遍历就可以无视走过的格子。
需要注意对边界的判断需要优先于值判断。

②广度优先遍历:

public int numIslands(char[][] grid) {
        int res = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    res++;
                }
            }
        }

        return res;
    }
public void bfs(char[][] grid, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {i, j});
        while (!queue.isEmpty()) {
            int[] cur = queue.remove();
            int row = cur[0];
            int col = cur[1];
            if (row < grid.length && col < grid[0].length && row >= 0 && col >= 0 && grid[row][col] == '1') {
                grid[row][col] = '0';
                queue.add(new int[] {row + 1, col});
                queue.add(new int[] {row - 1, col});
                queue.add(new int[] {row, col + 1});
                queue.add(new int[] {row, col - 1});
            }
        }
    }

遍历全部格子,遇到1时开始遍历:(深度使用函数递归,广度使用队列辅助)
队列记录所有有延展可能性的格子,每次d出一个进行判断,若在值为1,说明还有可能扩展,则标记后将其相邻格子加入队列,以便后续判断。

省份数量

二维数组i,j值对应城市i与城市j是否相连,相连则属于同一个省份。
①深度优先遍历

public int findCircleNum(int[][] isConnected) {
        int provinces = 0;
        boolean[] visited = new boolean[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            if (!visited[i]) {
                dfs(isConnected, i, visited);
                provinces++;
            }
        }

        return provinces;
    }

    public void dfs(int[][] isconnected, int i, boolean[] visited) {
        for (int j = 0; j < isconnected.length; j++) {
            if (isconnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(isconnected, j, visited);
            }
        }
    }

从每个城市单独出发去查找其与其他城市的连接性,在遍历过城市后也需要标记(创建visited数组记录);主函数中的循环是查找基准城市(可看作i),在方法内再向其余城市发散判断连接(可连接的城市看作j),标记后再以j城市进行发散。

②广度优先遍历

public int findCircleNum(int[][] isConnected) {
        int provinces = 0;
        boolean[] visited = new boolean[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            if (!visited[i]) {
                bfs(isConnected, i, visited);
                provinces++;
            }
        }

        return provinces;
    }
public void bfs(int[][] isconnected, int i, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        while (!queue.isEmpty()) {
            Integer city = queue.remove();
            visited[city] = true;
            for (int j = 0; j < isconnected.length; j++) {
                if (isconnected[city][j] == 1 && !visited[j]) {
                    queue.add(j);
                }
            }
        }
    }

依旧用队列辅助遍历,主函数内选基准城市,在方法内开始发散遍历,每次将所有与基准城市相连的城市标记并加入队列,后续不断d出重复上述 *** 作即可。

上述两题都是每次碰到所需区域就将结果+1,主要处理都是在将相关区域进行标记处理,类似第一题,经过标记处理后,保证每次遇到1即为新的岛屿。

填充每个节点的下一个右侧节点指针 II

题目给出一个树,目的是在每一层横向加一个链表指向。

public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            Node pre = null;

            for (int i = 0; i < size; i++) {
                Node remove = queue.remove();
                if (pre != null) {
                    pre.next = remove;
                }
                pre = remove;
                if (remove.left != null) {
                    queue.add(remove.left);
                }
                if (remove.right != null) {
                    queue.add(remove.right);
                }
            }
        }
        return root;
    }

既然是横向加链表,第一个想到广度优先遍历,在本次的广度优先仍然使用队列先入先出辅助实现,但需要进行切换行的判断,每到新行都需要重新记录行链表的头结点(代码中每次取的size就是每一行包含的节点数,那么每次遍历size个节点就是每次遍历一行;这点清楚后,每一行头结点的清楚在for遍历前进行即可),边向右遍历边记录。

另一棵树的子树

判断树中是否包含目标子树。

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return bfs(root, subRoot);
    }

    private boolean bfs(TreeNode sTree, TreeNode tTree) {
        if (sTree == null) {
            return false;
        }
        return check(sTree, tTree) || bfs(sTree.left, tTree) || bfs(sTree.right, tTree);
    }

    private boolean check(TreeNode sTree, TreeNode tTree) {
          if (sTree == null && tTree == null) {
              return true;
          }
          if (sTree == null || tTree == null || sTree.val != tTree.val) {
              return false;
          }

          if (sTree.val == tTree.val) {
              return check(sTree.left, tTree.left) && check(sTree.right, tTree.right);
          }
          return false;
    }

持续深度遍历,每次遍历都进行判断:
两者都为空:符合子树条件,并且说明探到底后完全相同,可以返回。
某一方为空:不符合条件
两节点值不同:不符合条件
值相同时:进行左右叶子结点的判断。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/871905.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-13
下一篇 2022-05-13

发表评论

登录后才能评论

评论列表(0条)

保存