二叉树的宽搜
429、N叉树的层序遍历
题解
BFS核心思想
二叉树的宽搜一般都是借助队列来实现的，实现的原理为首先将根节点进行放入队列中，然后将根节点进行弹出的时候，将这个节点的孩子节点进行放入队列中，然后继续弹出队头的元素，弹出对头节点时，在将该节点的孩子节点进行入队操作，以此循环直至队列中没有元素位置。
第一层for循环用于进行处理层序遍历的每一层的元素加入数组tier中，第二层for循环（范围for）用于处理该节点的孩子节点，使孩子节点进行入队操作。
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root)
{
vector<vector<int>> ret;
//创建队列
queue<Node*> q;
if(root==nullptr)
{
return ret;
}
q.push(root);
while(q.size())
{
vector<int> tier;
int sz=q.size();
for(int i=0;i<sz;i++)
{
//拿出队列的头部元素
Node* n=q.front();
//将节点进行出队列
q.pop();
//统计本层的节点
tier.push_back(n->val);
//将出队列的节点的孩子节点节点进行入队列
for(auto&e:n->children)
{
if(e!=nullptr)
{
q.push(e);
}
}
}
ret.push_back(tier);
}
return ret;
}
};103、二叉树的锯齿形层序遍历
题解
这题就是在上一道题的思路下进行利用标记位进行偶数情况的处理，以及reverse函数的使用。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root)
{
vector<vector<int>> ret;
queue<TreeNode*> q;
if(root==nullptr)
{
return ret;
}
q.push(root);
int flog=1;
while(q.size())
{
int sz=q.size();
vector<int>tier;
for(int i=0;i<sz;i++)
{
TreeNode* node=q.front();
q.pop();
tier.push_back(node->val);
if(node->left!=nullptr)
{
q.push(node->left);
}
if(node->right!=nullptr)
{
q.push(node->right);
}
}
if(flog%2==0)
{
reverse(tier.begin(),tier.end());
}
flog++;
ret.push_back(tier);
}
return ret;
}
};优先级队列（堆）
1046、最后一块石头的重量
题解
解法一：通过优先级队列辅助（大根堆）
C++中的STL容器中的优先级队列（priority_queue），堆顶的元素就是最大值，将堆顶元素进行弹出，进行获取最大值和次大值，然后进行按照要求进行处理该数据，直至数组中最多剩余一个值为止。
要是用到小根堆，priority_queue<int,vector<int>,greater<int>> 需要这样进行定义声明
class Solution {
public:
int lastStoneWeight(vector<int>& stones)
{
priority_queue<int> heap;
for(int i=0;i<stones.size();i++)
{
heap.push(stones[i]);
}
while(heap.size()>1)
{
int a=heap.top();
heap.pop();
int b=heap.top();
heap.pop();
if(a>b)
{
heap.push(a-b);
}
}
return heap.size()==0?0:heap.top();
}
};解法二：直接在数组本身进行操作
直接在数组本身进行相关排序后，进行获取最大值和次大值，然后进行按照要求进行处理该数据，直至数组中最多剩余一个值为止。本质就是模拟实现堆的操作。
class Solution {
public:
int lastStoneWeight(vector<int>& stones)
{
while(stones.size()>1)
{
sort(stones.begin(),stones.end());
int a=stones[stones.size()-1];
stones.pop_back();
int b=stones[stones.size()-1];
stones.pop_back();
if(a>b)
{
stones.push_back(a-b);
}
}
return stones.size()==0?0:stones.front();
}
};703、数据流中的第K大元素
题解
这道题本质就是TopK问题， Top K问题就是从N个元素中进行选出最大的K个元素或者最小的K个元素，相对于暴力极大的优化了时间复杂度。
解决TopK问题的两种最优方法
- 堆--O（nlogK）
- 快速选择算法--O（n）
用堆来解决TopK问题的步骤
1、创建一个大小为K的堆（大堆或者小堆）
2、循环：
1、依次进堆
2、判断堆的大小是否超过K
怎么进行判断用大根堆还是小根堆，理由是什么？
进行筛选最大的K个元素的时候，使用小根堆，否则使用大根堆，留在堆中的K个元素就是我们想要得到的结果，根据具体情况可能需要排序后使用。
class KthLargest
{
public:
KthLargest(int k, vector<int>& nums)
{
_k=k;
for(auto&e:nums)
{
heap.push(e);
if(heap.size()>_k)
{
heap.pop();
}
}
}
int add(int val)
{
heap.push(val);
if(heap.size()>_k)
{
heap.pop();
}
return heap.top();
}
private:
priority_queue<int,vector<int>,greater<int>> heap;
int _k;
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest* obj = new KthLargest(k, nums);
* int param_1 = obj->add(val);
*/BFS解决 FloodFill 算法
FloodFill算法简介
FloodFill算法译为中文是洪水灌溉算法，本质就是用于查找性质相同的联通块，进行查找性质相同的连通块一般是以一个点的上下左右为基准进行查找，解决洪水灌溉问题既可以通过深度优先遍历（dfs) 进行解决也可以通过广度优先遍历（bfs）进行解决。
733、图像渲染
题解
洪水灌溉问题本质就是寻找性质相同的子块，性质相同的含义在这题中就是数组中存的元素相同的位置连成的块状区域。
通过BFS进行遍历查找这个块状区域，通过BFS进行遍历，需要通过队列进行辅助实现，首先进行记录需要进行处理的位置的原始值，判断该值是否需要进行更改，如果不需要进行更改即原始值和将要进行修改的值是相同的，他周围的值和他相同也不需要进行修改，直接进行返回该数组即可。
当进行记录数组该位置的值和将要进行修改的值不相同时，将该位置放入队列中，开始准备在上下左右四个方向进行BFS层序遍历，将队列中的元素进行出队列时，将这个位置周围的位置（上下左右）数组对应位置的值和该位置原始的值相等时，将符合条件的位置进行进队列，依次进行处理，直至该队列为空时即处理完成。
技巧处理
通过两个数组进行处理这个上下左右四种情况，不在需要进行手动遍历了。这真的是太妙了。
代码实现
class Solution
{
typedef pair<int,int> PII;
//超级妙--妙不可言
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
{
queue<PII> q;
//先进行标记需要被修改的像素值
int prev=image[sr][sc];
if(prev==color)
{
return image;
}
//将其实位置进行入队列
q.push({sr,sc});
while(q.size())
{
auto [a,b]=q.front();
q.pop();
image[a][b]=color;
//这个处理思路太牛了
for(int i=0;i<4;i++)
{
int x=a+dx[i];
int y=b+dy[i];
if(x>=0&&y>=0&&x<image.size()&&y<image[0].size()&&image[x][y]==prev)
{
q.push({x,y});
}
}
}
return image;
}
};200、岛屿的数量
题解
先通过两层循环进行将数组中所有的位置都进行遍历，如果该位置的结果是字符1，然后通过BFS算法进行该位置的上下左右进行遍历查询，为了防止重复查询的情况发生，一般有两个方案进行去重，一种方案是在原数组的基础上进行，将遍历过的数组中位置为字符1的直接进行更改成字符0；另一种方式是通过一个辅助数组来进行，在辅助数组中进行将处理过的位置进行标记成true。
class Solution
{
public:
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool temp[301][301]={false};
int numIslands(vector<vector<char>>& grid)
{
int ret=0;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]=='1'&&temp[i][j]==false)
{
ret++;
bfs(grid,i,j);
}
}
}
return ret;
}
void bfs(vector<vector<char>> grid,int i,int j)
{
queue<pair<int,int>> q;
q.push({i,j});
temp[i][j]=true;
while(q.size())
{
auto [a,b]=q.front();
q.pop();
for(int k=0;k<4;k++)
{
int x=a+dx[k];
int y=b+dy[k];
if(x>=0&&y>=0&&x<grid.size()&&y<grid[0].size()&&grid[x][y]=='1'&&temp[x][y]==false)
{
q.push({x,y});
temp[x][y]=true;
}
}
}
}
};695、岛屿的最大面积
题解
这道题其实和上一道题本质的思路都是一样的，上一道题进行求的是岛屿的数量问题，这道题进行求解的是最大面积，首先也是通过遍历循环进行找到岛屿的位置进行通过BFS进行遍历出该岛屿所有的土地并进行记录，为了防止土地的重复遍历通过辅助数组来进行记录该岛屿是否被遍历过，然后通过ret进行更新最大值即可。
class Solution
{
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool temp[51][51]={false};
public:
int maxAreaOfIsland(vector<vector<int>>& grid)
{
int ret=0;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]==1&&temp[i][j]==false)
{
ret=max(bfs(grid,i,j),ret);
}
}
}
return ret;
}
int bfs(vector<vector<int>> grid,int i,int j)
{
int count=0;
queue<pair<int,int>> q;
q.push({i,j});
temp[i][j]=true;
count++;
while(q.size())
{
auto [a,b]=q.front();
q.pop();
for(int k=0;k<4;k++)
{
int x=a+dx[k];
int y=b+dy[k];
if(x>=0&&y>=0&&x<grid.size()&&y<grid[0].size()&&grid[x][y]==1&&temp[x][y]==false)
{
q.push({x,y});
temp[x][y]=true;
count++;
}
}
}
return count;
}
};130、被围绕的区域
题解
class Solution
{
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
public:
void solve(vector<vector<char>>& board)
{
//先进行处理边缘的问题
for(int i=0;i<board[0].size();i++)
{
if(board[0][i]=='O')
{
bfs(board,0,i);
}
if(board[board.size()-1][i]=='O')
{
bfs(board,board.size()-1,i);
}
}
for(int j=0;j<board.size();j++)
{
if(board[j][0]=='O')
{
bfs(board,j,0);
}
if(board[j][board[0].size()-1]=='O')
{
bfs(board,j,board[0].size()-1);
}
}
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[0].size();j++)
{
if(board[i][j]=='.')
{
board[i][j]='O';
}
else if(board[i][j]=='O')
{
board[i][j]='X';
}
}
}
}
void bfs(vector<vector<char>>& board,int i,int j)
{
queue<pair<int,int>>q;
q.push({i,j});
board[i][j]='.';
while(q.size())
{
auto [a,b]=q.front();
q.pop();
for(int k=0;k<4;k++)
{
int x=a+dx[k];
int y=b+dy[k];
if(x>=0&&y>=0&&x<board.size()&&y<board[0].size()&&board[x][y]=='O')
{
q.push({x,y});
board[x][y]='.';
}
}
}
}
};BFS 解决最短路问题
BFS是如何解决最短路径问题的？
首先还是需要进行借助队列进行实现，将路径的其实位置进行入队列，然后将与A相连的所有路径节点进行入队列，然后进行一层一层的出队列，如果遇到相同的路径节点并且该路径节点已经在队列中了就无需在将该节点进行重复加入队列中，该节点在路径中代表曾经的某一条路已将到达了这个节点了，后来到达这个节点的路肯定不会是最近的，因此舍弃，不再将这个迟到的节点进行入队列的操作。通过上图我们就可以看出最后进行BFS遍历的层数就是最短路径的长度。
防止走重复的路的策略
之前我们通过BFS进行解决洪水基本都是在二维数组中进行解决问题的，使用的是一般是在数组本身或者通过辅助数组进行记录遍历过的位置防止进行重复遍历，这里的最短路径问题是使用的是哈希表进行记录的重复位置。
1926、迷宫中离入口最近的出口
class Solution
{
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool temp[101][101]={false};
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance)
{
int ret=0;
int x=entrance.front();
int y=entrance.back();
return bfs(maze,x,y);
}
int bfs(vector<vector<char>>& maze,int i,int j)
{
queue<pair<int,int>>q;
q.push({i,j});
temp[i][j]=true;
int count=0;
while(q.size())
{
count++;
int sz=q.size();
for(int m=0;m<sz;m++)
{
auto [a,b]=q.front();
q.pop();
for(int k=0;k<4;k++)
{
int x=a+dx[k];
int y=b+dy[k];
if(x>=0&&y>=0&&x<maze.size()&&y<maze[0].size()&&maze[x][y]=='.'&&temp[x][y]==false)
{
if(x==0||y==0||x==maze.size()-1||y==maze[0].size()-1)
{
return count;
}
q.push({x,y});
temp[x][y]=true;
}
}
}
}
return -1;
}
};BFS解决拓扑排序
拓扑排序的简介
有向无环图（DAG图）
什么是有向图
有向无环图就是如上图所示没有形成环状结构的有向图
AVO网：顶点活动图
这只是草稿还没来得及进行处理。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
{
//准备工作
int n=numCourses;
unordered_map<int,vector<int>> edges;
vector<int> in(n);
//建图
for(auto&e:prerequisites)
{
int a=e[0];
int b=e[1];
edges[b].push_back(a);
in[a]++;
}
//进行拓扑排序
queue<int> q;
//将所有入度为0的点加入队列中
for(int i=0;i<n;i++)
{
if(in[i]==0)
{
q.push(i);
}
}
//进行bfs
while(q.size())
{
int t=q.front();
q.pop();
for(int a:edges[t])
{
in[a]--;
if(in[a]==0)
{
q.push(a);
}
}
}
//判断是否有环
for(int i=0;i<n;i++)
{
if(in[i])
{
return false;
}
}
return true;
}
};