层次遍历、四个方向遍历更新-LeetCode 429、892、542
层次遍历、四个方向遍历更新-LeetCode 429、892、542
层次遍历：LeetCode #429 892 542
1
编程题
【LeetCode #429】N叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。(即从左到右，逐层遍历)。 例如，给定一个 3叉树 :
返回其层序遍历:
[ [1], [3,2,4], [5,6] ]
解题思路：
注意题目是N叉树的层序遍历，相比于二叉树的层序遍历，N叉树的一个节点会有多个子树，并使用vector储存。因此，在二叉树中需要判断左右节点，并将非空节点压入到队列中，而在N叉树需要循环判断vector中的节点是否为空，若非空，压入队列中！
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> res;
queue<Node*> que;
if(root == nullptr) return res;
que.push(root);
while(!que.empty()){
int size = que.size();
vector<int> vec;
while(size--){
Node* tmp = que.front();
que.pop();
vec.push_back(tmp->val);
for(auto child: tmp->children){
if(child != nullptr){
que.push(child);
}
}
}
res.push_back(vec);
}
return res;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
【LeetCode #892】三维形体的表面积
在 N * N 的网格上，我们放置一些 1 * 1 * 1 的立方体。 每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。 请你返回最终形体的表面积。
示例 1： 输入：[[2]] 输出：10 示例 2： 输入：[[1,2],[3,4]] 输出：34
解题思路：
这个题目今年的360笔试出现过，刚开始看不怎么好像，但实质就是一个遍历的过程，首先对于叠放数不为零的位置，直接计算每个叠放长方体的表面积，也就是4 * grid[i][j]+2. 这里面肯定重复了，因此需要去掉重复的面积！ 比如[6,4], 这两个长方体重复的面积为min(6,4)*2，因此我们从x轴和y轴开始遍历的去掉重复的面积。 注意程序中的条件判断！
class Solution {
public:
int surfaceArea(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int res = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] != 0){
res += grid[i][j] * 4 + 2;
}
if(i > 0){
res -= min(grid[i-1][j], grid[i][j]) * 2;
}
if(j > 0){
res -= min(grid[i][j-1], grid[i][j]) * 2;
}
}
}
return res;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/surface-area-of-3d-shapes
【LeetCode #542】0 1矩阵
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。
示例 2: 输入: 0 0 0 0 1 0 1 1 1 输出: 0 0 0 0 1 0 1 2 1
解题思路：
首先对这个0 1矩阵建立一个距离矩阵dist，值为0的位置对应dist中也为0，因为该元素与本身的距离为零，值为1的位置对应dist中则为INT_MAX-10000，也就代表整数最大值得意思，为什么要减去10000呢？这是由于距离更新时会进行加一操作，而题中元素总数不超过10000，为了防止数据溢出，因此减去10000. 接下来就很简单了，我们从四个方向上、下、左和右来更新每个位置的距离，由于矩阵中至少有一个零，因此INT_MAX-10000必定会更新成为别的值！从而得到我们的结果！ 还有一种BFS的方法，效率有些低，可以到官方题解查看！
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int rows = matrix.size();
if(rows == 0)
return matrix;
int cols = matrix[0].size();
vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX-10000));
// 从上，从左开始更新距离
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(matrix[i][j] == 0){
dist[i][j] = 0;
}else{
if(i > 0)
dist[i][j] = min(dist[i][j], dist[i-1][j] + 1);
if(j > 0)
dist[i][j] = min(dist[i][j], dist[i][j-1] + 1);
}
}
}
// 从下，从右开始更新距离
for (int i = rows - 1; i >= 0; i--) {
for (int j = cols - 1; j >= 0; j--) {
if (i < rows - 1)
dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1);
if (j < cols - 1)
dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1);
}
}
return dist;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/01-matrix/