Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode笔记:575. Distribute Candies

LeetCode笔记:575. Distribute Candies

作者头像
Cloudox
发布于 2021-11-23 08:33:11
发布于 2021-11-23 08:33:11
25000
代码可运行
举报
文章被收录于专栏:月亮与二进制月亮与二进制
运行总次数:0
代码可运行

问题(Easy):

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain. Example 1: Input: candies = [1,1,2,2,3,3] Output: 3 Explanation: There are three different kinds of candies (1, 2 and 3), and two candies for each kind. Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too. The sister has three different kinds of candies. Example 2: Input: candies = [1,1,2,3] Output: 2 Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1]. The sister has two different kinds of candies, the brother has only one kind of candies. Note:

  1. The length of the given array is in range [2, 10,000], and will be even.
  2. The number in given array is in range [-100,000, 100,000].

大意:

给出一个偶数长度的证书数组,其中不同的数字表示不同类别的糖果。每个数字表示一个不同类别的糖果。你需要将这些糖果平均分给弟弟和妹妹。返回妹妹能得到的最大的糖果种类数。 例1: 输入:candies = [1,1,2,2,3,3] 输出:3 解释: 有三种糖果(1,2,3),每种类别有两个糖果。 可选的分布:妹妹得到糖果[1,2,3],弟弟也得到通过[1,2,3]。 妹妹得到了三种糖果。 例2: 输入:candies = [1,1,2,3] 输出:2 解释:比如,妹妹得到糖果[2,3],弟弟得到糖果[1,1]。 妹妹有两种糖果,而弟弟只有一种。 注意:

  1. 给出数组的长度在[2, 10000],会是偶数。
  2. 给出的数字的范围在[-100000, 100000]。

思路1:

其实就是看有多少个糖果种类,也就是多少个不同的数字,因为糖果一定是均分给两人的,如果种类数大于总数的一半,那妹妹能得到的最大种类数就是总数的一半。如果种类数小于总数的一半,那肯定最多能得到的就是种类数了。

需要注意的是题目并没说给出的数组是排了序的,所以不能直接遍历看种类,需要用一些集合来记录出现过的种类(数字),遇到出现过的就不再记录了,遍历一遍后得到总种类数,再跟总数的一半比大小就知道了。

代码1(C++):

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        int num = candies.size() / 2;
        int sort = 0;
        map<int, int> maps;
        auto iter = candies.begin();
        while (iter != candies.end()) {
            if (maps.find(*iter) == maps.end()) {
                sort++;
                maps.insert(pair<int, int>(*iter, 1));
            }
            iter++;
        }
        if (sort > num) return num;
        else return sort;
    }
};

其实用set会更加方便一点,不用判断是否出现过,直接放set里放,最后统计set里的元素数,set保证一样的只会留一个。且最后的比较可以用min函数。

代码1改进(C++):

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        unordered_set<int> kinds;
        for (int kind : candies) {
            kinds.insert(kind);
        }
        return min(kinds.size(), candies.size() / 2);
    }
};

思路2:

前面也说到了排序,如果先给集合排个序,那么就可以遍历集合来统计种类数了,只要遍历时跟前一个比较是否一样即可,这种方式因为要事先排序,时间复杂度会降低为排序的时间复杂度。

代码2(C++):

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        size_t kinds = 0;
        sort(candies.begin(), candies.end());
        for (int i = 0; i < candies.size(); i++) {
            kinds += i == 0 || candies[i] != candies[i - 1];
        }
        return min(kinds, candies.size() / 2);
    }
};

合集:https://github.com/Cloudox/LeetCode-Record


本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018/1/3 上午,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
Leetcode-Easy 575. Distribute Candies
728. Self Dividing Numbers 描述: 有偶数个糖,需要分给弟弟和妹妹,要求最终两个人分到的糖数目一样,返回妹妹获得糖的种类数目最大值 思路: 如果糖的种类数小于
致Great
2018/04/11
5920
Leetcode-Easy  575. Distribute Candies
天池在线编程 2020国庆八天乐 - 8. 分糖果
https://tianchi.aliyun.com/oj/118289365933779217/122647324212270016 描述: 给定长度为偶数的整数数组,该数组中不同的数字代表不同种类的糖果, 每个数字表示一种糖果。 您需要将这些糖果平均分配给弟弟和妹妹。 返回妹妹可以获得的糖果种类的最大数量。
Michael阿明
2021/02/19
2100
​LeetCode刷题实战575:分糖果
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2022/04/12
2590
leetcode-575-Distribute Candies(计算一个数组中元素的种类的快速方法)
题目描述: Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister.
chenjx85
2018/05/22
5770
Golang Leetcode 575. Distribute Candies.go
当糖果的种类数目大于妹妹应分得的糖果数目时,妹妹所能分得的最大糖果种类数为妹妹应分得的糖果数,反之,则为糖果的种类数。
anakinsun
2019/04/22
3210
【leetcode刷题】T51-分糖果
Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.
木又AI帮
2019/07/17
5470
575. 分糖果
数组的长度为[2, 10,000],并且确定为偶数。 数组中数字的大小在范围[-100,000, 100,000]内。
编程张无忌
2021/06/10
2990
三分钟看完「分糖果」算法问题
给定一个偶数长度的数组,其中不同的数字代表着不同种类的糖果,每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
五分钟学算法
2019/05/15
9150
LeetCode Weekly Contest 31解题思路
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/71204570
用户1147447
2019/05/26
3860
LeetCode 575. 分糖果(set集合去重)
给定一个偶数长度的数组,其中不同的数字代表着不同种类的糖果,每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
Michael阿明
2020/07/13
3750
LeetCode 575. 分糖果(set集合去重)
575. 分糖果
给定一个偶数长度的数组,其中不同的数字代表着不同种类的糖果,每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
lucifer210
2019/09/10
3860
575. 分糖果
LeetCode 第 25 场双周赛(718/1832,前39.2%)
全国排名:718 / 1832,39.2%;全球排名:2951 / 7699,38.3%
Michael阿明
2020/07/13
3870
LeetCode 第 25 场双周赛(718/1832,前39.2%)
力扣题目汇总(二进制表示中质素个数,分糖果,有序数组平方)
给定两个整数 L 和 R ,找到闭区间 [L, R] 范围内,计算置位位数为质数的整数个数。
小小咸鱼YwY
2019/07/24
4460
LeetCode笔记:Weekly Contest 287
这一题的思路其实也是比较直接的,分两步走就行了,首先求出时间差,然后用贪心算法获取变换所需的最小操作数即可。
codename_cys
2022/04/13
1750
LeetCode-575. 分糖果(Golang)
Alice 有 n 枚糖,其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长,所以前去拜访了一位医生。
bug菌
2023/08/24
1290
LeetCode-575. 分糖果(Golang)
Leetcode - 剑指offer 面试题29:数组中出现次数超过一半的数字及其变形(腾讯2015秋招 编程题4)
剑指offer 面试题29:数组中出现次数超过一半的数字 提交网址: http://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163
Enjoy233
2019/03/05
6510
Leetcode 575. Distribute Candies
文章作者:Tyan 博客:noahsnail.com  |  CSDN  |  简书
Tyan
2022/08/11
2110
Leetcode 575. Distribute Candies
力扣题目汇总(位1的个数,有效的字母异位词,检测大写字母)
否则,我们定义这个单词没有正确使用大写字母。 示例 1: 输入: "USA" 输出: True 示例 2: 输入: "FlaG" 输出: False 注意: 输入是由大写和小写拉丁字母组成的非空单词。
小小咸鱼YwY
2019/07/24
5070
【算法千题案例】每日一练LeetCode打卡——109.分糖果
Alice 有n 枚糖,其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长,所以前去拜访了一位医生。
呆呆敲代码的小Y
2022/01/25
3360
【算法千题案例】每日一练LeetCode打卡——109.分糖果
【Leetcode -575.分糖果 -594.最长和谐子序列】
题目:Alice 有 n 枚糖,其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长,所以前去拜访了一位医生。
YoungMLet
2024/03/01
920
相关推荐
Leetcode-Easy 575. Distribute Candies
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验