回溯系列二之泛洪遍历所有

喜欢ヅ旅行 2022-11-28 00:58 88阅读 0赞

### 文章目录 ###

*   *  01系列问题总结
     *   *  被环绕的区域
         *   *  Question
             *  Thinking
             *  Coding
         *  岛屿问题
         *   *  Question
             *  Thinking
             *  Coding
         *  最长连续1
         *   *  Question
             *  Thinking
             *  Coding
         *  图像渲染
         *   *  Question
             *  Thinking
             *  Coding

## 01系列问题总结 ##

> 广告： github上新开立了一个仓库[May-Nodes][]，本篇博客也收录其中。包括但不限于之前面试遇到的相关数据库,计算机操作系统,Java基础知识，计算机网络以及LeetCode等算法题解等知识。届时也会整理学习使用的PDF文档与资源。有需要的小伙伴 可以点个关注和`star`。在持续更新中，总会遇到你想要的。

### 被环绕的区域 ###

#### Question ####

给定一个二维的矩阵，包含 ‘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’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

#### Thinking ####

思想是这样的，因为我们要判断哪些能够转换成为‘X’是来判断是否与边界有接壤，我们就可以来对是在边界上并且值为‘o’的进行一个深度优先搜索，查找出来有有接壤的地方更换成为另外一个值。这样，剩下的还是‘o’的就表示是和边界没有接壤的。

#### Coding ####

class Solution { 
        public void solve(char[][] board) { 
            if (board == null || board.length == 0) return;
            int m = board.length;
            int n = board[0].length;
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    // 从边缘o开始搜索
                    boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                    if (isEdge && board[i][j] == 'O') { 
                        dfs(board, i, j);
                    }
                }
            }
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    if (board[i][j] == 'O') { 
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == '#') { 
                        board[i][j] = 'O';
                    }
                }
            }
        }
    
        public void dfs(char[][] board, int i, int j) { 
            if (i < 0 || j < 0 || i >= board.length  || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') { 
                // board[i][j] == '#' 说明已经搜索过了. 
                return;
            }
            board[i][j] = '#';
            dfs(board, i - 1, j); // 上
            dfs(board, i + 1, j); // 下
            dfs(board, i, j - 1); // 左
            dfs(board, i, j + 1); // 右
        }
    }

### 岛屿问题 ###

#### Question ####

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

**示例 1:**

输入:

11110
    11010
    11000
    00000

输出: 1

**示例 2:**

输入:

11000
    11000
    00100
    00011

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

#### Thinking ####

思想可以和第一题的思想类似，我们可以在一次的进入中，表示进入到一个岛屿，然后对其进行系列的变值操作，将可以得到关联的都更换一个值，然后再进入到下一轮的循环中。

#### Coding ####

private static int numIslands(int[][] grid) { 
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        int max=Integer.MIN_VALUE;
        for (int i = 0;i < m;i ++){ 
            for (int j = 0;j < n;j ++){ 
                if(grid[i][j]==1){ 
                   count++;
                   merge(grid,i,j);
    
                }
            }
          
        }
        return count;
    }
        private static  void merge(int[][] grid,int i,int j){ 
            int m = grid.length;
            int n = grid[0].length;
            if(i < 0 || i >= m || j < 0 || j >= n || grid[i][j]!=1) return ;
                grid[i][j] = -1;
                merge(grid,i - 1,j);
                merge(grid,i + 1,j);
                merge(grid,i,j - 1);
                merge(grid,i,j + 1);
        }

### 最长连续1 ###

#### Question ####

现有一二维数组由0，1组成，对于任意的值，其上下左右为其相邻接，求最大连续1的个数。

1110
    0101
    0110
    0010

这个时候应该返回7。

#### Thinking ####

同上题套路相同，外层是一个双重的循环处理，然后进行上下左右的判断，注意将判断过的值置为-1 防止重复的计算，不满足条件时候返回0.

#### Coding ####

private  static  int p;
    private static int numIslands(int[][] grid) { 
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        int max=Integer.MIN_VALUE;
        for (int i = 0;i < m;i ++){ 
            for (int j = 0;j < n;j ++){ 
                if(grid[i][j]==1){ 
                    p=0;
                    int sum=merge(grid,i,j);
                    max=Math.max(sum,max);
                }
            }
        }
        return max;
    }
        private static int  merge(int[][] grid,int i,int j){ 
            int m = grid.length;
            int n = grid[0].length;
            if(i < 0 || i >= m || j < 0 || j >= n || grid[i][j]!=1) return 0;
                p++;
                grid[i][j] = -1;
                merge(grid,i - 1,j);
                merge(grid,i + 1,j);
                merge(grid,i,j - 1);
                merge(grid,i,j + 1);
            return p;
            
        }

### 图像渲染 ###

#### Question ####

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例 1:

image = [[1,1,1],[1,1,0],[1,0,1]]
    sr = 1, sc = 1, newColor = 2
    输出: [[2,2,2],[2,2,0],[2,0,1]]
    解析: 
    在图像的正中间，(坐标(sr,sc)=(1,1)),
    在路径上所有符合条件的像素点的颜色都被更改成2。
    注意，右下角的像素没有更改为2，
    因为它不是在上下左右四个方向上与初始点相连的像素点。

#### Thinking ####

同前面的思想大体都是一致的，就是进行遍历查询，简单注意边界即可。并且对于想要进行替换的值本就和

#### Coding ####

public int[][] floodFill(int[][] image, int sr, int sc, int newColor) { 
          int h = image.length;
            int l = 0;
            if (h > 0) { 
                l = image[0].length;
            }
            int temp = image[sr][sc];
              if(temp!=newColor)
            results(image,temp,sr,sc,newColor);
            return  image;
    
        }
    
        private  static void results(int [][]image,int temp,int sr,int sc,int newColor){ 
    
            if(sr<0||sr>=image.length || sc<0 || sc>=image[0].length)
            { 
                return ;
            }
            if(image[sr][sc]== temp){ 
                image[sr][sc] = newColor;
                results(image,temp,sr-1,sc,newColor);
                results(image,temp,sr+1,sc,newColor);
                results(image,temp,sr,sc-1,newColor);
                results(image,temp,sr,sc+1,newColor);
    
            }
            return;
        }

[May-Nodes]: https://github.com/maycope/May-Nodes