层次遍历: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/