当前位置: 首页 > 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…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...