【每日一题】切割后面积最大的蛋糕

文章目录

  • Tag
  • 题目来源
  • 题目解读
  • 解题思路
    • 方法一:排序
  • 其他语言
    • python3
  • 写在最后

Tag

【排序】【数组】【2023-10-27】


题目来源

1465. 切割后面积最大的蛋糕


题目解读

切割后面积最大的蛋糕。


解题思路

方法一:排序

本题较为简单,找出最大的宽和高,然后返回乘积即可。为了找出找出最大的宽和高,我们需要计算相邻两条切痕之间的距离(包括边界与最近的切痕之间的距离)。为了便于计算,可以对水平方向和竖直方向的切痕进行排序。具体实现见下方代码。

实现代码

class Solution {
public:
    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        const int MOD = 1e9 + 7;
        sort(verticalCuts.begin(), verticalCuts.end());
        sort(horizontalCuts.begin(), horizontalCuts.end());

        long long width = 0, heigh = 0, prev = 0;
        for (auto vert : verticalCuts) {
            width = max(width, vert - prev);
            prev = vert;
        }
        width = max(width, w - prev);

        prev = 0;
        for (auto hor : horizontalCuts) {
            heigh = max(heigh, hor - prev);
            prev = hor;
        }
        heigh = max(heigh, h - prev);

        long long res = (long long) width * heigh % MOD;
        return res;
    }
};

复杂度分析

时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn) n n n 为数组 horizontalCutsverticalCuts 的最大长度。

空间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)

其他语言

python3

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        width, heigh, prev = 0, 0, 0
        mod = 10 ** 9 + 7
        horizontalCuts.sort()
        verticalCuts.sort()

        for vert in verticalCuts:
            width = max(width, vert - prev)
            prev = vert
        width = max(width, w - prev)

        prev = 0
        for hor in horizontalCuts:
            heigh = max(heigh, hor - prev)
            prev = hor
        heigh = max(heigh, h - prev)

        res = width * heigh % mod
        return res

写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/105413.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Android加载SO包

一、前言 这几天用Android整合开源的RTMP推拉流都没成功&#xff0c;好几年没玩Android了碰到好多坑&#xff0c;在Android中为了效率难免需要调用C语言编写生成的SO文件&#xff0c;比如图片渲染加速&#xff0c;视频编解码等插件&#xff0c;今天我们就先聊一下在Android中如…

51单片机实验:数码管动态显示00-99

1、实验要求 利用STC89C52RC单片机开发板实现&#xff1a;使用2位数码管循环显示00-99&#xff0c;每次间隔1s&#xff0c;并且当计数到20时&#xff0c;则蜂鸣器鸣响1次。 2、实验分析 程序实现分析&#xff1a; 1、定义数码管位选引脚&#xff08;P2.4、P2.5、P2.6、…

ES6初步了解迭代器

迭代器是什么&#xff1f; 迭代器(iterator)是一种接口&#xff0c;为各种不同的数据结构提供统一的访问机制。任何数据结构只要部署 iterator 接口&#xff0c;就可以完成遍历操作 ES6创造了一种新的遍历方法for…of循环&#xff0c;iterator 接口主要供 for…of 使用 原生中具…

Android12之#pragma clang diagnostic ignored总结(一百六十八)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 人生格言&#xff1a; 人生…

pip 更换源

方案1 在C盘用户名录下新建pip文件夹&#xff0c;里面包含pip.ini文件 方案2 在C盘用户名目录的AppData的Roaming下新建pip文件夹&#xff0c;里面包含pip.ini文件。 内容为 [global] index-url https://pypi.tuna.tsinghua.edu.cn/simple

Git(四)底层命令:git对象、树对象、提交对象

目录 一、知识回顾1.1 Linux 基础命令1.2 .git 文件夹解析 二、git 对象&#xff08;数据对象&#xff09;2.1 hash-object 存储对象2.2 cat-file 查看对象 三、树对象3.1 ls-files 查看暂存区3.2 update-index 创建暂存区3.3 write-tree 生成树对象3.4 更新暂存区&#xff0c;…

ffmpeg的下载和编译(vs2022)

感谢大佬的二创,直接提供了sln编译 ffmpeg二创地址 创建如下目录 build存放代码(build最好改成source,因为作者这么建议,编译完才发现) msvc存放第三方依赖的头文件,这里固定叫msvc,因为大佬的sln里查找的路径是这个,不嫌麻烦也可以自己改 下载代码和编译器 下载源码…

[论文阅读]Point Density-Aware Voxels for LiDAR 3D Object Detection(PDV)

PDV Point Density-Aware Voxels for LiDAR 3D Object Detection 论文网址&#xff1a;PDV 论文代码&#xff1a;PDV 简读论文 摘要 LiDAR 已成为自动驾驶中主要的 3D 目标检测传感器之一。然而&#xff0c;激光雷达的发散点模式随着距离的增加而导致采样点云不均匀&#x…

层次式架构的设计理论与实践

层次式架构的设计理论与实践 层次式架构概述 层次式架构的定义和特性 定义 特性 层次式架构的一般组成(表现层、中间层、数据访问层和数据层) 表现层框架设计 设计模式 MVC MVP MVVM XML技术 UIP设计思想 表现层动态生成设计思想(基于XML界面管理技术) 中间层架构设计 业务…

Vue+ElementUI项目打包部署到Ubuntu服务器中

1、修改config/index.js中的assetsPublicPath: /,修改为assetsPublicPath: ./ assetsPublicPath: ./2、在build/utils.js中增加publicPath: ../../ publicPath: ../../3、打开终端&#xff0c;在根目录下执行npm run build进行打包&#xff0c;打包成功后会生成dist npm run…

cmake练习一

需求&#xff1a; 1、利用CGAL库Boost库&#xff0c;写一个关于CGAL的程序 2、使用cmake构建 1、创建目录结构 src中有一个main.cpp&#xff0c;放的是我们的主程序代码 2、安装CGAL和Boost库 略 3、编写cmakelist.txt cmake_minimum_required(VERSION 3.1.0) project(cg…

规则推理桌游

目录 Eleusis Express 1&#xff0c;规则 2&#xff0c;出牌规则示例 3&#xff0c;中文规则 Eleusis Express 原文&#xff1a;Eleusis Express 1&#xff0c;规则 简单来说就是需要一个主持人想一个出牌规则&#xff0c;其他人通过出牌试探过程推理出这个出牌规则。 …

甘特图组件DHTMLX Gantt用例 - 如何自定义任务、月标记和网格新外观

dhtmlxGantt是用于跨浏览器和跨平台应用程序的功能齐全的Gantt图表。可满足项目管理应用程序的所有需求&#xff0c;是最完善的甘特图图表库。 本文将为大家揭示DHTMLX Gantt自定义的典型用例&#xff0c;包括自定义任务、网格的新外观等&#xff0c;来展示其功能的强大性&…

电力物联网关智能通讯管理机-安科瑞黄安南

众所周知&#xff0c;网关应用于各种行业的终端设备的数据采集与数据分析&#xff0c;然后去实现设备的监测、控制、计算&#xff0c;为系统与设备之间建立通讯联系&#xff0c;达到双向的数据通讯。 网关可以实时监测并及时发现异常数据&#xff0c;同时自身根据用户规则进行…

[AutoSar NVM] 存储服务层(Service)详解

专栏 《深入浅出AutoSAR》。全文 3400 字&#xff0c; 依AutoSAR及公开知识辛苦整理&#xff0c;禁止转载。 接上一讲 [AutoSar NVM] 存储架构 "数据是新时代的石油" -- 克莱门特•M•杜森堡&#xff08;Clement M. Dusenbury&#xff09; 我们深入了解下存储服务层 …

国际腾讯云自主拼装直播 URL教程!!!

注意事项 创建转码模板 并与播放域名进行 绑定 后&#xff0c;转码配置后的直播流&#xff0c;需将播放地址的 StreamName 拼接为 StreamName_转码模板名称&#xff0c;更多详情请参见 播放配置。 前提条件 已注册腾讯云账号&#xff0c;并开通 腾讯云直播服务。 已在 域名…

python二次开发Solidworks:方程式驱动曲线

1、渐开线 import win32com.client as win32 import pythoncomswApp win32.Dispatch(sldworks.application) swApp.Visible True Nothing win32.VARIANT(pythoncom.VT_DISPATCH, None) swModel swApp.ActiveDoc swExt swModel.Extension swSelMgr swModel.SelectionManag…

竞赛 深度学习图像修复算法 - opencv python 机器视觉

文章目录 0 前言2 什么是图像内容填充修复3 原理分析3.1 第一步&#xff1a;将图像理解为一个概率分布的样本3.2 补全图像 3.3 快速生成假图像3.4 生成对抗网络(Generative Adversarial Net, GAN) 的架构3.5 使用G(z)生成伪图像 4 在Tensorflow上构建DCGANs最后 0 前言 &#…

Mysql在ubuntu22.04上安装配置

更新并下载Mysql sudo apt update sudo apt install mysql-server启动Mysql服务 sudo systemctl start mysql安全配置 包括设置密码、删除匿名用户、禁止远程root登录等&#xff0c;按提示进行即可。 sudo mysql_secure_installation是否设置密码&#xff1a;是 三种强度密…

Node.js中的单线程服务器

为了解决多线程服务器在高并发的I/O密集型应用中的不足&#xff0c;同时避免早期简单单线程服务器的性能障碍&#xff0c;Node.js采用了基于"事件循环"的非阻塞式单线程模型&#xff0c;实现了如下两个目标&#xff1a; &#xff08;1&#xff09;保证每个请求都可以…