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

2517. 礼盒的最大甜蜜度(Maximum Tastiness of Candy Box)

2517. 礼盒的最大甜蜜度(Maximum Tastiness of Candy Box)

问题描述

给定一个正整数数组 price,其中 price[i] 表示第 i 类糖果的价格,另给定一个正整数 k。商店将 k 类不同糖果组合成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖果价格绝对差的最小值。

要求我们返回礼盒的最大甜蜜度。

示例

示例 1:

输入:

price = [13,5,1,8,21,2], k = 3

输出:

8

解释:
选出价格分别为 [13, 5, 21] 的三类糖果。礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8

示例 2:

输入:

price = [1,3,1], k = 2

输出:

2

解释:
选出价格分别为 [1, 3] 的两类糖果。礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2

示例 3:

输入:

price = [7,7,7,7], k = 2

输出:

0

解释:
从现有的糖果中任选两类糖果,甜蜜度都会是 0

解题思路

1. 问题分析

我们需要从 price 数组中选择 k 类糖果,这些糖果的甜蜜度是由它们的价格差决定的,而我们需要找到一种选择方法,使得最大甜蜜度尽可能大。

  • 甜蜜度的定义:礼盒中任意两种糖果价格的绝对差的最小值。
  • 目标:最大化礼盒的最小价格差。

2. 关键观察

  • 排序:price 数组排序后,糖果的价格差会变得更加规律。因为如果选择相邻的价格差,显然会更小。
  • 二分查找: 为了找到最大甜蜜度,我们可以用二分查找来试探不同的甜蜜度,逐渐逼近最优解。

3. 解法步骤

  • 排序: 首先对 price 数组进行排序,使得选择的糖果价格差最小。

  • 二分查找: 设定一个甜蜜度的范围,从 0price[-1] - price[0]。在此范围内进行二分查找,检查是否可以选出 k 类糖果,使得它们的最小价格差大于等于当前的 mid

  • 贪心选择: 对于每一个候选的甜蜜度 d,我们可以通过贪心算法来选择糖果。遍历价格数组,确保每个新选择的糖果价格与之前选择的糖果价格差不小于 d,如果满足条件,则继续选择糖果。

4. 代码实现

from typing import Listclass Solution:def maximumTastiness(self, price: List[int], k: int) -> int:# 辅助函数:判断是否可以选出至少 k 个糖果,且其最小价格差大于等于 ddef f(d: int) -> int:cnt = 1  # 选择第一个糖果pre = price[0]  # 上一个选择的糖果的价格for p in price:if p >= pre + d:  # 当前糖果价格与前一个糖果价格差 >= dcnt += 1pre = p  # 更新上一个选择的糖果return cntprice.sort()  # 对价格数组进行排序left = 0  # 二分查找的左边界right = (price[-1] - price[0]) // (k - 1) + 1  # 二分查找的右边界# 二分查找最大甜蜜度while left + 1 < right:mid = (left + right) // 2if f(mid) >= k:  # 如果可以选择 k 个糖果,返回 midleft = midelse:right = midreturn left

5. 时间复杂度

  • 排序操作的时间复杂度为 O(n log n),其中 nprice 数组的长度。
  • 二分查找的时间复杂度为 O(log(max_price - min_price))
  • 对每一个中间值 mid,我们需要遍历一次 price 数组,时间复杂度为 O(n)

因此,总的时间复杂度为 O(n log n + n log(max_price - min_price)),其中 n 是糖果数量,max_price - min_price 是糖果价格的范围。

6. 总结

本题通过对糖果价格数组排序,并利用二分查找和贪心策略来最大化糖果礼盒的甜蜜度。这个解法不仅高效,还能通过二分查找不断逼近最优解,从而找到最大的甜蜜度。

相关文章:

2517. 礼盒的最大甜蜜度(Maximum Tastiness of Candy Box)

2517. 礼盒的最大甜蜜度&#xff08;Maximum Tastiness of Candy Box&#xff09; 问题描述 给定一个正整数数组 price&#xff0c;其中 price[i] 表示第 i 类糖果的价格&#xff0c;另给定一个正整数 k。商店将 k 类不同糖果组合成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖…...

Golang 的字符编码与 regexp

前言 最近在使用 Golang 的 regexp 对网络流量做正则匹配时&#xff0c;发现有些情况无法正确进行匹配&#xff0c;找到资料发现 regexp 内部以 UTF-8 编码的方式来处理正则表达式&#xff0c;而网络流量是字节序列&#xff0c;由其中的非 UTF-8 字符造成的问题。 我们这里从 G…...

利用ollama 与deepseek r1大模型搭建本地知识库

1.安装运行ollama ollama下载 https://ollama.com/download/windows 验证ollama是否安装成功 ollama --version 访问ollama本地地址&#xff1a; http://localhost:11434/ 出现如下界面 ollama运行模型 ollama run llama3.2 ollama常用操作命令 启动 Ollama 服务&#xf…...

Java短信验证功能简单使用

注册登录阿里云官网&#xff1a;https://www.aliyun.com/ 搜索短信服务 自己一步步申请就可以了 开发文档&#xff1a; https://next.api.aliyun.com/api-tools/sdk/Dysmsapi?version2017-05-25&languagejava-tea&tabprimer-doc 1.引入依赖 <dependency>…...

CAS单点登录(第7版)21.可接受的使用政策

如有疑问&#xff0c;请看视频&#xff1a;CAS单点登录&#xff08;第7版&#xff09; 可接受的使用政策 概述 可接受的使用政策 CAS 也称为使用条款或 EULA&#xff0c;它允许用户在继续应用程序之前接受使用策略。此功能的生产级部署需要修改流&#xff0c;以便通过外部存…...

53倍性能提升!TiDB 全局索引如何优化分区表查询?

作者&#xff1a; Defined2014 原文来源&#xff1a; https://tidb.net/blog/7077577f 什么是 TiDB 全局索引 在 TiDB 中&#xff0c;全局索引是一种定义在分区表上的索引类型&#xff0c;它允许索引分区与表分区之间建立一对多的映射关系&#xff0c;即一个索引分区可以对…...

Pythong 解决Pycharm 运行太慢

Pythong 解决Pycharm 运行太慢 官方给Pycharm自身占用的最大内存设低估了限制,我的Pycharm刚开始默认是256mb。 首先找到自己的Pycharm安装目录 根据合适自己的改 保存&#xff0c;重启Pycharm...

库里存储的数据有大量回车时,该如何进行存取

如图&#xff0c;打印模板存了很多坐标性的字段数据&#xff1a; 大量带换行的文本数据存到库里之后取出&#xff0c;前端需要做非空、合法校验&#xff0c; 然后在循环中&#xff0c;使用eval 函数接收每一句字符串&#xff0c;去执行这句 JavaScript 代码。 let arrStr tem…...

【devops】Github Actions Secrets | 如何在Github中设置CI的Secret供CI的yaml使用

一、Github Actions 1、ci.yml name: CIon: [ push ]jobs:build:runs-on: ubuntu-lateststeps:- name: Checkout codeuses: actions/checkoutv3- name: Set up Gouses: actions/setup-gov4with:go-version: 1.23.0- name: Cache Go modulesuses: actions/cachev3with:path: |…...

体验 DeepSeek-R1:解密 1.5B、7B、8B 版本的强大性能与应用

文章目录 &#x1f34b;引言&#x1f34b;DeepSeek 模型简介&#x1f34b;版本更新&#xff1a;1.5B、7B、8B 的区别与特点&#x1f34b;模型评估&#x1f34b;体验 DeepSeek 的过程&#x1f34b;总结 &#x1f34b;引言 随着大规模语言模型的持续发展&#xff0c;许多模型在性…...

一文说清楚什么是Token以及项目中使用Token延伸的问题

首先可以参考我的往期文章&#xff0c;我这里说清楚了Cookie&#xff0c;Seesion&#xff0c;Token以及JWT是什么 其实Token你就可以理解成这是一个认证令牌就好了 详细分清Session&#xff0c;Cookie和Token之间的区别&#xff0c;以及JWT是什么东西_还分不清 cookie、sessi…...

大模型-Tool call、检索增强

大模型 Tool call 心知天气&#xff1a;https://www.seniverse.com/ 例子&#xff1a;调用天气接口 API from openai import OpenAI import requests import json """ ##### 天气接口 API 密钥获取&#xff1a;https://www.free-api.com/doc/558 ##### &quo…...

【算法】【区间和】acwing算法基础 802. 区间和 【有点复杂,但思路简单】

题目 假定有一个无限长的数轴&#xff0c;数轴上每个坐标上的数都是 0。 现在&#xff0c;我们首先进行 n 次操作&#xff0c;每次操作将某一位置 x 上的数加 c。 接下来&#xff0c;进行 m 次询问&#xff0c;每个询问包含两个整数 l 和 r&#xff0c;你需要求出在区间 [l,r] …...

Ubuntu22.04通过Docker部署Jeecgboot

程序发布环境包括docker、mysql、redis、maven、nodejs、npm等。 一、安装docker 1、用如下命令卸载旧Docker: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done 2、安装APT环境依赖包…...

HTML4

HTML 初体验 1.鼠标右键 > 新建 > 文本文档 > 输入以下内容&#xff0c;并保存 2.修改后缀为 .html &#xff0c;然后双击打开即可 这里的后缀名&#xff0c;使用 .htm 也可以&#xff0c;但推荐使用更标准的 .html <marquee>尚硅谷&#xff0c;让天下没有难…...

STM32F10X 启动文件完整分析

最近在准备面试相关 顺便复盘总结一下之前的内容 启动文件在基于ARM的芯片是很重要的组成部分&#xff0c;它主要负责完成芯片上电启动时的一系列初始化工作和各种异常及中断的入口地址。 也是理解bootloader自举的关键点&#xff0c;所以需要理解一下 1. 向量表定义 启动文件…...

typescript快速入门之安装与运行

安装 安装ts环境&#xff0c;最好全局安装&#xff0c;这样就不需要开一个项目又安装 npm i -g typescript初始化 可以运行初始化配置文件&#xff0c;也可以手动生成&#xff1b;不生成的话会运行默认配置 使用默认配置 把ts文件转成js文件使用的是es3语言&#xff0c;语…...

React源码解读

配置React源码本地调试环境 本次环境构建采用了node版本为16、react-scripts 版本号为 3.4.4&#xff0c;源码下载地址 react源码调试: react源码调试环境 使用 create-react-app 脚手架创建项目 npx create-react-app react-test 进入刚刚下载的目录&#xff0c;弹射 crea…...

【DeepSeek-R1】 API申请(火山方舟联网版)

DeepSeek-R1 API申请&#xff08;火山方舟联网版&#xff09; 1、新建联网版应用2、开通信息增强服务3、开启联网内容插件4、创建接入点5、获取模型名称6、获取API Key 如果第一次注册账号&#xff0c;请先按照文章《【Deepseek-R1】 API申请&#xff08;火山方舟&#xff09;》…...

负载均衡集群——LVS-DR配置

一、简介 1.1 什么是集群&#xff1f; 两台及以上的计算机完成一个任务的模式称为集群。 常见的集群类型包括&#xff1a; LB&#xff08;负载均衡&#xff09;集群&#xff1a;按照不同的算法将前端的访问转发给后端计算点&#xff0c;使节点负载相对平衡。提高并发能力 缺…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...