class Solution {
void change(vector>& matrix,int& rowSize, int& colSize, int r, int c){
//change col
int m_r = r, m_c = c;
for(m_r = 0; m_r < rowSize; ++m_r){
matrix[m_r][c] = 0;
}
//change row
for(m_c = 0; m_c < colSize; ++m_c){
matrix[r][m_c] = 0;
}
}
public:
void setZeroes(vector>& matrix) {
int rowSize = matrix.size(), colSize = matrix[0].size();
int r = 0, c = 0;
vector> rc;
for(r = 0; r < rowSize; ++r){//遍历数组，寻找等于0的点
for(c = 0; c < colSize; ++c){
if(matrix[r][c] == 0){
rc.emplace_back(r,c);//记录所有0点
}
}
}
for(auto x: rc){
change(matrix, rowSize, colSize, x.first, x.second);//统一更改所有0所在点的行列
}
}
};
没啥好说的
1727class Solution {
public:
int largestSubmatrix(vector>& matrix) {
int rowSize = matrix.size(), colSize = matrix[0].size();
int row = 0, col = 0, sum = 0;
vector vline(colSize,0);
for(row = 0; row < rowSize; ++row){//遍历每一行
for(col = 0; col < colSize; ++col){//遍历每一列
if(matrix[row][col] == 1){//记录当前高度
++vline[col];
}
else{
vline[col] = 0;
}
}
vector tvline = vline;//使用备用数组，进行排序计算
sort(tvline.begin(), tvline.end(),[](int x, int y){
return x>y;
});//降序排序
for(int x = 0; x < tvline.size(); ++x){//确定最大面积
sum = max((tvline[x]*(x+1)),sum);
}
}
return sum;
}
};
思路
以矩阵每一行为起点，向上计算连续1的个数，及求出每个一的最大高度。然后进行排序，求出最大面积。
10341.循环的方式深度优先搜索
class Solution {
public:
vector> colorBorder(vector>& grid, int row, int col, int color) {
vector> Node;//存储需要遍历的节点,row,col,color
vector> visited(grid.size(),vector(grid[0].size(),false));//下一个节点是否被访问
vector> target;//目标染色点的坐标
vector dir = {-1,0,1,0,-1};//确定方向
vector tmp = {row, col, grid[row][col]};
Node.emplace_back(tmp);//存入初始节点
visited[row][col] = true;//最开始的节点一定会被访问
target.emplace_back(row,col);
while(!Node.empty()){//循环遍历每一个需要走的节点
vector curNode = Node[0];//.back();//获取最后一个元素
int isKernel = 0;//是否是内部节点
int i = 0, nextR = 0, nextC = 0;
for(i = 0; i < 4; ++i){
nextR = curNode[0]+dir[i];//获取要走的下一个元素的行
nextC = curNode[1]+dir[i+1];//获取要走的下一个元素的列
//如果节点可走，加入
if(nextR >= 0 && nextR < grid.size() && nextC >= 0 && nextC < grid[0].size()){//合法
if(!visited[nextR][nextC] && (curNode[2] == grid[nextR][nextC])){//当前位置没走过
visited[nextR][nextC] = true;
target.emplace_back(nextR,nextC);//存储要染色的目标
vector tmp = {nextR,nextC,grid[nextR][nextC]};
Node.emplace_back(tmp);
}
}
if(nextR >= 0 && nextR < grid.size() && nextC >= 0 && nextC < grid[0].size() && grid[nextR][nextC] == curNode[2]){
++isKernel;
if(isKernel == 4){//删除节点
auto iter = find(target.begin(),target.end(),make_pair(curNode[0],curNode[1]));
for(; iter != target.end();){
target.erase(iter);
iter =find(target.begin(),target.end(),make_pair(curNode[0],curNode[1]));
}
}
}
}
Node.erase(Node.begin());//删除首元素
}
for(auto x: target){//全部染色
grid[x.first][x.second] = color;
}
return grid;
}
};
思路
本题的题目写得很屎，简单翻译一下
- 和题目最开始选定的点，上下左右相邻任意一个，并且颜色相同，就是连通区域，大概率要染色（下一条解释为什么是大概率）
- 如果点的周围都有连通区域，那么该点本身就不是边界，因此不能染色
- eg:[1,1,1],[1,1,1],[1,1,1]。我们选取坐标为[1][1]的点，它的上下左右都是连通区域，因此[1][1]本身就不能被染色
- 如果点的周围都有连通区域，那么该点本身就不是边界，因此不能染色
- 被染色的点作为新的点，判断新的点的连通区域，重复规则1
基于以上原则，我们的代码逻辑基本上就是以下几点：
- 判断点curNode的周围是否存在颜色相同的点，如果有，以新点的基础上继续判断新点周围的点。
- 如果curNode周围都有颜色相同的点，改点本身不能被染色。
解法
- 循环遍历当前需要遍历的点，直到没有可以遍历的点为止
- 从4个方向判别周围点是否可以被染色，如果可以，视为当前需要遍历的点，并对其存储
- 如果点的4个方向都和中心点的颜色相同，那么中心点不能被染色。
- 存储合法点的染色点。
2.dfs
class Solution {
vector> target;
int dir[5] = {-1,0,1,0,-1};//确定方向
public:
vector> colorBorder(vector>& grid, int row, int col, int color) {
int rowSize = grid.size(), colSize = grid[0].size();
vector> visited(rowSize,vector(colSize));
dfs(grid, visited, row, col, rowSize, colSize);
for(auto x: target){
grid[x.first][x.second] = color;
}
return grid;
}
void dfs(vector> grid, vector>& visited, int& row, int& col, int& rowSize, int& colSize){
if(!(row>=0 && row=0 && col
return ;
}
if(visited[row][col]){//访问过
return ;
}
visited[row][col] = 1;//现在访问
pair curNode = make_pair(row,col);
int isKernal = 0;//是否是内部点
for(int i = 0; i < 4; ++i){//确定下一个方位
int nextR = curNode.first+dir[i];
int nextC = curNode.second+dir[i+1];
if(nextR>=0 && nextR=0 && nextC//合法位置并且color相同
++isKernal;
dfs(grid,visited,nextR,nextC,rowSize, colSize);
}
}
if(isKernal != 4){target.emplace_back(row,col);}
}
};
