LeetCode-575. 分糖果(Golang)

2023-10-25 01:50
文章标签 leetcode golang 糖果 575

本文主要是介绍LeetCode-575. 分糖果(Golang),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、前言

作者:bug菌
博客:CSDN、掘金、infoQ、51CTO等
简介:CSDN/阿里云/华为云/51CTO博客专家,博客之星Top30,掘金年度人气作者Top40,51CTO年度博主Top12,掘金/InfoQ/51CTO等社区优质创作者,全网粉丝合计10w+,硬核微信公众号「猿圈奇妙屋」,欢迎你的加入!免费领取简历模板/学习资料/大厂面试真题/职业规划等海量资料。

       哈喽,小伙伴们,我是bug菌呀👀。金三银四,又到了刷题月啦。所以不管你是准备跳槽还是在职,都一起行动起来,顺应这个时代月干点该干的事儿👣。所以,赶紧跟着bug菌的步伐卷起来吧⏰,变强从这一刻开始!➕🧈

       小伙伴们在批阅文章的过程中如果觉得文章对您有一丝丝帮助,还请别吝啬您手里的赞呀,大胆的把文章点亮👍吧,您的点赞三连(收藏⭐️+关注👨‍🎓+留言📃)就是对bug菌我创作道路上最好的鼓励与支持😘。时光不弃🏃🏻‍♀️,创作不停💕,加油☘️

🏆本文收录于《LeetCode每日一题》,专门攻坚算法提升带着你一块儿刷题。

二、题目描述

Alice 有 n 枚糖,其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长,所以前去拜访了一位医生。

医生建议 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 种糖。

提示:

  • n == candyType.length
  • 2 <= n <= 104
  • n 是一个偶数
  • -105 <= candyType[i] <= 105

三、思路分析

直接将所有众数找出,跟数组长度的一半比较,如果众数大于数组长度的一半,返回数组长度的一半;如果众数小于数组长度的一半,直接返回众数即可

四、算法实现

func distributeCandie(candies []int) int {m := make(map[int]int)for i := 0; i < len(candies); i++ {//目的是计算有多少种不同种类的糖果数(可以看成不同的众数)m[candies[i]]++}//如果众数大于长度的一半,则妹妹可以获得的最大糖果的种类数就是数组长度的一半if len(m) > len(candies)/2 {return len(candies) / 2}//如果众数小于map长度的一半,则最大糖果的种类数就是该map长度return len(m)
}

算法执行截图:

五、复杂度分析

时间复杂度:O(n),其中 nnn 是数组 candies 的长度。

空间复杂度:O(n)。哈希表需要 O(n) 的空间。

六、小结

其实这道题直接采用贪心算法即可破题。

七、往期推荐

  1. leetcode-9.回文数
  2. leetcode-1.两数之和
  3. leetcode-13.罗马数字转整数
  4. leetcode-14.最长公共前缀
  5. leetcode-20.有效的括号
  6. leetcode-21.合并两个有序链表
  7. leetcode-26. 删除有序数组中的重复项

        如果你还想要学习更多,小伙伴们大可关注bug菌专门为你们创建的专栏,带着你一块儿刷题《每日一题LeetCode》。

        一个人刷可能会觉得很累很难坚持,但是一群人刷就会觉得它是一件很有意义的事儿,互相督促互相鼓励,一起变强。

        我是bug菌,一名想走👣出大山改变命运的程序猿。接下来的路还很长,都等待着我们去突破、去挑战。来吧,小伙伴们,我们一起加油!未来皆可期,fighting!

这篇关于LeetCode-575. 分糖果(Golang)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/279228

相关文章

golang 日志log与logrus示例详解

《golang日志log与logrus示例详解》log是Go语言标准库中一个简单的日志库,本文给大家介绍golang日志log与logrus示例详解,感兴趣的朋友一起看看吧... 目录一、Go 标准库 log 详解1. 功能特点2. 常用函数3. 示例代码4. 优势和局限二、第三方库 logrus 详解1.

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Golang基于内存的键值存储缓存库go-cache

《Golang基于内存的键值存储缓存库go-cache》go-cache是一个内存中的key:valuestore/cache库,适用于单机应用程序,本文主要介绍了Golang基于内存的键值存储缓存库... 目录文档安装方法示例1示例2使用注意点优点缺点go-cache 和 Redis 缓存对比1)功能特性

Golang中map缩容的实现

《Golang中map缩容的实现》本文主要介绍了Go语言中map的扩缩容机制,包括grow和hashGrow方法的处理,具有一定的参考价值,感兴趣的可以了解一下... 目录基本分析带来的隐患为什么不支持缩容基本分析在 Go 底层源码 src/runtime/map.go 中,扩缩容的处理方法是 grow

golang获取prometheus数据(prometheus/client_golang包)

《golang获取prometheus数据(prometheus/client_golang包)》本文主要介绍了使用Go语言的prometheus/client_golang包来获取Prometheu... 目录1. 创建链接1.1 语法1.2 完整示例2. 简单查询2.1 语法2.2 完整示例3. 范围值

golang panic 函数用法示例详解

《golangpanic函数用法示例详解》在Go语言中,panic用于触发不可恢复的错误,终止函数执行并逐层向上触发defer,最终若未被recover捕获,程序会崩溃,recover用于在def... 目录1. panic 的作用2. 基本用法3. recover 的使用规则4. 错误处理建议5. 常见错

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

golang内存对齐的项目实践

《golang内存对齐的项目实践》本文主要介绍了golang内存对齐的项目实践,内存对齐不仅有助于提高内存访问效率,还确保了与硬件接口的兼容性,是Go语言编程中不可忽视的重要优化手段,下面就来介绍一下... 目录一、结构体中的字段顺序与内存对齐二、内存对齐的原理与规则三、调整结构体字段顺序优化内存对齐四、内

Golang操作DuckDB实战案例分享

《Golang操作DuckDB实战案例分享》DuckDB是一个嵌入式SQL数据库引擎,它与众所周知的SQLite非常相似,但它是为olap风格的工作负载设计的,DuckDB支持各种数据类型和SQL特性... 目录DuckDB的主要优点环境准备初始化表和数据查询单行或多行错误处理和事务完整代码最后总结Duck