在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
输入：grid = [[2,1,1],[1,1,0],[0,1,1]] 输出：4
class Solution {
private:
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
public:
int orangesRotting(vector>& grid) {
int res=0;
queue> q;
int m=grid.size();
int n=grid[0].size();
vector> visited(m,vector(n,0));
for(int i=0;i=0&&xnew=0&&ynewvisited[xnew][ynew]?res:visited[xnew][ynew];//记录所有visit中的最大值就是最短腐烂所需要的时间
q.push({xnew,ynew});
}
}
}
for(int i=0;i
463. 岛屿的周长
给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
class Solution {
constexpr static int dx[4] = {0, 1, 0, -1};
constexpr static int dy[4] = {1, 0, -1, 0};
public:
int islandPerimeter(vector> &grid) {
int n = grid.size(), m = grid[0].size();
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j]) {
int cnt = 0;
for (int k = 0; k < 4; ++k) {
int tx = i + dx[k];
int ty = j + dy[k];
if (tx < 0 || tx >= n || ty < 0 || ty >= m || !grid[tx][ty]) {
cnt += 1;//遇到边界或者遇到水就对边长进行加1 因为边长跟边界和水交界的地方才会有边
}
}
ans += cnt;
}
}
}
return ans;
}
};
200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
class Solution {
public:
void dfs(vector>& grid,int x,int y){
if(grid.size()==0) return ;
int m=grid.size();
int n=grid[0].size();
grid[x][y]='0';
if(x-1>=0&&grid[x-1][y]=='1') dfs(grid,x-1,y);//下一个需要遍历的位置负荷要求 并且是岛屿1 这个地方x-1必须卸载前面，因为如果超过数组边界 那么grid[x-1][y]就会出错
if(x+1=0&&grid[x][y-1]=='1') dfs(grid,x,y-1);
if(y+1>& grid) {
if(grid.size()==0) return 0;
int res=0;
for(int i=0;i
695. 岛屿的最大面积
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
class Solution {
public:
int dfs(vector>& image,int x,int y){//返回值需要设置成int 对每一个1进行广搜 搜到一个就加1 最后返回这个1 所相邻的岛屿的面积的大小
int ans=1;//如果是1 那么本身是算在面积里面的 所以初始化需要设置为1
int m=image.size();
int n=image[0].size();
image[x][y]=0;//遍历之后需要将1变为0 防止后续重复遍历
if(x-1>=0&&image[x-1][y]==1) ans+=dfs(image,x-1,y);
if(x+1=0&&image[x][y-1]==1) ans+=dfs(image,x,y-1);
if(y+1& image) {
if(image.size()==0) return 0;
int res=0;
// std::cout<<0;
for(int i=0;i
733. 图像渲染
有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像 。
class Solution {
public:
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
void dfs(vector>& image, int x, int y, int color, int newColor) {
image[x][y] = newColor;//染色操作
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < image.size() && my >= 0 && my < image[0].size()&&image[mx][my] == color) {//没有超过数组的边界 对下一个点进行尝试染色操作 并且判断是否与初始坐标的颜色相同如果颜色相同才进行染色
dfs(image, mx, my, color, newColor);
}
}
}
vector> floodFill(vector>& image, int sr, int sc, int newColor) {
int currColor = image[sr][sc];//记录渲染开始的颜色
if (currColor != newColor) {//如果需要渲染的颜色跟给的newcolor不一样 那么就需要进行染色的操作
dfs(image, sr, sc, currColor, newColor);
}
return image;
}
};
1034. 边界着色
给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。
两个网格块属于同一 连通分量 需满足下述全部条件：
两个网格块颜色相同
在上、下、左、右任意一个方向上相邻
连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：
在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻
在网格的边界上（第一行/列或最后一行/列）
请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色，并返回最终的网格 grid 。
class Solution {
public:
vector dx{ 0,0,-1,1 };
vector dy{ 1,-1,0,0 };
void dfs(vector>& grid, int row, int col, int orcolor, vector>& bord, vector>& visted) {
int m = grid.size();
int n = grid[0].size();
bool border = false;//首先对边界判断变量赋初值
visted[row][col]=true;//将当前点的状态设置为已经被访问的状态
for (int i = 0; i < 4; i++) {
int xnew = row + dx[i];
int ynew = col + dy[i];
if (!(xnew >= 0 && ynew >= 0 && xnew < m && ynew < n && grid[xnew][ynew] == orcolor)) {//下一个点不在范围内或者颜色跟最开始的颜色不同 那么当前点就是边界点
border = true;
}
else if (!visted[xnew][ynew]) {//如果下一个点没有没访问则访问 进行下一步的边界点的判断
dfs(grid, xnew, ynew, orcolor, bord, visted);
}
}
if (border) {//如果是边界 那么将该点的坐标加入到bord中
bord.push_back({ row,col });
}
}
vector> colorBorder(vector>& grid, int row, int col, int color) {
int ans = 0;
int orcolor = grid[row][col];
int m = grid.size();
int n = grid[0].size();
vector> bord;//用来储存联通量边界的坐标 两列 第一列是行坐标 第二列是列坐标
vector> visted(m, vector(n, false));//用来记录网格点是否被访问过 初始化为false表示没有被访问
dfs(grid, row, col, orcolor, bord, visted);//广搜结束之后得到连通分量的边界的坐标集合bord
for (int i = 0; i < bord.size(); i++) {
grid[bord[i][0]][bord[i][1]] = color;//对边界点进行着色
}
for(auto v:visted){
for(auto x:v){
std::cout<
130. 被围绕的区域
本题给定的矩阵中有三种元素：
字母 X；
被字母 X 包围的字母 O；
没有被字母 X 包围的字母 O。
本题要求将所有被字母 X 包围的字母 O都变为字母 X ，但很难判断哪些 O 是被包围的，哪些 O 不是被包围的。
注意到题目解释中提到：任何边界上的 O 都不会被填充为 X。 我们可以想到，所有的不被包围的 O 都直接或间接与边界上的 O 相连。我们可以利用这个性质判断 O 是否在边界上，具体地说：
对于每一个边界上的 O，我们以它为起点，标记所有与它直接或间接相连的字母 O；
最后我们遍历这个矩阵，对于每一个字母：
如果该字母被标记过，则该字母为没有被字母 X 包围的字母 O，我们将其还原为字母 O；
如果该字母没有被标记过，则该字母为被字母 X 包围的字母 O，我们将其修改为字母 X。自己的代码（不能全部通过）边界不改剩下的遇到O就改 没有考虑全面
class Solution {
public:
vector dx={-1,1,0,0};
vector dy={0,0,-1,1};
void dfs(vector>& board,int x,int y){
int m=board.size();
int n=board[0].size();
if(x==0||y==0||x==m-1||y==n-1) return ;//如果是边界 直接返回
board[x][y]='X';
for(int i=0;i<4;i++){
int mx=x+dx[i];
int my=x+dy[i];
if(mx>=0&&mx=0&&my>& board) {
int m=board.size();
int n=board[0].size();
for(int i=0;i
最后又重新写的代码
class Solution {
public:
vector dx={-1,1,0,0};
vector dy={0,0,-1,1};
void dfs(vector>& board,int x,int y){
int m=board.size();
int n=board[0].size();
if(x<0||x>=m||y<0||y>=n||board[x][y]!='O') return;
board[x][y]='A';//标记
// for(int i=0;i<4;i++){
// int mx=x+dx[i];
// int my=x+dy[i];
// dfs(board,mx,my);
// }为啥不能for循环？？？好像是广度搜索 我是大傻逼 my=x+dy[i];应该是y！！！
dfs(board,x-1,y);
dfs(board,x+1,y);
dfs(board,x,y-1);
dfs(board,x,y+1);
}
void solve(vector>& board) {
int m=board.size();
int n=board[0].size();
for(int j=0;j
102. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
class Solution {
public:
vector> levelOrder(TreeNode* root) {
queue que;//辅助队列
if (root != NULL) que.push(root);//首先放入根节点
vector> result;
vector path;
// result.push_back(que)
while(!que.empty()){//队列非空
int size=que.size();//一定要使用size进行遍历 因为遍历的过程中队列的长度会发生改变
for(int i=0;ival);
if(que.front()->left) que.push(que.front()->left);//左孩子存在则入队
if(que.front()->right) que.push(que.front()->right);//右孩子存在则入队
que.pop();//遍历之后弹出队首元素
}
result.push_back(path);//将每一层的结果放入result中
path.clear();
}
return result;
}
};
107. 二叉树的层序遍历 II
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
class Solution {
public:
vector> levelOrderBottom(TreeNode* root) {
queue que;
if (root != NULL) que.push(root);
vector> result;
while (!que.empty()) {
int size = que.size();
vector vec;
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
reverse(result.begin(),result.end());//唯一跟二叉树遍历不同的地方
return result;
}
};
103. 二叉树的锯齿形层序遍历
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
class Solution {
public:
vector> zigzagLevelOrder(TreeNode* root) {
queue q;
vector> result;
if(root) q.push(root);
int flag=1;//设置控制从左还是从右遍历的标志 默认是从左开始
while(!q.empty()){
int size=q.size();
vector path;
for(int i=0;ival);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
q.pop();
}
if(flag==1){//从左开始遍历
result.push_back(path);
flag=-1;//结束之后需要对flag进行改变 下一次则进行从右开始的遍历
}
else if(flag==-1){
reverse(path.begin(),path.end());//从右向左的遍历则需要对路径path进行翻转
result.push_back(path);
flag=1;//放入结果后将flag进行改变 下一次则从左向右遍历
}
}
return result;
}
};
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
class Solution {
public:
int minDepth(TreeNode *root) {
if (root == nullptr) {
return 0;
}
queue > que;
que.emplace(root, 1);
while (!que.empty()) {
TreeNode *node = que.front().first;
int depth = que.front().second;
que.pop();
if (node->left == nullptr && node->right == nullptr) {
return depth;
}
if (node->left != nullptr) {
que.emplace(node->left, depth + 1);
}
if (node->right != nullptr) {
que.emplace(node->right, depth + 1);
}
}
return 0;
}
};
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。（就是层序遍历结果的数组的行的数量）
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
class Solution {
public:
int maxDepth(TreeNode* root) {
queue que;
if (root != NULL) que.push(root);
vector> result;
while (!que.empty()) {
int size = que.size();
vector vec;
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result.size();
}
};
116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
class Solution {
public:
Node* connect(Node* root) {
queue que;
if (root != NULL) que.push(root);
vector> result;
while (!que.empty()) {
int size = que.size();
vector vec;
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
Node* node = que.front();
que.pop();
vec.push_back(node->val);
if (i < size - 1) {
node->next = que.front();
}//该部分就是添加next的语句 不是要弹出的元素的最后一个就要添加next 并且指向队首的元素
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return root;
}
};
117. 填充每个节点的下一个右侧节点指针 II
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
class Solution {
public:
void handle(Node* &last, Node* &p, Node* &nextStart) {
if (last) {
last->next = p;
}
if (!nextStart) {
nextStart = p;
}
last = p;
}
Node* connect(Node* root) {
if (!root) {
return nullptr;
}
Node *start = root;
while (start) {
Node *last = nullptr, *nextStart = nullptr;
for (Node *p = start; p != nullptr; p = p->next) {
if (p->left) {
handle(last, p->left, nextStart);
}
if (p->right) {
handle(last, p->right, nextStart);
}
}
start = nextStart;
}
return root;
}
};
199. 二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
class Solution {
public:
vector rightSideView(TreeNode* root) {
queue que;
if (root != NULL) que.push(root);
vector> result;
while (!que.empty()) {
int size = que.size();
vector vec;
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
vector res;
for(int i=0;i
