Skip to content

4_搜索.md

Latest commit

 

History

History
812 lines (672 loc) · 19.6 KB

4_搜索.md

File metadata and controls

812 lines (672 loc) · 19.6 KB
Raw

回溯-Backtract

1、二叉树中和为某一值的路径

二叉树中和为某一值的路径

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> values = new ArrayList<>();
    backtrack(root,target,values,res);
    return res;
}

// values : 记录从根节点到叶子节点的所有路径
// paths : 存储所有可能的结果
private void backtrack(TreeNode root, int target,
                       ArrayList<Integer> values,
                       ArrayList<ArrayList<Integer>> paths) {
    if (root == null) {
        return;
    }
    values.add(root.val);
    if(root.left==null && root.right==null && root.val==target){
        paths.add(new ArrayList<>(values));
    }else{
        backtrack(root.left,target-root.val,values,paths);
        backtrack(root.right,target-root.val,values,paths);
    }
    values.remove(values.size()-1);
}

*2、二叉树的所有路径

二叉树的所有路径

public List<String> binaryTreePaths(TreeNode root) {
    List<String> paths=new ArrayList<>();
    if(root==null){
        return paths;
    }
    List<Integer> values=new ArrayList<>();
    backtrack(root,values,paths);
    return paths;
}

//values 记录从根节点到叶子节点
//paths 记录路径
private void backtrack(TreeNode root, List<Integer> values,List<String> paths){
    if(root==null){
        return;
    }
    values.add(root.val);
    if(root.left==null && root.right==null){ // 到达叶子节点
        paths.add(buildPath(values));
    }else{
        backtrack(root.left,values,paths);
        backtrack(root.right,values,paths);
    }
    values.remove(values.size()-1);
}

private String buildPath(List<Integer> values){
    StringBuilder res=new StringBuilder();
    for(int i=0;i<values.size();i++){
        if(i==values.size()-1){
            res.append(values.get(i));
        }else{
            res.append(values.get(i)).append("->");
        }
    }
    return res.toString();
}

*3、矩阵中的路径

矩阵中的路径

//思路：典型的回溯法思想
private int m,n; //矩阵的长度、宽度
private boolean[][] visted; //标记是否访问

private int[][] d={
    {0,1}, //向右
    {-1,0},//向上
    {0,-1},//向左
    {1,0} //向下
};

private boolean inArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

//从board[startx][starty]开始寻找word[index...word.ength()]
private boolean searchMatrix(char[][] matrix, char[] str,int index,int startx,int starty){
    if(index==str.length-1){ //递归到最后一个元素，检测是否相等
        return matrix[startx][starty] == str[index];
    }
    if(matrix[startx][starty]==str[index]){
        visted[startx][starty] = true;
        for(int i=0;i<4;i++){
            int newX = startx+d[i][0];
            int newY = starty+d[i][1];
            if(inArea(newX,newY) && !visted[newX][newY]){
                if(searchMatrix(matrix,str,index+1,newX,newY)){
                    return true;
                }
            }
        }
        visted[startx][starty] =false;
    }
    return false;
}

//构建二维矩阵
private char[][] buildMatrix(char[] array, int rows, int cols){
    //根据char[] matrix, rows, cols 构建二维的矩阵
    char[][] matrix = new char[rows][cols];
    int index=0;
    for(int i=0;i<rows;i++) {
        for (int j = 0; j < cols; j++) {
            matrix[i][j] = array[index++];
        }
    }
    return matrix;
}

//matirx 就是字符串矩阵;
//rows 和 cols 是其长度和宽度
public boolean hasPath(char[] array, int rows, int cols, char[] str) {
    if(rows==0){
        return false;
    }
    char[][] matrix = buildMatrix(array,rows,cols);

    m = rows;
    n = cols;
    visted = new boolean[m][n];

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(searchMatrix(matrix,str,0,i,j)){
                return true;
            }
        }
    }
    return false;
}

4、单词搜索

单词搜索

private boolean[][] visited;

private int m,n;

private int[][] d={
    {-1,0},
    {0,1},
    {1,0},
    {0,-1}
};

private boolean inArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

//从(startX,startY)位置在 board 中查找 word[index...n]
private boolean dfs(char[][] board,int startX,int startY,String word,int index){
    if(index==word.length()-1){
        return board[startX][startY]==word.charAt(index);
    }
    if(board[startX][startY]==word.charAt(index)){
        visited[startX][startY]=true;
        for(int i=0;i<4;i++){
            int newX=startX+d[i][0];
            int newY=startY+d[i][1];
            if(inArea(newX,newY) && !visited[newX][newY]){
                if(dfs(board,newX,newY,word,index+1)){
                    return true;
                }
            }
        }
        visited[startX][startY]=false;
    }
    return false;
}

public boolean exist(char[][] board, String word) {
    m=board.length;
    if(m==0){
        return false;
    }
    n=board[0].length;
    visited=new boolean[m][n];

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(dfs(board,i,j,word,0)){
                return true;
            }
        }
    }
    return false;
}

*5、N皇后

N皇后

  • 思路：

在第 i 行放上皇后，判断是否其他地方能够放皇后的情况：

(1)竖向：col[j] 表示第 j 列被占用

(2)对角线1：dai1[m] 表示第 m 条对角线1被占用，如 dia1[0]=true 表示[0,0] 位置不能放皇后，

dia1[1] =true 就表示 [0,1]和[1,0] 位置不能放皇后。

对角线1总共有 (2*n-1) 条；m 与 i 、 j 的关系：m=i+j。

(3)对角线2：dai2[m]表示第 m 条对角线被2占用，如 dai2[0]=true 表示[0,3] 位置不能放皇后，

dai2[2]=true 则表示 [0,2] 和 [1,3] 不能放皇后,

对角线2总共有（2*n-1）条；m 与 i、j 关系：m=i-j+n-1。

private List<List<String>> res;

//用于判断是否在同一竖线上，因为index表示行数，是变化的，所以不用判断是否在相同行
private boolean[] cols;
//判断是否在1类对角线上，相应坐标 i+j
private boolean[] dial1;
//判断是否在2类对角线上，相应坐标 i-j+n-1
private boolean[] dial2;

//在 index 行放皇后
//row 记录在 index 行能够放皇后的位置
//比如 row.get(0) = 1，就表示在棋盘的 [0,1] 位置放上皇后
private void putQueen(int n,int index,List<Integer> row){
    if(index==n){
        res.add(generateBoard(n,row));
        return;
    }
    // [index,j] 放皇后
    for(int j=0;j<n;j++){
        if(!cols[j] && !dial1[index+j] && !dial2[index-j+n-1]){
            row.add(j);
            cols[j]=true;
            dial1[index+j]=true;
            dial2[index-j+n-1]=true;
            putQueen(n,index+1,row);
            dial2[index-j+n-1]=false;
            dial1[index+j]=false;
            cols[j]=false;
            row.remove(row.size()-1);
        }
    }
}

//创建棋盘
private List<String> generateBoard(int n, List<Integer> row) {
    List<String> res=new ArrayList<>();
    if(n<=0){
        return res;
    }

    char[][] board=new char[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            board[i][j]='.';
        }
    }
    for(int i=0;i<row.size();i++){
        board[i][row.get(i)]='Q';
    }

    for(int i=0;i<n;i++){
        res.add(new String(board[i]));
    }
    return res;
}

public List<List<String>> solveNQueens(int n) {
    res=new ArrayList<>();
    if(n==0){
        return res;
    }
    cols=new boolean[n];
    dial1=new boolean[2*n-1];
    dial2=new boolean[2*n-1];
    List<Integer> row=new ArrayList<>();
    putQueen(n,0,row);
    return res;
}

6、解数独

解数独

// 思路：回溯法
// 数独矩阵是 9*9 的方阵，也就是有 81 个位置，
// 可以看成是一个长度为 81 的数组，使用 pos(从0开始) 记录在数组中位置
// row[i][m] 表示第 i 行填数字 m 的占用情况，即 row[i][m]=true，表示在第i行填上数字 m 了。
// col[i][m] 表示第 i 列填数字 m 的占用情况，即 col[i][m]=true，表示在第i列填上数字 m 了。
// block[i][m] 表示第 i个九宫格填数字 m 的占用情况
public void solveSudoku(char[][] board) {
    if(board==null){
        return;
    }
    boolean[][] row=new boolean[9][10];
    boolean[][] col=new boolean[9][10];
    boolean[][] block=new boolean[9][10];
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            if(board[i][j]!='.'){ // [i,j]位置已填上数字
                int num= board[i][j]-'0';
                row[i][num]=true;
                col[j][num]=true;
                block[i/3*3+j/3][num]=true;
            }
        }
    }
    for(int pos=0;pos<81;pos++){
        int x=pos/9;
        int y=pos%9;
        if(board[x][y]=='.'){
            if(!putNum(board,pos,row,col,block)){
                continue;
            }
        }
    }
}

// 向 pos 位置放数字
private boolean putNum(char[][] board, int pos,
                       boolean[][] row, boolean[][] col, boolean[][] block){
    if(pos==81){
        return true;
    }
    int nextPos = pos+1; // pos 位置的下一未填数字的位置
    for(;nextPos<81;nextPos++){
        if(board[nextPos/9][nextPos%9]=='.'){
            break;
        }
    }
    // [x,y] 表示 pos 在表格中位置
    int x=pos/9;
    int y=pos%9;

    for(int num=1;num<=9;num++){ // pos 位置可以填 1-9 任意整数
        if(!row[x][num] && !col[y][num] && !block[x/3*3+y/3][num]){
            board[x][y]=(char)(num+'0');
            row[x][num]=true;
            col[y][num]=true;
            block[x/3*3+y/3][num]=true;
            if(putNum(board,nextPos,row,col,block)){
                return true;
            }
            block[x/3*3+y/3][num]=false;
            col[y][num]=false;
            row[x][num]=false;
            board[x][y]='.';
        }
    }
    return false;
}

广度优先-BFS

1、单词接龙

单词接龙

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    wordList.add(beginWord);
    int N = wordList.size();
    int start = N - 1;
    int end = 0;
    while (end < N && !wordList.get(end).equals(endWord)) {
        end++;
    }
    if (end == N) {
        return 0;
    }
    List<Integer>[] graphic = buildGraphic(wordList);
    return getShortestPath(graphic, start, end);
}

private List<Integer>[] buildGraphic(List<String> wordList) {
    int N = wordList.size();
    List<Integer>[] graphic = new List[N];
    for (int i = 0; i < N; i++) {
        graphic[i] = new ArrayList<>();
        for (int j = 0; j < N; j++) {
            if (isConnect(wordList.get(i), wordList.get(j))) {
                graphic[i].add(j);
            }
        }
    }
    return graphic;
}

private boolean isConnect(String s1, String s2) {
    int diffCnt = 0;
    for (int i = 0; i < s1.length() && diffCnt <= 1; i++) {
        if (s1.charAt(i) != s2.charAt(i)) {
            diffCnt++;
        }
    }
    return diffCnt == 1;
}

private int getShortestPath(List<Integer>[] graphic, int start, int end) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] marked = new boolean[graphic.length];
    queue.add(start);
    marked[start] = true;
    int path = 1;
    while (!queue.isEmpty()) {
        int size = queue.size();
        path++;
        while (size-- > 0) {
            int cur = queue.poll();
            for (int next : graphic[cur]) {
                if (next == end) {
                    return path;
                }
                if (marked[next]) {
                    continue;
                }
                marked[next] = true;
                queue.add(next);
            }
        }
    }
    return 0;
}

深度优先-DFS

1、岛屿数量

岛屿数量

// 思路：典型的 flood-fill 算法
private int m,n;

private boolean[][] visited;

private boolean inArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

private int[][] d={
    {-1,0},
    {0,1},
    {1,0},
    {0,-1}
};

private void dfs(char[][] grid,int startx,int starty){
    visited[startx][starty]=true;
    for(int i=0;i<4;i++){
        int newX=startx+d[i][0];
        int newY=starty+d[i][1];
        if(inArea(newX,newY) &&
           (!visited[newX][newY] && grid[newX][newY]=='1')){
            dfs(grid,newX,newY);
        }
    }
}

public int numIslands(char[][] grid) {
    m=grid.length;
    if(m==0){
        return 0;
    }
    n=grid[0].length;
    visited=new boolean[m][n];
    int res=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]=='1' && !visited[i][j]){
                res++;
                dfs(grid,i,j);
            }
        }
    }
    return res;
}

*2、岛屿的最大面积

岛屿的最大面积

private int m,n;

private boolean[][] visited;

private int[][] d={
    {-1,0},
    {0,1},
    {1,0},
    {0,-1}
};

private boolean inArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

private int dfs(int[][] grid,int startx,int starty){
    visited[startx][starty]=true;
    int area=1;
    for(int i=0;i<4;i++){
        int newX=startx+d[i][0];
        int newY=starty+d[i][1];
        if(inArea(newX,newY) &&
           (!visited[newX][newY] && grid[newX][newY]==1)){
            area+=dfs(grid,newX,newY);
        }
    }
    return area;
}

public int maxAreaOfIsland(int[][] grid) {
    m=grid.length;
    if(m==0){
        return 0;
    }
    n=grid[0].length;
    visited=new boolean[m][n];
    int res=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==1 && !visited[i][j]){
                res=Math.max(res,dfs(grid,i,j));
            }
        }
    }
    return res;
}

3、机器人的运动范围

机器人的运动范围

//思路：
//flood-fill 算法
private int m;
private int n;

private boolean[][] visited;

private int[][] d={
    {0,1}, //向右
    {-1,0},//向上
    {0,-1},//向左
    {1,0} //向下
};

private boolean inArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

//获取一个数各个位上的数字相加
private int getNum(int num){
    int sum = 0;
    while(num>0){
        sum += num %10;
        num/=10;
    }
    return sum;
}

private boolean valid(int threshlod ,int x,int y){
    return (getNum(x)+getNum(y))<=threshlod;
}

private int walk(int threshold,int startx,int starty){
    visited[startx][starty]=true;
    int walks = 0;
    if(valid(threshold,startx,starty)){
        walks=1;
    }
    for(int i=0;i<4;i++){
        int newX = startx+d[i][0];
        int newY = starty+d[i][1];
        if(inArea(newX,newY)){
            if(!visited[newX][newY] && valid(threshold,newX,newY)){
                walks += walk(threshold,newX,newY);
            }
        }
    }
    return walks;
}

public int movingCount(int threshold, int rows, int cols) {
    if(threshold<0){ //threshold<0，则机器人就不能走了
        return 0;
    }
    m = rows;
    if(m==0){
        return 0;
    }
    n= cols;
    visited = new boolean[m][n];
    return walk(threshold,0,0);
}

4、被围绕的区域

被围绕的区域

private int m,n;

private boolean[][] visited;

private int[][] d={
    {-1,0},
    {0,1},
    {1,0},
    {0,-1}
};

private boolean inArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

private void dfs(char[][] board,int startx,int starty){
    visited[startx][starty]=true;
    for(int i=0;i<4;i++){
        int newX=startx+d[i][0];
        int newY=starty+d[i][1];
        if(inArea(newX,newY)){
            if(!visited[newX][newY] && board[newX][newY]=='O'){
                dfs(board,newX,newY);
            }
        }
    }
}

public void solve(char[][] board) {
    m=board.length;
    if(m==0){
        return;
    }
    n=board[0].length;
    visited=new boolean[m][n];

    //从边边界进行标记
    for(int j=0;j<n;j++){
        if(!visited[0][j] && board[0][j]=='O'){
            dfs(board,0,j);
        }
        if(!visited[m-1][j] && board[m-1][j]=='O'){
            dfs(board,m-1,j);
        }
    }

    for(int i=0;i<m;i++){
        if(!visited[i][0] && board[i][0]=='O'){
            dfs(board,i,0);
        }
        if(!visited[i][n-1] && board[i][n-1]=='O'){
            dfs(board,i,n-1);
        }
    }

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(!visited[i][j] && board[i][j]=='O'){
                board[i][j]='X';
            }
        }
    }
}

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

太平洋大西洋水流问题

private int m,n;
private boolean[][] pacific;
private boolean[][] atlantic;

private int[][] d={
    {-1,0},
    {0,1},
    {1,0},
    {0,-1}
};

private boolean inArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

private void dfs(int[][] matrix,int startx,int starty,boolean[][] visited){
    visited[startx][starty]=true;
    for(int i=0;i<4;i++){
        int newX=startx+d[i][0];
        int newY=starty+d[i][1];
        if(inArea(newX,newY)){
            if(!visited[newX][newY] && matrix[newX][newY]>=matrix[startx][starty]){
                dfs(matrix,newX,newY,visited);
            }
        }
    }
}

public List<List<Integer>> pacificAtlantic(int[][] matrix) {
    List<List<Integer>> res=new ArrayList<>();
    m=matrix.length;
    if(m==0){
        return res;
    }
    n=matrix[0].length;
    pacific=new boolean[m][n];
    atlantic=new boolean[m][n];

    for(int j=0;j<n;j++){
        if(!pacific[0][j]){
            dfs(matrix,0,j,pacific);
        }
        if(!atlantic[m-1][j]){
            dfs(matrix,m-1,j,atlantic);
        }
    }

    for(int i=0;i<m;i++){
        if(!pacific[i][0]){
            dfs(matrix,i,0,pacific);
        }
        if(!atlantic[i][n-1]){
            dfs(matrix,i,n-1,atlantic);
        }
    }

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(pacific[i][j] && atlantic[i][j]){
                res.add(Arrays.asList(i,j));
            }
        }
    }
    return res;
}