首页 > 编程语言 >Java LeetCode练习

Java LeetCode练习

时间:2024-09-02 22:50:31浏览次数:13  
标签:Java 天际线 int 高度 练习 矩阵 grid 建筑物 LeetCode

        LeetCodeExercise

        807. 保持城市天际线

        题解:贪心

        从左侧和右侧看,城市天际线等于矩阵 grid 的每一行的建筑物高度最大值;从顶部和底部看,城市天际线等于矩阵 grid 的每一列的建筑物高度最大值。只要不改变每一行和每一列的建筑物高度最大值,就能保持城市天际线,因此可以使用贪心的思想计算建筑物高度可以增加的最大总和。

        由于矩阵 grid 的行数和列数都是 n,因此创建两个长度为 n 的数组 rowMax 和 colMax 分别记录矩阵 grid 的每一行的最大值和每一列的最大值。遍历矩阵 grid 填入两个数组之后,再次遍历矩阵,计算每个建筑物高度可以增加的最大值。

        当 0≤i,j<n 时,对于第 i 行第 j 列的建筑物,其所在行的建筑物高度最大值是 rowMax[i],其所在列的建筑物高度最大值是 colMax[j]。为了保持城市天际线,该建筑物增加后的高度不能超过其所在行和所在列的建筑物高度最大值,即该建筑物增加后的最大高度是 min(rowMax[i],colMax[j])。由于该建筑物的原始高度是 grid[i][j],因此该建筑物高度可以增加的最大值是 min(rowMax[i],colMax[j])−grid[i][j]。

        对于矩阵 grid 中的每个元素计算可以增加的最大值,即可得到建筑物高度可以增加的最大总和。

package JavaExercise20240902;

public class LeetCodeExercise {
    public static void main(String[] args) {
        // 需求
        // 给你一座由 n x n 个街区组成的城市,每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ,
        // 其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。
        // 城市的 天际线 是从远处观察城市时,所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 天际线 可能不同。
        // 我们被允许为 任意数量的建筑物 的高度增加 任意增量(不同建筑物的增量可能不同) 。
        // 高度为 0 的建筑物的高度也可以增加。然而,增加的建筑物高度 不能影响 从任何主要方向观察城市得到的 天际线 。
        // 在 不改变 从任何主要方向观测到的城市 天际线 的前提下,返回建筑物可以增加的 最大高度增量总和 。
        int[][] grid = {{3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3}, {0, 3, 1, 0}};
        Solution solution = new Solution();
        System.out.println(solution.maxIncreaseKeepingSkyline(grid));
    }
}

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length;
        int[] rowMax = new int[n];
        int[] colMax = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rowMax[i] = Math.max(rowMax[i], grid[i][j]);
                colMax[j] = Math.max(colMax[j], grid[i][j]);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans += Math.min(rowMax[i], colMax[j]) - grid[i][j];
            }
        }
        return ans;
    }
}

标签:Java,天际线,int,高度,练习,矩阵,grid,建筑物,LeetCode
From: https://blog.csdn.net/Aishangyuwen/article/details/141832464

相关文章

  • 「Java跳槽面试必备」2024年09月最新八股文
    【前言】网上各种面试八股文太多太多,但我今年找了好几个都是很久很久以前的老面试题,老文档了,和我出去面试市场上面试官问的问题基本上不一样了,可以说被打了一个措手不及,浪费了好几个机会,回来又找了好一些资料,以及结合自己最近的面试情况总结了一些心得免费分享给大家!虽然只有几本......
  • Java学习案例:控制台实现电影院管理系统
    文章目录@[TOC](文章目录)前言一、实现效果1、登录界面以及注册功能演示2、普通用户登录(1)热映影片(2)即将上映(3)个人信息(4)票夹3、管理员登录(1)电影管理(2)用户管理(3)个人信息二、功能源码1、接收用户的合法输入2、控制台格式化输出3、创建工具类4、多个类之间数据传递三......
  • 《JavaEE进阶》----9.<SpringMVC实践项目:【简易对话留言板(数据存在数据库中)】>
    本篇博客讲解设计的一个网页版简易对话留言板。这个是将数据存在数据库中。我们通过链接本地数据库。在这里面存入的数据。此时数据存在在硬盘中,只要数据不被删除,硬盘不损坏。那么这些数据就会被永久保存引入的依赖:配置数据库:spring:datasource:#数据库连接配置......
  • Java表达式与语句
    文章目录Java表达式和语句1.变量2.运算符与表达式3.语句Java表达式和语句1.变量变量及作用域局部变量在一个方法或由一对{}表示的代码块内定义的变量称为局部变量,有时也称为自动变量、临时变量或堆栈变量。局部变量的作用域是所在的方法或代码块,当程序执行流......
  • Java 面向对象编程的四个基本原则(封装、继承、多态和抽象),并给出一个简单的例子说明如
    面向对象编程(OOP)是一种编程范式,它使用“对象”来设计软件。在Java中,面向对象编程的四个基本原则是封装、继承、多态和抽象。每个原则都有其特定的目标,帮助开发者构建更加模块化、可维护和可扩展的代码。封装封装是指将数据(属性)和行为(方法)捆绑在一起,并隐藏对象的具体实现细......
  • Java 面试题:事务隔离级别以及并行事务会出现什么问题&&怎么解决脏读、不可重复读和幻
    文章目录四种事务隔离级别MySQL中设置事务隔离级别四种事务隔离级别在并行事务中可能会遇到的问题脏读、不可重复读和幻读三者区别事务的隔离级别是怎么解决这三个问题的?ReadView是什么ReadView包含的信息ReadView在MVCC中的工作原理工作流程总结事务的隔......
  • 探索Groovy的Elvis操作符及其在Java中的替代方案
    在编程的世界里,我们经常需要处理变量的默认值问题,尤其是在变量可能为null的情况下。Groovy语言提供了一种优雅的方式来处理这种情况,那就是Elvis操作符。本文将探讨Elvis操作符的用法,并展示如何在Java中实现类似的功能。Elvis操作符简介Elvis操作符(?:)是Groovy语言中的一种......
  • 解耦利器 - Java中的SPI机制
    为什么需要SPI机制SPI和API的区别是什么SPI是一种跟API相对应的反向设计思想:API由实现方确定标准规范和功能,调用方无权做任何干预;而SPI是由调用方确定标准规范,也就是接口,然后调用方依赖此接口,第三方实现此接口,这样做就可以方便的进行扩展,类似于插件机制,这是SPI出现的需求背景。......
  • 解耦利器 - Java中的SPI机制
    为什么需要SPI机制SPI和API的区别是什么SPI是一种跟API相对应的反向设计思想:API由实现方确定标准规范和功能,调用方无权做任何干预;而SPI是由调用方确定标准规范,也就是接口,然后调用方依赖此接口,第三方实现此接口,这样做就可以方便的进行扩展,类似于插件机制,这是SPI出现的需求背景。......
  • JAVA 内部类与Lambda
    JAVA内部类与Lambda目录JAVA内部类与Lambda1内部类1.1内部类基础1.2私有成员内部类1.3静态内部类1.4局部内部类1.5匿名内部类2Lambda表达式2.1初识Lambda2.1.1无参无返回值抽象方法2.1.2Lambda有参无返回值抽象方法2.1.3Lambda无参有返回值抽象方法2.1.4有参有......