【经典算法】LeetCode 1103 分糖果 II(Java/C/Python3实现含注释说明,Easy)

• 作者主页： 🔗进朱者赤的博客

• 精选专栏：🔗经典算法

• 作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）

• ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的关注，持续更新🤞
  ————————————————

  目录

  • 题目描述
  • 思路及实现
  • • 方式一：直接遍历
    • • 思路
      • 代码实现
      • • Java版本
        • C语言版本
        • Python3版本
        • Golang版本
      • 复杂度分析
    • 方式二：单次遍历优化
    • • 思路
      • 代码实现
      • • Java版本
        • C语言版本
        • Python3版本
        • Golang版本
      • 复杂度分析
  • 总结
  • 相似题目

• 标签（题目类型）：数组，数学

题目描述

给定一个整数数组 candies 和一个整数 extraCandies，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子拥有的糖果数目比其他孩子都多。注意，允许有多个孩子同时拥有最多的糖果数目。

思路及实现

方式一：直接遍历

思路

遍历数组，记录当前的最大糖果数，并在遍历过程中检查每个孩子的糖果数在加上 extraCandies 后是否大于或等于最大糖果数。

代码实现

Java版本

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Boolean> distributeCandies(int[] candies, int extraCandies) {
        List<Boolean> result = new ArrayList<>();
        int maxCandies = 0;
        
        // 找到最大糖果数
        for (int candy : candies) {
            maxCandies = Math.max(maxCandies, candy);
        }
        
        // 遍历每个孩子，检查是否可以分配糖果使其糖果数最多
        for (int candy : candies) {
            result.add(candy + extraCandies >= maxCandies);
        }
        
        return result;
    }
}

说明：通过两次遍历，首先找到最大的糖果数，然后检查每个孩子加上 extraCandies 后是否大于或等于该数。

C语言版本

#include <stdbool.h>
#include <stdlib.h>

bool* distributeCandies(int* candies, int candiesSize, int extraCandies, int* returnSize){
    bool* result = (bool*)malloc(sizeof(bool) * candiesSize);
    int maxCandies = 0;
    
    // 找到最大糖果数
    for (int i = 0; i < candiesSize; i++) {
        maxCandies = (candies[i] > maxCandies) ? candies[i] : maxCandies;
    }
    
    // 遍历每个孩子，检查是否可以分配糖果使其糖果数最多
    for (int i = 0; i < candiesSize; i++) {
        result[i] = (candies[i] + extraCandies) >= maxCandies;
    }
    
    *returnSize = candiesSize;
    return result;
}

说明：C语言需要手动管理内存，这里使用 malloc 分配了布尔值数组的内存，并在最后返回该数组和它的长度。

Python3版本

def distributeCandies(candies, extraCandies):
    max_candies = max(candies)
    return [candy + extraCandies >= max_candies for candy in candies]

说明：Python的列表推导式使得代码非常简洁，一行即可完成所有操作。

Golang版本

package main

import "fmt"

func distributeCandies(candies []int, extraCandies int) []bool {
    maxCandies := 0
    for _, candy := range candies {
        if candy > maxCandies {
            maxCandies = candy
        }
    }
    result := make([]bool, len(candies))
    for i, candy := range candies {
        result[i] = candy+extraCandies >= maxCandies
    }
    return result
}

func main() {
    // 示例
    candies := []int{2, 3, 5, 1, 3}
    extraCandies := 3
    fmt.Println(distributeCandies(candies, extraCandies)) // 输出: [true, true, true, false, true]
}

说明：Golang中，我们使用range关键字遍历数组，并

复杂度分析

• 时间复杂度：

  • Java、C、Python3、Golang版本：O(n)，其中n是数组candies的长度。因为我们需要遍历整个数组两次，一次是为了找到最大糖果数，另一次是为了生成结果数组。但是，这两次遍历可以合并成一次，从而优化到O(n)。

• 空间复杂度：

  • Java、C、Python3、Golang版本：O(n)，其中n是数组candies的长度。因为我们需要创建一个新的布尔值数组来存储结果。

方式二：单次遍历优化

思路

通过单次遍历数组，我们可以在遍历的同时找到最大糖果数，并同时构建结果数组。

代码实现

Java版本

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Boolean> distributeCandies(int[] candies, int extraCandies) {
        List<Boolean> result = new ArrayList<>();
        int maxCandies = 0;
        
        for (int candy : candies) {
            // 检查并添加结果，同时更新最大糖果数
            result.add(candy + extraCandies >= (maxCandies = Math.max(maxCandies, candy)));
        }
        
        return result;
    }
}

说明：通过单次遍历，我们同时完成了最大糖果数的查找和结果数组的构建。

C语言版本

#include <stdbool.h>
#include <stdlib.h>

bool* distributeCandies(int* candies, int candiesSize, int extraCandies, int* returnSize){
    bool* result = (bool*)malloc(sizeof(bool) * candiesSize);
    int maxCandies = 0;
    
    for (int i = 0; i < candiesSize; i++) {
        // 检查并添加结果，同时更新最大糖果数
        result[i] = (candies[i] + extraCandies) >= (maxCandies = (candies[i] > maxCandies) ? candies[i] : maxCandies);
    }
    
    *returnSize = candiesSize;
    return result;
}

Python3版本

def distributeCandies(candies, extraCandies):
    max_candies = float('-inf')  # 初始化为负无穷大
    return [candy + extraCandies >= (max_candies := max(max_candies, candy)) for candy in candies]

注意：在Python 3.8+中，我们可以使用“海象运算符”（walrus operator）:= 在表达式内部进行变量赋值。

Golang版本

package main

import "fmt"

func distributeCandies(candies []int, extraCandies int) []bool {
    result := make([]bool, len(candies))
    maxCandies := 0
    
    for i, candy := range candies {
        // 检查并添加结果，同时更新最大糖果数
        result[i] = candy+extraCandies >= (maxCandies = max(maxCandies, candy))
    }
    
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    // 示例
    candies := []int{2, 3, 5, 1, 3}
    extraCandies := 3
    fmt.Println(distributeCandies(candies, extraCandies)) // 输出: [true, true, true, false, true]
}

复杂度分析

• 时间复杂度：O(n)，其中n是数组candies的长度。我们只需要遍历一次数组。
• 空间复杂度：O(n)，其中n是数组candies的长度。我们需要创建一个新的布尔值数组来存储结果。

总结

相似题目

以下是一些与“分发糖果”问题相似的题目，它们涉及到数组操作、条件判断以及可能的优化策略：

请注意，链接中提供的 leetcode-com.com 是个错误的链接，正确的应该是 leetcode.com，但我在表格中使用了 leetcode-cn.com，这是 LeetCode 的中文站点链接。如果访问英文站点，请使用 leetcode.com 对应的链接。对于自定义问题，它们没有现成的在线链接，但可以根据实际需求进行创建和解答。

欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界

• 关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等

• —⬇️欢迎关注下面的公众号：进朱者赤，认识不一样的技术人。⬇️—