当前位置: 首页 > news >正文

LeetCode:3218. 切蛋糕的最小总开销 I(贪心 Java)

目录

3218. 切蛋糕的最小总开销 I

题目描述:

实现代码与解析:

贪心

原理思路:


3218. 切蛋糕的最小总开销 I

题目描述:

        有一个 m x n 大小的矩形蛋糕,需要切成 1 x 1 的小块。

给你整数 m ,n 和两个数组:

  • horizontalCut 的大小为 m - 1 ,其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。
  • verticalCut 的大小为 n - 1 ,其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。

一次操作中,你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一:

  1. 沿着水平线 i 切开蛋糕,开销为 horizontalCut[i] 。
  2. 沿着垂直线 j 切开蛋糕,开销为 verticalCut[j] 。

每次操作后,这块蛋糕都被切成两个独立的小蛋糕。

每次操作的开销都为最开始对应切割线的开销,并且不会改变。

请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。

示例 1:

输入:m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

输出:13

解释:

  • 沿着垂直线 0 切开蛋糕,开销为 5 。
  • 沿着水平线 0 切开 3 x 1 的蛋糕块,开销为 1 。
  • 沿着水平线 0 切开 3 x 1 的蛋糕块,开销为 1 。
  • 沿着水平线 1 切开 2 x 1 的蛋糕块,开销为 3 。
  • 沿着水平线 1 切开 2 x 1 的蛋糕块,开销为 3 。

总开销为 5 + 1 + 1 + 3 + 3 = 13 。

示例 2:

输入:m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

输出:15

解释:

  • 沿着水平线 0 切开蛋糕,开销为 7 。
  • 沿着垂直线 0 切开 1 x 2 的蛋糕块,开销为 4 。
  • 沿着垂直线 0 切开 1 x 2 的蛋糕块,开销为 4 。

总开销为 7 + 4 + 4 = 15 。

提示:

  • 1 <= m, n <= 20
  • horizontalCut.length == m - 1
  • verticalCut.length == n - 1
  • 1 <= horizontalCut[i], verticalCut[i] <= 103

实现代码与解析:

贪心

import java.util.Arrays;class Solution {public int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {Arrays.sort(horizontalCut);Arrays.sort(verticalCut);int rs = m - 2, cs = n - 2;int cntR = 1; // 本次横向需要切的次数int cntC = 1; // 本次纵向需要切的次数int res=  0;while (rs >= 0 || cs >= 0) {if ( cs < 0 || (rs >= 0 && horizontalCut[rs] > verticalCut[cs])) { // 横向切res += horizontalCut[rs--] * cntC;cntR++;} else if (rs < 0 || (cs >= 0 && horizontalCut[rs] <= verticalCut[cs])) { // 纵向切res += verticalCut[cs--] * cntR;cntC++;}}return res;}
}

原理思路:

        因为无论如何每块的行与列都需要被切,所以每行和列开销最大的需要切的块数越少那么总开销就越少,所以每次切到时候选行和列中开销最大的行切即可。

相关文章:

LeetCode:3218. 切蛋糕的最小总开销 I(贪心 Java)

目录 3218. 切蛋糕的最小总开销 I 题目描述&#xff1a; 实现代码与解析&#xff1a; 贪心 原理思路&#xff1a; 3218. 切蛋糕的最小总开销 I 题目描述&#xff1a; 有一个 m x n 大小的矩形蛋糕&#xff0c;需要切成 1 x 1 的小块。 给你整数 m &#xff0c;n 和两个数…...

前端下载后端文件流,文件可以下载,但是打不开,显示“文件已损坏”的问题分析与解决方案

目录 场景还原 相关代码开发者工具 - 网络请求记录 问题排查 定位改bug 总结 场景还原 我在前端使用axios接收后端xlsx表格文件流并下载&#xff0c;xlsx文件能够下载成功&#xff0c;但是打开却显示文件无法打开 相关代码 请求API封装:Content–Type以及responseType经核…...

PageRank Web页面分级算法 HNUST【数据分析技术】(2025)

1.理论知识 算法原理PageRank 通过网络浩瀚的超链接关系来确定一个页面的等级。 Google 把从 A 页面到 B 页面的链接解释为A页面给B页面投票&#xff0c; Google 根据投票来源&#xff08;甚至来源的来源&#xff0c; 即链接到A页面的页面&#xff09;和投票目标的等级来决定新…...

数字IC前端学习笔记:脉动阵列的设计方法学(四)

相关阅读 数字IC前端https://blog.csdn.net/weixin_45791458/category_12173698.html?spm1001.2014.3001.5482 引言 脉动结构&#xff08;也称为脉动阵列&#xff09;表示一种有节奏地计算并通过系统传输数据的处理单元(PEs)网络。这些处理单元有规律地泵入泵出数据以保持规则…...

对话 Project Astra 研究主管:打造通用 AI 助理,主动视频交互和全双工对话是未来重点

Project Astra 愿景之一&#xff1a;「系统不仅能在你说话时做出回应&#xff0c;还能在持续的过程中帮助你。」 近期&#xff0c;Google DeepMind 的 YouTube 频道采访了 Google DeepMind 研究主管格雷格韦恩 (Greg Wayne)。 格雷格韦恩的研究工作为 DeepMind 的诸多突破性成…...

NetApp 存储设备巡检作业指导书

NetApp 存储设备巡检作业指导书 一、目的 本指导书旨在指导管理员通过 SSH 或 Console 登录 NetApp FAS2552 存储系统&#xff0c;切换节点并进行日常管理操作。 二、适用范围 适用于基于 NetApp ONTAP 操作系统的 FAS2552 存储环境。 三、前提条件 网络和权限要求&#xff1…...

adb无法连接到安卓设备【解决方案】报错:adb server version (40) doesn‘t match this client (41);

下载老版本Platformtools​​​​​​​​​​​​​​https://dl.google.com/android/repository/platform-tools_r28.0.2-windows.zip?hlzh-cn 替换原来的platform-tools文件夹即可。 问题原因分析&#xff1a;电脑端adb client版本&#xff08;41&#xff09;和安卓端adb …...

每天五分钟机器学习:核函数

本文重点 在学习支持向量机算法之前,我们要继续学习一些数学基础,本文我们将学习核函数的概念。当数据线性不可分的时候,此时就需要核函数出场了,它可以将低维不可分的数据映射到高维可分数据,此时就可以完成数据分类了。 核函数的定义 核函数K(x, y)定义为两个数据点x…...

Word窗体联动Excel实现级联组合框

在Word中的使用用户窗体&#xff08;UserForm&#xff09;定制界面如下图所示&#xff0c;其中控件如下&#xff08;忽略Label控件&#xff09;&#xff1a; CompanyName 组合框Attention 组合框CommandButton1 按钮 现在需要实现级联组合框效果&#xff0c;即用户在 CompanyN…...

RAG实战:构建基于本地大模型的智能问答系统

RAG实战&#xff1a;构建基于本地大模型的智能问答系统 引言 在当今AI快速发展的时代&#xff0c;如何构建一个既智能又可靠的问答系统是一个重要课题。本文将介绍如何使用RAG&#xff08;检索增强生成&#xff09;技术&#xff0c;结合本地大模型&#xff0c;构建一个高效的智…...

Docker 部署 plumelog 最新版本 实现日志采集

1.配置plumelog.yml version: 3 services:plumelog:#此镜像是基于plumelog-3.5.3版本image: registry.cn-hangzhou.aliyuncs.com/k8s-xiyan/plumelog:3.5.3container_name: plumelogports:- "8891:8891"environment:plumelog.model: redisplumelog.queue.redis.redi…...

TCP/IP 邮件

TCP/IP邮件是互联网通信中非常重要的应用之一。当我们发送电子邮件时&#xff0c;我们实际上并没有直接使用TCP/IP协议&#xff0c;而是通过电子邮件程序&#xff0c;例如微软的Outlook、莲花软件的Notes或Netscape Communicator等来实现。这些电子邮件程序背后使用了不同的TCP…...

FreeSql

官网 实体特性 Ado 它包括所有对 SQL 操作的封装&#xff0c;提供 ExecuteReader、ExecuteDataSet、ExecuteDataTable、ExecuteNonQuery、ExecuteScalar 等方法&#xff0c;使用起来和传统 SqlHelper 一样。 1、安装包 Install-Package FreeSql Install-Package FreeSql.Prov…...

记一次前端Vue项目国际化解决方案

背景 有一个vue项目&#xff0c;要实现国际化功能&#xff0c;能够切换中英文显示&#xff0c;因为该项目系统的用户包括了国内和国外用户。 需求 1、页面表单上的所有中文标签要国际化&#xff0c;包括表单属性标签、表格列头标签等&#xff0c; title“数量”&#xff1b;…...

JS进阶-手写Promise

一、什么是Promise 在Promise A规范中规定&#xff0c;Promise是一个有一个符合规范的then方法的对象或者函数。 1.关于then then接收onFulfilled和onRejected两个可选参数&#xff1b;then必须返回一个新的Promise对象&#xff1b;如果onFulfilled是一个函数 在状态切换为f…...

PCL点云库入门——PCL库点云滤波算法之直通滤波(PassThrough)和条件滤波(ConditionalRemoval)

0、滤波算法概述 PCL点云库中的滤波算法是处理点云数据不可或缺的一部分&#xff0c;它们能够有效地去除噪声、提取特征或进行数据降维。例如&#xff0c;使用体素网格滤波&#xff08;VoxelGrid&#xff09;可以减少点云数据量&#xff0c;同时保留重要的形状特征。此外&#…...

ioctl回顾

一、ioctl协议的命令组成 cmd本质为一个32位的数字&#xff0c;共分为四段&#xff1a; [31-30]:读写方向dir&#xff0c;分为无数据(_IO)、读数据(_IOR)、写数据(_IOW)、读写数据(_IOWR)四种模式&#xff1b; [29-16]:传递数据的大小size&#xff0c;一般利用其宏_IO、_IOR…...

jquery-validate在前端数据校验中的应用以及remote异步调用实践-以若依为例

目录 前言 一、关于Jquery Validate组件 1、validate是什么 2、内置验证方式及触发方式 3、自定义验证规则 二、基本验证实战以及Remote验证 1、基本验证实现 2、remote校验方式 三、总结 前言 随着技术的不断演进&#xff0c;在我们的日常开发过程中&#xff0c;大家一…...

如何重新设置VSCode的密钥环密码?

故障现象&#xff1a; 忘记了Vscode的这个密码&#xff1a; Enter password to unlock An application wants access to the keyring “Default ke... Password: The unlock password was incorrect Cancel Unlock 解决办法&#xff1a; 1.任意terminal下&#xff0c;输入如下…...

Android--java实现手机亮度控制

文章目录 1、开发需求2、运行环境3、主要文件4、布局文件信息5、手机界面控制代码6、debug 1、开发需求 需求&#xff1a;开发一个Android apk实现手机亮度控制 2、运行环境 Android studio最新版本 3、主要文件 app\src\main\AndroidManifest.xml app\src\main\res\layou…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...