👉引言
| 铭记于心 | ||
| 🎉✨🎉我唯一知道的，便是我一无所知🎉✨🎉 |
💖 ❄️我们的算法之路❄️💖
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs) ，💝宽度优先搜索（bfs） ，💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：宽度优先搜索
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
👉⭐️第一题💎
✨题目
✨思路：
最经典的二叉树按层遍历题目，通过一个队列即可实现，每遍历一个根节点，就将它的左右子节点都放进队列。值得注意的是由于本题要拿到每层的节点，需要标记层级，则需要一个flag跟踪子节点入队列的过程，当本层结束遍历后，flag会指向下一层末尾节点，到开始遍历下一层时，用F复制flag，用于表示本层节点结束的标志，及时更新vector
✨代码：
/** * 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>> levelOrder(TreeNode *root) { queue<TreeNode *> le; vector<vector<int>> res; le.push(root); if(!root)return res; TreeNode *flag = root,*F=root; vector<int> tem; while (!le.empty()) { TreeNode *child = le.front(); tem.push_back(child->val); le.pop(); if (child->left) { le.push(child->left); flag = child->left; } if (child->right) { le.push(child->right); flag = child->right; } if (F == child) { res.push_back(tem); tem.resize(0); F = flag; } } return res; } };
👉⭐️第二题💎
✨题目
✨思路：
问题，最短路径首先想到BFS，这里将time（分钟数）当做遍历的层数，先从第0层（将最初所有腐烂的果子放进队列）开始while
✨代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int orangesRotting(vector<vector<int>> &grid) { int flag[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; queue<vector<int>> q; int n = grid.size(), m = grid[0].size(); int count = 0, t = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 1) count++; else if (grid[i][j] == 2) q.push(vector<int>({i, j})); } } while (count && q.size()) { t++; int N = q.size(); for (int i = 0; i < N; i++) { vector<int> tem = q.front(); q.pop(); int r = tem[0], c = tem[1]; for (int t = 0; t < 4; t++) { int nr = r + flag[t][0], nc = c + flag[t][1]; if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 1) { grid[nr][nc] = 2; count--; q.push(vector<int>({nr, nc})); } } } } return count ? -1 : t; } };
👉⭐️第三题💎
✨题目
✨思路：
深度优先遍历，先递归右节点 让它在下一层先被处理，当res长度和step相等时 当前节点就是这一层的右节点，加入数组中；时间复杂度O(n)，每个节点遍历一次。空间复杂度O(n)，递归栈空间
✨代码：
class Solution { public List<Integer> rightSideView(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); List<Integer> ans = new ArrayList<>(); if(root == null){ return ans; } queue.offer(root); while (!queue.isEmpty()){ int size = queue.size(); while (size -- > 0){ TreeNode poll = queue.poll(); if(size == 0){ ans.add(poll.val); } if(poll.left != null){ queue.add(poll.left); } if(poll.right != null){ queue.add(poll.right); } } } return ans; } }
写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！
