专栏首页Java小白成长之路刷题第5篇:被包围的区域

刷题第5篇:被包围的区域

各位同学好!本周的刷题结果又来了!本周刷的一些题目里面,觉得下面这道题目比较有点意思吧!有时候我们容易陷入一个思想的误区里面,稍微使用一下逆向思维,可能会带来不一样的感受!


下面这道题目,属于LeetCode上面的第130题。

题目描述

题目的链接:

https://leetcode-cn.com/problems/surrounded-regions/

这道题看上去有点像类似于行军作战,一旦字母"O"被字母"X"包围,那么字母"X"就会"干掉"字母"o"。类似于下面这样

                XXXXXXXXXX                          XXXXXXXXXX
                OOOXXXXXOO                          OOOXXXXXOO
                XXXXXOOXXX          ----->          XXXXXXXXXX
                XXOOXXXXXX                          XXXXXXXXXX
                XXXXXOOOOO                          XXXXXOOOOO

解法一:逐个进行DFS

解法一属于一种直观的思考。主要就是在用一种直观的思路,使用深度优先算法DFS,逐行逐列遍历每一个元素。

当元素为字母"O"的时候,对其周围的元素进行探索,查看是否能够遇到一个边界元素"O"。

如果进行DFS的过程中,没有遇到边界的字母"O",则将此过程中所有的字母"O"更换为字母"X"。

如果进行DFS过程中,遇到了一个边界字母"O",则对此过程中遍历的字母都不进行操作。

实现代码如下:

public void solve(char[][] board) {
    int rows = board.length;
    if (rows == 0) {
        return;
    }
    int cols = board[0].length;
    //考虑除去边界以外的所有 O
    for (int i = 1; i < rows - 1; i++) {
        for (int j = 1; j < cols - 1; j++) {
            if (board[i][j] == 'O') {
                //visited 用于记录 DFS 过程中已经访问过的节点
                HashSet<String> visited = new HashSet<>();
                //如果没有到达边界,就把当前 O 置为 X
                if (!solveHelper(i, j, board, visited)) {
                    board[i][j] = 'X';
                }
            }
        }
    }
}

private boolean solveHelper(int row, int col, char[][] board, HashSet<String> visited) {
    //是否访问过
    if (visited.contains(row + "@" + col)) {
        return false;
    }
    visited.add(row + "@" + col);

    //到达了 X 直接返回 false
    if (board[row][col] == 'X') {
        return false;
    }

    if (row == 0 || row == board.length - 1 || col == 0 || col == board[0].length - 1)     {
        return true;
    }

    //分别尝试四个方向
    if (solveHelper(row - 1, col, board, visited, memoization)
        || solveHelper(row, col - 1, board, visited, memoization)
        || solveHelper(row + 1, col, board, visited, memoization)
        || solveHelper(row, col + 1, board, visited, memoization)) {
        return true;
    } else {
        return false;
    }
}

但是遗憾的是,这样的代码提交到LeetCode上面之后,运行时间超时了,无法通过。

解法二:由外向内

在上面的解法一中,我们对整个board进行遍历。在每次的遍历过程中,我们需要对所遇到的字母"O"先进行保存处理,因为我们不知道此字母在后面的遍历过程中是否会遇到的边界上的"O",所以在内存上面也会遇到很多问题。

那么我们尝试着换一种思路。经过分析可以发现:在所有的字母"O"中,可以将其分为两类,一类是被包围的"O",最后需要被字母"X"替换;还有一类是没有被包围的"O",最后不需要进行任何操作。

如果我们的起始字母"O",就已经处于边界点,那么根据边界点"O"进行DFS搜索得到的字母"O"都属于没有被包围的点。

记录下这些没有被包围的点之后,那么可以将剩下的"O"进行替换处理。

所以,我们解法二的处理应该将边界点"O"作为入口,遍历每个邻居节点。

与此同时,我们可以对未被包围的字母"O",使用一个"#"作为占位符处理。全部遍历完之后,先将剩余的"O"替换为"X",再将"#"替换为"O"。

实现代码如下:

public void solve(char[][] board) {
    if (board.length < 3 || board[0].length < 3){
        return;
    }
    int[][] direction = {{-1,0},{1,0},{0,1},{0,-1}};
    int m = board.length;
    int n = board[0].length;
    for (int i = 0; i < m ; i++){
        for (int  j =0 ; j < n ; j++){
            if (board[i][j] == 'O' && T130_isEdge(i,j,board)){//从边界开始向内进行腐蚀
                T130(i,j,direction,board);
            }
        }
    }
    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] == '#'){//将未被包含的字符'O'还原回来
                board[i][j] = 'O';
            }
        }
    }
}
public void T130 (int row,int column,int[][] direction,char[][] board ){
    if (board[row][column] == '#' || board[row][column] == 'X'){
        return;
    }
    board[row][column] = '#';//使用一个占位符表示未被包围的字符'O'
    for (int i = 0 ; i < direction.length ; i++){
        //获取新的坐标
        int X = row+direction[i][0];
        int Y = column+direction[i][1];
        if (T130_helper(X,Y,board.length,board[0].length)){//如果新坐标在内部
            T130(X,Y,direction,board);
        }
    }
}
public boolean T130_isEdge(int row,int column,char[][] board){
    return row == 0 || column == 0 || row == board.length-1 || column == board[0].length-1;
}
public boolean T130_helper (int X,int Y,int row,int column){
    return X >= 0 && X <= row-1 && Y >= 0 && Y <= column-1 ;
}

上面的代码运行通过了!

总结

在解法一中,我们在使用DFS的时候,由于每次遍历开始,我们无法区分当前"O"属于哪一类,所以需要等待,一直到最后的字母"O",结束之后,才可以进行判断。

在解法二中,我们使用的是一种逆向思维,从边界开始思考,那么在使用DFS进行遍历的时候,可以直接将其归为未被包围的"O"点,大大减少了我们判断的难度。所以时间会更加快一点!

本文分享自微信公众号 - Java小白成长之路(Java_xiaobai),作者:鹏程万里

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-16

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 回溯:系列经典题目

    对于回溯算法,一开始接触感觉还是挺难的,随着刷到的题目的数量增多,慢慢也可以总结出来相应的套路出来。大家一起来看看下面的伪代码

    鹏-程-万-里
  • 剑指offer第11题:机器人运动范围

    此方法我们可以直接按照题目中的要求,将所有的方格全都访问一遍,由于所有的格子需要满足一个条件,连续性和单元格的坐标和小于n即可。

    鹏-程-万-里
  • 剑指offer第10题:矩阵中的路径

    根据题目要求,需要我们从一个已知矩阵中找到一个可以挨个形成给定字符串的路径。如果有这条路径的话,我们需要返回true,如果没有的话,我们返回false,并且相同...

    鹏-程-万-里
  • 基于一维级联快速膨胀与腐蚀算法

    一:基本原理 膨胀与腐蚀是图像形态学两个基本操作之一,传统的代码实现都是基于二维窗口卷积模式,对于正常的3x3窗口要八次与运算,而基于一维级联方式先X方向后Y方...

    OpenCV学堂
  • OpenCV 学习日记(三)--- 常见数据类型

    OpenCV基本数据类型: CvPoint,这些结构中最简单的一个,包含两个整型变量x和y。 CvPoint还有两个兄弟:CvPoint2D32f 和 CvPo...

    TeeyoHuang
  • 华为突破封锁,对标谷歌Dropout专利,开源自研算法Disout,多项任务表现更佳

    美国持续封锁,华为的技术自研,已经深入到了AI底层算法层面上,并开始将研究成果面向业界开源。

    量子位
  • poj 1316 Self Numbers

    题意:找出10000以内所有的不能由n+n的各位数字和组成的数字 #include<stdio.h> #include<string.h> int main()...

    用户1624346
  • 实例变量的懒初始化

    jeremyxu
  • C++版 - Leetcode 69. Sqrt(x) 解题报告【C库函数sqrt(x)模拟-求平方根】

    Total Accepted: 93296 Total Submissions: 368340 Difficulty: Medium

    Enjoy233
  • 零售业数据分析那些事儿

    随着大数据时代的到来,数据分析已经成为了零售业非常重要的一环,也是精细化运营的基础。零售业数据分析包括:

    静一

扫码关注云+社区

领取腾讯云代金券