【C++刷题】力扣-#575-分糖果

题目描述

Alice 有 n 枚糖,其中第 i 枚糖的类型为 candyType[i]。根据医生的建议,Alice 需要减少糖分摄入,只吃她所有糖的 n/2 即可(n 是一个偶数)。Alice 非常喜欢这些糖,她希望在遵循医生建议的情况下,尽可能吃到最多不同种类的糖。
给你一个长度为 n 的整数数组 candyType,返回 Alice 在仅吃掉 n/2 枚糖的情况下,可以吃到糖的最多种类数。

示例

示例 1

输入:candyType = [1,1,2,2,3,3]
输出:3
解释:Alice 只能吃 6 / 2 = 3 枚糖,由于只有 3 种糖,她可以每种吃一枚。

示例 2

输入:candyType = [1,1,2,3]
输出:2
解释:Alice 只能吃 4 / 2 = 2 枚糖,不管她选择吃的种类是 [1,2][1,3] 还是 [2,3],她只能吃到两种不同类的糖。

示例 3

输入:candyType = [6,6,6,6]
输出:1
解释:Alice 只能吃 4 / 2 = 2 枚糖,尽管她能吃 2 枚,但只能吃到 1 种糖。

题解

  1. 统计糖果种类:使用一个 unordered_set(无序集合)来存储 candyType 数组中的所有不同糖果种类。由于集合中的元素是唯一的,这可以帮助我们快速统计出不同糖果的种类数。
  2. 计算糖果总数和种类数:获取 candyType 数组的总长度 totalCandies,以及通过集合 candySet 的大小得到不同糖果的种类数 maxTypes。
  3. 判断种类数与总数的关系:如果不同糖果的种类数 maxTypes 大于糖果总数的一半 totalCandies / 2,则意味着 Alice 无法吃到所有种类的糖果,因此将 maxTypes 设置为 totalCandies / 2。
  4. 返回结果:返回 Alice 可以吃到的糖果种类数 maxTypes。

代码实现

int distributeCandies(vector<int>& candyType) {unordered_set<int> candySet(candyType.begin(), candyType.end());int totalCandies = candyType.size();int maxTypes = candySet.size();if (maxTypes > totalCandies / 2) {maxTypes = totalCandies / 2;}return maxTypes;
}

复杂度分析

● 时间复杂度:O(n),其中 n 是数组 candyType 的长度。我们需要遍历一次数组来构建集合。
● 空间复杂度:O(k),其中 k 是糖果种类的数量。我们使用集合来存储所有不同的糖果种类。
这个算法的优势在于它直接使用集合来统计不同糖果的种类数,并通过简单的条件判断来确定 Alice 可以吃到的糖果种类数,从而高效地解决了问题。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于SSM学生竞赛模拟系统的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;公告信息管理&#xff0c;试题管理&#xff0c;论坛交流&#xff0c;试卷管理&#xff0c;系统管理 前台账号功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;公告…

pip使用

pip全称pip install package,是python第三方包sitepackage管理的工具&#xff0c;安装&#xff0c;卸载第三方包。安装python时可以选择安装pip&#xff0c;或自己安装pip 查看pip是否安装&#xff1a;pip --version 安装pip &#xff1a;pip python -m pip install --upgrade…

Netron:神经网络模型可视化工具指南【全网最详细】

目录 Netron初印象 Netron 功能是什么&#xff1f; Netron 的来源 支持的模型文件格式 如何使用 Netron 打开和查看模型文件&#xff1f; 要掌握哪些知识才能看懂模型结构&#xff1f; 模型结构解释 part1 part2 part3 part4 part5 各节点解释说明 起始和终止节点…

ComfyUI - ComfyUI 工作流中集成 SAM2 + GroundingDINO 处理图像与视频 教程

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/143359538 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 SAM2 与…

阿里云物联网的通信方式

阿里云物联网通信的两种方式&#xff0c;一个是物模型&#xff08;分为服务&#xff0c;事件&#xff0c;属性此篇文章只讲解物模型中的服务和属性用法&#xff09;&#xff0c;一个是自定义topic&#xff08;要另外设置数据流转&#xff09; 1.使用产品内的功能定义&#xff0…

mysql5.7.44 arm 源码编译安装

一、&#xff1a;下载源码&#xff1a;mysql官网&#xff1a;MySQL :: MySQL Downloads #####下载mysql安装包 &#xff1a; 网址&#xff1a;https://www.mysql.com/ 可在页面下载后上传或直接下载。 官网地址首页&#xff0c;拉到最底部&#xff0c;找到社区版本下载&#xf…

BatchNorm推理阶段和Conv合并

BatchNorm推理阶段和Conv合并 本文全文来自&#xff1a; https://www.cnblogs.com/xiaxuexiaoab/p/16422640.html。 只只作为自己的复习使用&#xff0c;不作他用。 BN层作用 批量归一化&#xff08;Batch Normalization&#xff0c;BN&#xff09;在深度学习中常放在卷积层之…

第二十章 Vue组件通信之父子通信

目录 一、引言 二、组件关系分类 三、组件通信的解决方案 3.1. 父子通信流程图 3.2. 父组件通过 props 将数据传递给子组件 3.2.1. 代码App.vue 3.2.2. 代码MySon.vue 3.3. 子组件利用 $emit 通知父组件修改更新 ​编辑3.3.1. 代码App.vue 3.3.2. 代码MySon.vue 3…

对话瀚荃:为何欧美拟统一采用USB-C充电接口?

【哔哥哔特导读】英国、美国等地都准备统一电气设备充电标准&#xff0c;USB-C接口为何成为业界首选?选择USB-C连接器&#xff0c;又有什么注意事项? 近期&#xff0c;有消息指出英国、美国等地均启动了关于电气设备充电标准的咨询活动&#xff0c;希望听取制造商、进口商、…

如何解决RabbitMQ消息的重复消费问题

什么情况下会导致消息的重复消费——在消费者还没成功发送自动确认机制时发生&#xff1a; 网络抖动消费者挂了 解决方案 每条消息设置一个唯一的标识id幂等方案&#xff1a;【Redis分布式锁、数据库锁&#xff08;悲观锁、乐观锁&#xff09;】 面试官&#xff1a;如何解决…

vue中el-table显示文本过长提示

1.el-table设置轻提示:show-overflow-tooltip“true“&#xff0c;改变轻提示宽度

Couldn‘t apply path mapping to the remote file.

Couldn’t apply path mapping to the remote file. /s6home2/zjw524/projects/seq2seq/code/deepnmtpycharm/deepNmt/code/deepNmtPycharm/deepNmt/model/Deep_NMT_Model.py can’t be found in project. You can continue debugging, but without the source. To fix that yo…

Tech Talk: 浅谈AI浪潮下的计算型存储SSD

引言 近年来&#xff0c;AI应用态势迅猛增加&#xff0c;对计算侧的算力和内存提出了更高的要求。GPU、HBM这些高性能高密计算部件和内存部件&#xff0c;在AI计算场景中作为必需品&#xff0c;成为市场热点。业界也在讨论能否把计算侧的业务卸载到存储侧&#xff0c;称为计算…

华为配置 之 STP

目录 简介&#xff1a; STP&#xff1a; RSTP: 如何改变根网桥&#xff1a; &#xff08;1&#xff09;改变优先级&#xff1a; &#xff08;2&#xff09;改变root: 各端口的状态&#xff1a; 总结&#xff1a; 简介&#xff1a; STP&#xff08;Spanning Tree Protoco…

大数据挖掘和数据挖掘有什么不一样?

一、数据挖掘&#xff1a; 数据挖掘&#xff08;Data Mining&#xff09;是指从大量的、不完全的、有噪声的、模糊的、随机的数据中&#xff0c;提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 数据挖掘的概念起源于 20 世纪 80 年代后期&#xff0c…

活动|2024 CodeFuse 「编码挑战季」活动已开启!欢迎报名参加

Hi~开发者们&#xff0c;1024 程序员节快乐&#xff0c;向你们致敬&#xff01; CodeFuse 开源一年多以来&#xff0c;受到众多开发者的欢迎。在 1024 程序员节之际&#xff0c;CodeFuse 发起「编码挑战季」活动&#xff0c;诚邀广大开发者们参与 muAgent、MFTCoder、ModelCach…

Linux上本地部署KubeSphere与cpolar实现远程管理和监控集群

文章目录 前言1. 部署KubeSphere2. 本地测试访问3. Linux 安装Cpolar4. 配置KubeSphere公网访问地址5. 公网远程访问KubeSphere6. 固定KubeSphere公网地址 前言 本文主要介绍如何在Linux CentOS搭建KubeSphere并结合Cpolar内网穿透工具&#xff0c;实现远程访问&#xff0c;根…

Chrome浏览器音/视频无法自动播放

背景&#xff1a;由于google的一些制度&#xff0c;我们在写html项目时会发现刷新页面时无法自动播放audio和video&#xff0c;即使你添加了autoplay属性也无济于事&#xff0c; 但是IE和Edge浏览器是可以自动播放的。 解决方案&#xff1a; 本人在网上搜寻了很多方法&#xf…

vue的路由的两种模式 hash与history 详细讲解

文章目录 1. Hash 模式工作原理优点缺点使用示例 2. History 模式工作原理优点缺点服务器配置示例使用示例 总结 Vue Router 是 Vue.js 的官方路由管理器&#xff0c;它支持多种路由模式&#xff0c;其中最常用的两种是 hash 模式和 history 模式。下面我们详细讲解这两种模式的…

什么是目标检测?

首先计算机视觉能够解决哪些问题&#xff1f;&#xff1f; 分类、检测、分割 首先以下面这幅图为例&#xff1a; 分类就是输入一张图像&#xff0c;算法能够告诉我们图像中有什么类别&#xff0c;比如说猫或者狗&#xff0c;而并不知道这个类别在图像中的位置&#xff0c;如…