力扣575. 分糖果

2024-06-02 15:44

文章标签 力扣糖果 575

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

题目：

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

医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。

给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的最多种类数。

思路：

用一个集合visited记录哪些糖果种类吃过，遍历所有的糖果：当当前糖果种类不在visited中时，ans加一，并将该种类加入到visited中。当ans等于n/2时，或遍历完所有糖果时，结束循环。代码如下：

class Solution:def distributeCandies(self, candyType: List[int]) -> int:n = len(candyType)ans = 0index = 0    # 糖的索引visited = set()      # 集合记录已吃过的种类while ans < n/2 and index < n:itype = candyType[index]if itype not in visited:ans += 1visited.add(itype)index += 1return ans

提交通过：

优化：

从例子中可以发现规律：设一共有k种糖，糖的总数为n，若k>n/2，说明吃到的所有糖都是不同种类，答案为n/2；若k<n/2，说明吃到的糖里只有k种，答案为k。也就是说答案为min(k,n/2)。代码如下：

class Solution:def distributeCandies(self, candyType: List[int]) -> int:n = len(candyType)itype = set(candyType)   # 利用集合去掉重复种类k = len(itype)return min(k, int(n/2))

提交通过：