力扣每日一题575

2021.11.01

575. 分糖果
     给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

示例 1:

输入: candies = [1,1,2,2,3,3]
输出: 3
解析: 一共有三种种类的糖果，每一种都有两个。
最优分配方案：妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。
示例 2 :

输入: candies = [1,1,2,3]
输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。
注意:

数组的长度为[2, 10,000]，并且确定为偶数。
数组中数字的大小在范围[-100,000, 100,000]内。

个人做法（我果然是个算法垃圾！）

class Solution2 {
    public static int distributeCandies(int[] candyType) {
        //能否被2除尽
        //int flag= (candyType.length%2==0? 1: -1);
        //if(flag>0){
            //记录妹妹获得的糖果种类
            ArrayList sister_candy = new ArrayList();
            for(int a:candyType){
                if(!sister_candy.contains(a)){
                    sister_candy.add(a);
                }
            }
            int a=(sister_candy.size()>(candyType.length/2)?candyType.length/2:sister_candy.size());
            return a;
            // }
       // return 0;
    }
    public static void main(String[] args) {
        int[] candyType={1,1,2,2,3,3};
        System.out.println(distributeCandies(candyType));
    }
}

接下来，接收官方爸爸的指（du）导(da)
(一)贪心算法
我的思路也是偏向贪心算法，但是官方完美的利用了HashSet的特性（它不允许集合中有重复的值），最后的Math.min利用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);
    }
}

优化
因为题目中提到数组的长度为[2, 10,000]。
可以对此进行进一步优化
限定

      Set<Integer> set = new HashSet<Integer>(100000);

所以，细节决定成败，今天的菜鸡依旧要努力呀！
(￢_￢叮:我说的是我自己，你，你，你别想太多！

以及剩下暴力解决法和排序法，学习链接如下：（瞎BB，官方大大要是不说，我都想不出这种方法= =||，大大也是够努力了，哈哈哈）
https://leetcode-cn.com/problems/distribute-candies/solution/fen-tang-guo-by-leetcode/

==================================================================
题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/distribute-candies
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。