首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >BAT面试算法进阶(9)- 三维形体投影面积

BAT面试算法进阶(9)- 三维形体投影面积

作者头像
iOSSir
发布2023-03-19 11:59:26
2620
发布2023-03-19 11:59:26
举报

题目

N * N 的网格中,我们放置了一些与x,y,z 三轴对齐的 1 * 1 * 1 立方体。每个值 v = grid[i][j] 表示 v 个正方体叠放在单元格 (i, j) 上。现在,我们查看这些立方体在xy、yz 和 zx平面上的投影。

投影就像影子,将三维形体映射到一个二维平面上。在这里,从顶部、前面和侧面看立方体时,我们会看到“影子”。返回所有三个投影的总面积。

  • 例子
  • 输入: [[1,2],[3,4]]
  • 输出: 17
  • 解释: 这里的形状在3个轴对齐平面上的3个投影("阴影部分")
  • 提示:
  • 1<= grid.length = grid[0].length <=50
  • 0 <= grid[i][j] <=50

解决方案

算法思路

  • 从顶部看,由该形状生成的阴影将是网格中非零值的数目
  • 从侧面看,由该形状生成的阴影将是网格中每一行的最大值
  • 从前面看,由该形状生成的阴影将是网格中每一列中的最大值.
例如 [[1,2][3,4]]
  • 从顶部的阴影将为4,因为网格中有4个非零值
  • 侧面阴影为2+4,因为第一行的最大值为2,第二行的最大值为4
  • 前面阴影为3+4,因为第一列的最大值是3,第二列的最大值为4;

代码实现

C++ Code

Java Code

Python Code

复杂度分析

  • 时间复杂度:O(N^2),其中N是grid的长度
  • 空间复杂度:O(1)

学习建议

  • 结合案例图例分析题目
  • 结合代码分析计算逻辑

算法面试系列文章:

BAT面试算法进阶(1)--两数之和

BAT面试算法进阶(2)- 无重复字符的最长子串(暴力法)

BAT面试算法进阶(3)- 无重复字符的最长子串(滑动窗口法)

BAT面试算法进阶(4)- 无重复字符的最长子串(滑动法优化+ASCII码法)

BAT面试算法进阶(5)- BAT面试算法进阶(5)- 最长回文子串(方法一)

BAT面试算法进阶(6)- BAT面试算法进阶(6)-最长回文子串(方法二)

BAT面试算法进阶(7)- 反转整数

BAT面试算法进阶(8)- 删除排序数组中的重复项

BAT面试算法进阶(10)- 最长的斐波那契子序列的长度(暴力法)

BAT面试算法进阶(11)- 最长的斐波那契子序列的长度(动态规划法)

BAT面试算法进阶(12)- 环形链表(哈希表法)

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-02-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Python课后小剧场 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 解决方案
    • 算法思路
      • 例如 [[1,2][3,4]]
  • 代码实现
    • C++ Code
      • Java Code
        • Python Code
        • 复杂度分析
        • 学习建议
        相关产品与服务
        腾讯云代码分析
        腾讯云代码分析(内部代号CodeDog)是集众多代码分析工具的云原生、分布式、高性能的代码综合分析跟踪管理平台,其主要功能是持续跟踪分析代码,观测项目代码质量,支撑团队传承代码文化。
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档