阅读 1237

小白带你领略算法魅力之leetcode算法题——分糖果

作者:Horace
ps:本人新手小白一枚,如有错误,欢迎指出,敬请谅解!

简要介绍

相信大家小时候对 "排排坐,分果果" 这句话一定不陌生,分糖果也有分糖果的智慧,所以今天由我这个小白给大家带来一道leetcode上关于分糖果的算法题的解析。

题目描述

这道关于分糖果的题目在leetcode上的描述如下:

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

示例 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]内。

思路分析

刚开始拿到这道题的时候可能会觉得很懵逼,不知道要从哪里下手,心里想着:为什么妹妹不能多分一点(当然这只是开个玩笑!),还有具体的糖果种类和每个人分得的糖果种类是多少,对于这些都无从下手的感觉。

好了,言归正传,我们重新整理一下思路,一步一步的带大家通过一个小白的角度来解决这道题。

题目要求我们能求得妹妹能够分得的最大的糖果种类数,经过思考我们可以知道,解决这道题的时候我们首先需要知道总共的糖果种类数有多少,然后我们才可以进行下一个步骤。题目说弟弟和妹妹分得的糖果数目一样(这也是为什么题目要求糖果的数目是偶数个),这样的话弟弟和妹妹每个人分得的糖果数量就是糖果数组 candies 的长度的一半。

这样一来就很好理解这道题了,如果我们求得了糖果的种类数,只需要用糖果种类数去和每个人可以分得的糖果数量 candies.length/2 比较一下:

  • 如果糖果的种类数小于 candies.length/2 那我们就可以把这些种类的糖果每种都给妹妹分一个了,妹妹就拿到了最多种类数的糖果,这样就应该返回糖果的种类数,妹妹可以拿到的最大糖果种类数就是所有糖果里的种类数。
  • 如果糖果的种类数大于等于 candies.length/2 此时,由于妹妹只能拿到所有糖果的一半,而种类数大于等于了这个值,那么妹妹就可以拿到一半的糖果,并且这些糖果的种类都不相同,这样就应该返回 candies.length/2 妹妹可以拿到的最大糖果种类数就是妹妹可以分得的糖果的数量,也就是 candies.length/2

JS实现

经过上面的分析,我们的代码写起来就非常容易了,通过一个循环我们可以找到所有糖果里的种类数,这样我们就可以很直观的写出我们的第一版代码。

/**
 * @param {Array length even} candies 
 * @return {number} count
 */
var distributeCandies = (candies) => {
    let count = 0;
    let obj = {}; //对象字面量
    for(let item of candies) {
        if(!obj[item]) {
            obj[item] = 1;
            count++;
        }
    }
    if(count > candies.length/2) {
        return candies.length/2;
    }else {
        return count;
    }
}
复制代码

有了之前的分析,上面的代码应该不难看懂,这个时候我们就可以开始发散我们的思维了。求糖果的种类数,无非就是所有糖果中没有重复的那些部分,这样我们就联想到了数组的去重,只要我们对糖果数组 candies 进行一次去重,去重后的数组的长度就是糖果的种类,这样我们这道算法题的核心就变成了数组去重。上面的代码中使用了对象字面量来实现了简单的去重,接下来我们用另一种方法实现去重的功能:

var distributeCandies = (candies) => {
    let count = 0;
    let res = [];
    for(let i = 0, len = candies.length; i < len; i++) {
        let current = candies[i];
        if(res.indexOf(current) === -1)
            res.push(current);
    }
    count = res.length;
    return (count >= candies.length >> 1) ? candies.length >> 1 : count; //除法右移一位 乘法左移一位
};
复制代码

上面去重的方法参考了大神冴羽的这篇文章《JavaScript专题之数组去重》,有兴趣的小伙伴可以去看看。
还有没有让我们的代码更简洁一点的方式呢?当然有!这个时候我们应该思考:既然核心是去重,那有没有一种数据结构就是可以直接只能存储无重复的内容呢?实际中是有的,JS中提供了一种数组容器 Set 这个容器中只能存储非重复的值,这样我们就省略了去重的步骤,下面带大家看看。

const distributeCandies = (candies) => {
    // 去重 数据结构 数组容器 不重复
    const count = new Set(candies);
    // console.log(count.size);
    return Math.min(count.size, candies.length >> 1); // 数学对象
}
复制代码

上面最后的一个返回语句可能有些朋友就会有点疑惑,其实很简单,我们要将糖果的种类数 count 和 妹妹可以分得的糖果数 candies.length/2 进行比较,通过我们之前的分析我们可以得出结论:返回的数就是这两个数中更小的那一个,这就是上面return语句的由来。

Python 实现

本人目前对于Python还不是很了解,但是我尝试着用Python实现了一下这道题。

class Solution:
    def distributeCandies(self, candies: List[int]) -> int:
        return min(len(set(candies)), len(candies) >> 1)
复制代码

总结

这样一道分糖果的算法就算是解决了,接下来我们来回味一下解题步骤:

  1. 确定糖果的种类和弟弟妹妹能够分得的糖果数
  2. 将糖果的种类数和能分得的糖果数进行一个比较
  3. 返回种类数和分得糖果数中较小得那个

当然,后面利用 Set 这种数据结构来改进代码就是需要自己去进行挖掘了。

写在后面

本次代码没有附加去考虑算法的时间复杂度和空间复杂度,作者本人也是一个小白,目的是希望把自己的思路分享给更多的人,可以让更多人能够KO这道算法题,所以我尽量用更加直接的语言来形容描述这道题的解法,同时也希望能和大家多交流算法方面的问题。

如果你觉得这篇小白的算法解析对你一点点帮助,我想邀请大家给文章点个赞,让更多的人能看到这篇文章。也欢迎大家在评论区多和我交流,我也会不定期的发表算法解析的文章!

关注下面的标签,发现更多相似文章
评论