LeetCode 算法之搜索

发布于 2023-09-02 00:17:44 字数 14716 浏览 17 评论 0

深度优先搜索和广度优先搜索广泛运用于树和图中,但是它们的应用远远不止如此。

BFS

广度优先搜索一层一层地进行遍历,每层遍历都是以上一层遍历的结果作为起点,遍历一个距离能访问到的所有节点。需要注意的是,遍历过的节点不能再次被遍历。 第一层:

  • 0 -> {6,2,1,5}

第二层:

  • 6 -> {4}
  • 2 -> {}
  • 1 -> {}
  • 5 -> {3}

第三层:

  • 4 -> {}
  • 3 -> {}

每一层遍历的节点都与根节点距离相同。设 di 表示第 i 个节点与根节点的距离,推导出一个结论:对于先遍历的节点 i 与后遍历的节点 j,有 di <= dj。利用这个结论,可以求解最短路径等 最优解 问题:第一次遍历到目的节点,其所经过的路径为最短路径。应该注意的是,使用 BFS 只能求解无权图的最短路径,无权图是指从一个节点到另一个节点的代价都记为 1。 在程序实现 BFS 时需要考虑以下问题:

  • 队列:用来存储每一轮遍历得到的节点;
  • 标记:对于遍历过的节点,应该将它标记,防止重复遍历。

DFS

广度优先搜索一层一层遍历,每一层得到的所有新节点,要用队列存储起来以备下一层遍历的时候再遍历。 而深度优先搜索在得到一个新节点时立即对新节点进行遍历:从节点 0 出发开始遍历,得到到新节点 6 时,立马对新节点 6 进行遍历,得到新节点 4;如此反复以这种方式遍历新节点,直到没有新节点了,此时返回。返回到根节点 0 的情况是,继续对根节点 0 进行遍历,得到新节点 2,然后继续以上步骤。 从一个节点出发,使用 DFS 对一个图进行遍历时,能够遍历到的节点都是从初始节点可达的,DFS 常用来求解这种 可达性 问题。 在程序实现 DFS 时需要考虑以下问题:

  • 栈:用栈来保存当前节点信息,当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
  • 标记:和 BFS 一样同样需要对已经遍历过的节点进行标记。

1.岛屿的最大面积

695.给定一个包含了一些 0 和 1 的非空二维数组 grid 。 一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。 找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ,因为岛屿只能包含水平或垂直的四个方向的 1 。 思路:对遍历过的 1 清零。

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        int maxArea = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    maxArea = Math.max(maxArea, dfs(grid, m, n, i, j));
                }
            }
        }
        return maxArea;

    }
    private int dfs(int[][] grid, int m, int n, int i, int j){
        if(i < 0 || j < 0 || i >= m || j >= n) return 0;
        if(grid[i][j] == 0) return 0;
        grid[i][j] = 0;
        int area = 1;
        area += dfs(grid, m, n, i + 1, j);
        area += dfs(grid, m, n, i - 1, j);
        area += dfs(grid, m, n, i, j + 1);
        area += dfs(grid, m, n, i, j - 1);
        return area;
    }
}

2.岛屿数量

200.给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。

输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

思路:可以将矩阵表示看成一张有向图。

class Solution {
    public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0){
            return 0;
        }
        int m = grid.length, n = grid[0].length;
        int num = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    num++;
                    dfs(grid, m, n, i, j);
                }
            }
        }
        return num;
    }
    private void dfs(char[][] grid, int m, int n, int i, int j){
        if(i < 0 || j < 0 || i >= m || j >= n) return;
        if(grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid, m, n, i+1, j);
        dfs(grid, m, n, i-1, j);
        dfs(grid, m, n, i, j+1);
        dfs(grid, m, n, i, j-1);
    }
}

3.朋友圈

547.班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。 给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果 M[i][j] = 1,表示已知第 i 个和 j 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。 思路:好友关系可以看成是一个无向图,例如第 0 个人与第 1 个人是好友,那么 M[0][1] 和 M[1][0] 的值都为 1。 使用一个 visited 数组, 依次判断每个节点, 如果其未访问, 朋友圈数加 1 并对该节点进行 dfs 搜索标记所有访问到的节点。

class Solution {
    public int findCircleNum(int[][] M) {
        if(M == null || M.length == 0 || M[0].length == 0) return 0;
        int n = M.length;
        int num = 0;
        boolean[] visited = new boolean[n];
        for(int i = 0; i < n; i++){
            if(!visited[i]){
                num++;
                dfs(M, n, i, visited);
            }
        }
        return num;
    }
    private void dfs(int[][] M, int n, int i, boolean[] visited){
        visited[i] = true;
        for(int k = 0; k < n; k++){
            if(M[i][k] == 1 && !visited[k]){
                dfs(M, n, k, visited);
            }
        }
    }
}

3.被围绕的区域

130.给定一个二维的矩阵,包含 'X' 和 'O'(字母 O)。 找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。 示例:

X X X X
X O O X
X X O X
X O X X

运行你的函数后,矩阵变为:

X X X X
X X X X
X X X X
X O X X

解释: 被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。 思路: 先填充最外侧以及最外侧相连的,剩下的就是里侧了。 (从边缘往里走)

class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0 || board[0].length == 0) return;
        int m = board.length, n = board[0].length;
        for(int i = 0; i < m; i++){
            dfs(board, m, n, i, 0);
            dfs(board, m, n, i, n-1);
        }
        for(int j = 0; j < n; j++){
            dfs(board, m, n, 0, j);
            dfs(board, m, n, m-1, j);
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }else if(board[i][j] == 'T'){
                    board[i][j] = 'O';
                }
            }
        }
    }
    private void dfs(char[][] board, int m, int n, int i, int j){
        if(i < 0 || j < 0 || i >= m || j >= n) return;
        if(board[i][j] != 'O') return;
        board[i][j] = 'T';
        dfs(board, m, n, i+1, j);
        dfs(board, m, n, i-1, j);
        dfs(board, m, n, i, j+1);
        dfs(board, m, n, i, j-1);
    }
}

5.太平洋大西洋水流问题

417.给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界,而“大西洋”处于大陆的右边界和下边界。 规定水流只能按照上、下、左、右四个方向流动,且只能从高到低或者在同等高度上流动。 请找出那些水流既可以流动到“太平洋”,又能流动到“大西洋”的陆地单元的坐标。

给定下面的 5x5 矩阵:

  太平洋 ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * 大西洋

返回:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

思路: 要同时满足可以到达大西洋与太平洋,所以一个点需要进行两次路径的行走,一次以太平洋为目标,一次以大西洋为目标。从内部的点以边界为目标去进行路径行走比较麻烦,但是如果换一个思路,从边缘往里面走。 从边缘向里走就修改通行规则,要往高度比当前点高或者相等的点走。

public class Solution {
    private int m, n;
    private int[][] matrix;
    private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> ret = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return ret;
        }

        m = matrix.length;
        n = matrix[0].length;
        this.matrix = matrix;
        boolean[][] canReachP = new boolean[m][n];
        boolean[][] canReachA = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            dfs(i, 0, canReachP);
            dfs(i, n - 1, canReachA);
        }
        for (int i = 0; i < n; i++) {
            dfs(0, i, canReachP);
            dfs(m - 1, i, canReachA);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachP[i][j] && canReachA[i][j]) {
                    ret.add(Arrays.asList(i, j));
                }
            }
        }

        return ret;
    }

    private void dfs(int r, int c, boolean[][] canReach) {
        if (canReach[r][c]) {
            return;
        }
        canReach[r][c] = true;
        for (int[] d : direction) {
            int nextR = d[0] + r;
            int nextC = d[1] + c;
            if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n
                    || matrix[r][c] > matrix[nextR][nextC]) {

                continue;
            }
            dfs(nextR, nextC, canReach);
        }
    }

}

回溯

Backtracking(回溯)属于 DFS。

  • 普通 DFS 主要用在 可达性问题 ,这种问题只需要执行到特点的位置然后返回即可。
  • 而 Backtracking 主要用于求解 排列组合 问题,例如有 { 'a','b','c' } 三个字符,求解所有由这三个字符排列得到的字符串,这种问题在执行到特定的位置返回之后还会继续执行求解过程。

因为 Backtracking 不是立即返回,而要继续求解,因此在程序实现时,需要注意对元素的标记问题:

  • 在访问一个新元素进入新的递归调用时,需要将新元素标记为已经访问,这样才能在继续递归调用时不用重复访问该元素;
  • 但是在递归返回时,需要将元素标记为未访问,因为只需要保证在一个递归链中不同时访问一个元素,可以访问已经访问过但是不在当前递归链中的元素。

1. 数字键盘组合

17.给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

class Solution {
    private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    StringBuilder sb = new StringBuilder();//用于构造字符串
    List<String> result = new ArrayList<>();//保存结果
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0) return result;
        if(digits.length() == sb.length()){
            result.add(sb.toString());
            return result;//虚假的返回
        }
        int cur = digits.charAt(sb.length()) - '0';
        String letters = KEYS[cur];
        for(char c : letters.toCharArray()){
            sb.append(c);
            letterCombinations(digits);
            sb.deleteCharAt(sb.length()-1);
        }
        return result;
    }
}

2. IP 地址划分

93.给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

class Solution {
    StringBuilder sb = new StringBuilder();
    List<String> result = new ArrayList<>();
    int k = -1;//用于记录此时在划分第几个整数
    public List<String> restoreIpAddresses(String s) {
        k++;
        //已经分好四个整数或者已经将字符串分完
        if(k == 4 || s.length() == 0){
            if(k == 4 && s.length() == 0){//恰好分完
                result.add(sb.toString());
            }
            return result;//虚假的返回
        }

        for(int i = 0; i < s.length() && i <= 2; i++){
            if(i != 0 && s.charAt(0) == '0'){//0 后面不能跟其他数
                break;
            }
            String part = s.substring(0, i+1);
            if(Integer.valueOf(part) <= 255) {
                if(sb.length() != 0){//第一个整数前不用加
                    part = "." + part;
                }
                sb.append(part);
                restoreIpAddresses(s.substring(i+1));
                sb.delete(sb.length() - part.length(), sb.length());
                k--;//k 也要复原
            }
        }
        return result;
    }
}

剑指 27.字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc,则打印出由字符 a,b,c 所能排列出来的所有字符串 abc,acb,bac,bca,cab 和 cba。

输入一个字符串,长度不超过 9(可能有字符重复),字符只包括大小写字母。

思路: 回溯。 固定 A 不动,然后交换 B 与 C,从而得到"ABC" 和 "ACB" 同理,对于"BAC"、"BCA" 、"CAB"和"CBA"是同样道理。 当两个字符相同时,不应该交换。

  • 递归函数的功能:dfs(int pos, string s), 表示固定字符串 s 的 pos 下标的字符 s[pos]
  • 递归终止条件:当 pos+1 == s.length()的时候,终止,表示对最后一个字符进行固定,也就说明,完成了一次全排列
  • 下一次递归:dfs(pos+1, s), 很显然,下一次递归就是对字符串的下一个下标进行固定

回溯:每次递归完成后,须重新交换回来。

import java.util.ArrayList;
import java.util.Collections;
public class Solution 
{
    public ArrayList<String> Permutation(String str)
    {
        ArrayList<String> res=new ArrayList<String>();
        if(str.length()==0||str==null)return res;
        int n= str.length();
        helper(res,0,str.toCharArray());
        Collections.sort(res);
        return res;
         
    }
    public void helper( ArrayList<String> res,int index,char []s)
    {
        if(index==s.length-1)res.add(new String(s));
        for(int i=index;i<s.length;i++)
        {
            if(i==index||s[index]!=s[i])
            {
                swap(s,index,i);
                helper(res,index+1,s);
                swap(s,index,i);
            }
        }
         
    }
     
    public void swap(char[]t,int i,int j)
     {
        char c=t[i];
        t[i]=t[j];
        t[j]=c;
    }
}

剑指 65.矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 思路: 回溯。

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        //标志位,初始化为 false
        boolean[] flag = new boolean[matrix.length];
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                 //循环遍历二维数组,找到起点等于 str 第一个元素的值,再递归判断四周是否有符合条件的----回溯法
                 if(judge(matrix,i,j,rows,cols,flag,str,0)){
                     return true;
                 }
            }
        }
        return false;
    }
     
    //judge(初始矩阵,索引行坐标 i,索引纵坐标 j,矩阵行数,矩阵列数,待判断的字符串,字符串索引初始为 0 即先判断字符串的第一位)
    private boolean judge(char[] matrix,int i,int j,int rows,int cols,boolean[] flag,char[] str,int k){
        //先根据 i 和 j 计算匹配的第一个元素转为一维数组的位置
        int index = i*cols+j;
        //递归终止条件
        if(i<0 || j<0 || i>=rows || j>=cols || matrix[index] != str[k] || flag[index] == true)
            return false;
        //若 k 已经到达 str 末尾了,说明之前的都已经匹配成功了,直接返回 true 即可
        if(k == str.length-1)
            return true;
        //要走的第一个位置置为 true,表示已经走过了
        flag[index] = true;
         
        //回溯,递归寻找,每次找到了就给 k 加一,找不到,还原
        if(judge(matrix,i-1,j,rows,cols,flag,str,k+1) ||
           judge(matrix,i+1,j,rows,cols,flag,str,k+1) ||
           judge(matrix,i,j-1,rows,cols,flag,str,k+1) ||
           judge(matrix,i,j+1,rows,cols,flag,str,k+1)  )
        {
            return true;
        }
        //走到这,说明这一条路不通,还原,再试其他的路径
        flag[index] = false;
        return false;
    }
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据

关于作者

0 文章
0 评论
22 人气
更多

推荐作者

qq_E2Iff7

文章 0 评论 0

Archangel

文章 0 评论 0

freedog

文章 0 评论 0

Hunk

文章 0 评论 0

18819270189

文章 0 评论 0

wenkai

文章 0 评论 0

    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文