首页 > 代码库 > leetcode 之 Surrounded Regions
leetcode 之 Surrounded Regions
Given a 2D board containing ‘X‘ and ‘O‘, capture all regions surrounded by ‘X‘.
A region is captured by flipping all ‘O‘s into ‘X‘s in that surrounded region.
For example,
X X X X X O O X X X O X X O X X
After running your function, the board should be:
X X X X X X X X X X X X X O X X思路：首先把四个边界的O改成A，防止对内部的影响，然后对内部进行处理，处理之后再把边界还原。
class Solution {
public:
void solve_border(vector<vector<char> >& board,int i,int j,int row,int col)
{
board[i][j] = 'A';
if(i+1 < row && board[i+1][j] == 'O')solve_border(board,i+1,j,row,col);
if(j > 0 && board[i][j-1] == 'O')solve_border(board,i,j-1,row,col);
if(i > 0 && board[i-1][j] == 'O')solve_border(board,i-1,j,row,col);
if(j+1 < col && board[i][j+1] == 'O')solve_border(board,i,j+1,row,col);
}
void solve(vector<vector<char> > &board) {
int row = board.size();
if(row <= 0)return;
int col = board[0].size();
int i,j;
for(j = 0;j < col;j++)
{
if(board[0][j] == 'O')solve_border(board,0,j,row,col);
if(board[row-1][j] == 'O')solve_border(board,row-1,j,row,col);
}
for(i = 0;i < row;i++)
{
if(board[i][col-1] == 'O')solve_border(board,i,col-1,row,col);
if(board[i][0] == 'O')solve_border(board,i,0,row,col);
}
for(i = 1; i < row;i++)
{
for(j = 1;j < col;j++)
{
if(board[i][j] == 'O')board[i][j] = 'X';
}
}
for(i = 0; i< row;i++)
{
for(j = 0;j < col;j++)
{
if(board[i][j] == 'A')board[i][j] = 'O';
}
}
}
};Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
click to show follow up.
Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
思路：首先记下第一行和第一列是否有0，然后把所有的清零信息保存在第一行和第一列里。
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix)
{
int rows = matrix.size();
if(rows <= 0)return;
int cols = matrix[0].size();
if(cols <= 0)return;
int i,j;
bool row0 = false,col0 = false;
for(j = 0;j < cols;++j)//判断第一行是否有0
{
if(matrix[0][j]==0)
{
row0 = true;
break;
}
}
for(i = 0;i < rows;++i)//判断第一列是否有0
{
if(matrix[i][0]==0)
{
col0 = true;
break;
}
}
for(i = 1;i < rows;++i)
{
for(j = 1;j < cols;++j)
{
if(matrix[i][j] == 0)
{
matrix[i][0] = matrix[0][j] = 0;//记录在第一行和第一列
}
}
}
for(j = 1; j < cols;++j)
{
if(matrix[0][j] == 0)//把第j列设置为0
{
for(i = 0;i < rows;++i)matrix[i][j] = 0;
}
}
for(i = 1;i < rows;++i)
{
if(matrix[i][0] == 0)//把第i行设置为0
{
for(j = 0;j < cols;++j)matrix[i][j] = 0;
}
}
if(row0)
{
for(j = 0;j < cols;++j)matrix[0][j] = 0;
}
if(col0)
{
for(i = 0;i < rows;++i)matrix[i][0] = 0;
}
}
};leetcode 之 Surrounded Regions
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。