【算法千题案例】每日一练LeetCode打卡——109.分糖果

【算法千题案例】每日一练LeetCode打卡——109.分糖果算法题打卡:分糖果。没有特别幸运,那么请先特别努力,别因为懒惰而失败,还矫情地将原因归于自己倒霉。所以说,树倒了,没有一片雪花是无辜的

请添加图片描述


📢前言

🚀 算法题 🚀
  • 🌲 每天打卡一道算法题,既是一个学习过程,又是一个分享的过程😜
  • 🌲 提示:本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
  • 🌲 要保持一个每天都在学习的状态,让我们一起努力成为算法大神吧🧐!
  • 🌲 今天是力扣算法题持续打卡第101天🎈!
🚀 算法题 🚀

🌲原题样例:分糖果

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

🌻C#方法:贪心

在这里插入图片描述

代码:

public class Solution { 
   
    public int DistributeCandies(int[] candyType) { 
   
        ISet<int> set = new HashSet<int>();
        foreach (int candy in candyType) { 
   
            set.Add(candy);
        }
        return Math.Min(set.Count, candyType.Length / 2);
    }
}

执行结果

通过
执行用时:248 ms,在所有 C# 提交中击败了69.14%的用户
内存消耗:62.9 MB,在所有 C# 提交中击败了75.70%的用户

🌻Java 方法:贪心

思路解析
在这里插入图片描述

代码:

class Solution { 
   
    public int distributeCandies(int[] candyType) { 
   
        Set<Integer> set = new HashSet<Integer>();
        for (int candy : candyType) { 
   
            set.add(candy);
        }
        return Math.min(set.size(), candyType.length / 2);
    }
}

执行结果

通过
执行用时:32 ms,在所有 Java  提交中击败了82.41%的用户
内存消耗:40.4 MB,在所有 Java 提交中击败了56.53%的用户

复杂度分析

时间复杂度:O( n )
空间复杂度:O(n) 

💬总结

  • 今天是力扣算法题打卡的第109天!
  • 文章采用 C#Java 两种编程语言进行解题
  • 一些方法也是参考力扣大神写的,也是边学习边分享,再次感谢算法大佬们
  • 那今天的算法题分享到此结束啦,明天再见!
    请添加图片描述

今天的文章【算法千题案例】每日一练LeetCode打卡——109.分糖果分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/33772.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注