IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> Java&C++题解与拓展——leetcode883.三维形体投影面积【模拟么的新知识】 -> 正文阅读

[数据结构与算法]Java&C++题解与拓展——leetcode883.三维形体投影面积【模拟么的新知识】

每日一题做题记录,参考官方和三叶的题解

题目要求

image.png

思路:模拟

话不多说就是模拟……

遍历每一行每一列,求三视图的面积,然后相加:

  • 主视图(xz平面的投影):每一列(y轴方向)最高的会被投影,所以统计每一列内的最大高度;
  • 左视图(yz平面的投影):每一行(x轴方向)最高的会被投影;所以统计每一行内的最大高度;
  • 俯视图(xy平面的投影):当前格子里有块就会被投影,格子内块数不为零则结果加一。

因为网格长宽相等,所以遍历中不分行列,可在同一轮中同时统计行列最大值。具体的,xz中行不动
列变化求最大,yz中列不动行变化求最大。

Java

class Solution {
    public int projectionArea(int[][] grid) {
        int res = 0;
        int n = grid.length;
        for(int i = 0; i < n; i++) {
            int xz = 0, yz = 0;
            for(int j = 0; j < n; j++) {
                if(grid[i][j] > 0)
                    res++; // xy
                xz = Math.max(xz, grid[i][j]); // 当前行最大值
                yz = Math.max(yz, grid[j][i]); // 当前列最大值
            }
            res += xz + yz;
        }
        return res;
    }
}
  • 时间复杂度: O ( n 2 ) O(n^2) O(n2) n n n行(列)循环遍历套 n n n列(行)
  • 空间复杂度: O ( 1 ) O(1) O(1)

C++

和Java几乎一样……毕竟是考逻辑的简单题……

class Solution {
public:
    int projectionArea(vector<vector<int>>& grid) {
        int res = 0;
        int n = grid.size();
        for(int i = 0; i < n; i++) {
            int xz = 0, yz = 0;
            for(int j = 0; j < n; j++) {
                if(grid[i][j] > 0)
                    res++; // xy
                xz = max(xz, grid[i][j]); // 当前行最大值
                yz = max(yz, grid[j][i]); // 当前列最大值
            }
            res += xz + yz;
        }
        return res;
    }
};
  • 时间复杂度: O ( n 2 ) O(n^2) O(n2) n n n行(列)循环遍历套 n n n列(行)
  • 空间复杂度: O ( 1 ) O(1) O(1)

总结

模拟能有啥好总结的……

光速解决,去忙论文……


欢迎指正与讨论!
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-04-28 12:04:59  更:2022-04-28 12:08:38 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 6:28:31-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码