题解 | #被围绕的区域#

被围绕的区域

http://www.nowcoder.com/practice/3946670643fe4ec2aedcc2be45aed1a9

描述

给定一个 n*m 大小的的矩阵,矩阵中由 ‘X' 和 'O' 构成,找到所有被 'X' 围绕的区域,并将其用 'X' 填充。
例如:
[['X','X','X','X'],
['X','O','O','X'],
['X','O','X','X'],
['X','X','O','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'。但凡任何一个方向没有'X',这个位置就没有被包围。否则就是被围住的。
这个算法是简单粗暴的,有重复操作的过程,但也是最简单的。
时间复杂度O(n2m或nm2):最坏情况是全为O时,这样里面的元素每个都要查(n+m-2)次,
                           而需要查的元素总共有n*m-2(m+n-2)个,所以复杂度为n2m或nm2
空间复杂度O(1):只定义了几个变量
优化思路:定义一个结构体
 struct  A {
   bool up;//保存当前检查到的上面是否有X,有就为1,否就为0
   bool left;//保存当前检查到左边是否有X,有就为1,否就为0;
   int low;//下面开始出现x的位置
   int right;//右边开始出现x的位置
 * };
保存每个位置的左边是否出现x,上边是否出现x,因为整个遍历过程是从左向右,从上到下的,在定义一个vector<A> 型的数组,保存每次遍历结果,
这样当出现遍历到(i,j)位置只需要检查上一个是否为X,是x直接不用管,否则直接看上一个的up。同理检查左边,左边第一个是X,直接不用管,
否则看左边第一个的left值。而右边只需要看左边第一个的right是否大于当前j。同样的下边看上一个的low是否大于当前的i。
如果想进一步优化,还可以定义两个bool型数组,col[m]和row[n]。row[i]只要该行全为O,就为true,col[j]只要该列全为O就为true,
这样每次先判断row[i]和col[j] 是否为真,真直接为O。这样即使是最坏情况时间复杂度也只有O(n*m)。但就是空间复杂度高了点,对n和m比较大
还是可以用空间换时间的。
上面两个优化思路就不写了,这题目n和m也不是特别大。
class Solution {
public:
    vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
        int n=board.size();
        if(n==1) return board;//只有一行直接返回
        int m=board[0].size();
        if(m==1) return board;//只有一列直接返回
        for(int i=1;i<n-1;++i)
            for(int j=1;j<m-1;++j) 
                if(board[i][j]=='O'){
                    //结果返回4,说明上下左右都有X,赋值为X,否则不做操作
                   if(check(board,i,j,n-1,m-1)==4)
                       board[i][j]='X';
                }
        return board;
    }
    int check(vector<vector<char> > &board,int i,int j,int n,int m) {
        int num=0;
        for(int k=i-1;k>=0;--k) //检查(i,j)上面
            if(board[k][j]=='X') {++num;break;}
        for(int k=i+1;k<=n;++k)//检查(i,j)下面
            if(board[k][j]=='X') {++num;break;}
        for(int k=j-1;k>=0;--k)//检查(i,j)左边
            if(board[i][k]=='X') {++num;break;}
        for(int k=j+1;k<=m;++k)//检查(i,j)右边
            if(board[i][k]=='X') {++num;break;}
        return num;
    }
};


全部评论

相关推荐

头像
11-27 14:28
长沙理工大学
刷算法真的是提升代码能力最快的方法吗?&nbsp;刷算法真的是提升代码能力最快的方法吗?
牛牛不会牛泪:看你想提升什么,代码能力太宽泛了,是想提升算法能力还是工程能力? 工程能力做项目找实习,算法也分数据结构算法题和深度学习之类算法
点赞 评论 收藏
分享
10-24 11:10
山西大学 Java
若梦难了:哥们,面试挂是很正常的。我大中厂终面挂,加起来快10次了,继续努力吧。
点赞 评论 收藏
分享
微风不断:兄弟,你把四旋翼都做出来了那个挺难的吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务