leetcode
leetcode 2501 ~ 2550
给小朋友们分糖果 I

给小朋友们分糖果 I

难度:

标签:

题目描述

You are given two positive integers n and limit.

Return the total number of ways to distribute n candies among 3 children such that no child gets more than limit candies.

 

Example 1:

Input: n = 5, limit = 2
Output: 3
Explanation: There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).

Example 2:

Input: n = 3, limit = 3
Output: 10
Explanation: There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) and (3, 0, 0).

 

Constraints:

  • 1 <= n <= 50
  • 1 <= limit <= 50

代码结果

运行时间: 22 ms, 内存: 15.9 MB


/*
 * Problem: Given two positive integers n and limit, you need to distribute n candies among 3 children such that no child receives more than limit candies. Return the total number of ways to do so.
 * 
 * Approach: Use Java Streams to generate all possible combinations of distributing candies to three children. Filter out the combinations where any child gets more than limit candies, and then count the valid combinations.
 */
import java.util.stream.IntStream;

public class CandyDistributionStream {
    public static int countWays(int n, int limit) {
        return (int) IntStream.rangeClosed(0, Math.min(n, limit))
                .boxed()
                .flatMap(i -> IntStream.rangeClosed(0, Math.min(n - i, limit))
                        .mapToObj(j -> new int[]{i, j, n - i - j}))
                .filter(arr -> arr[2] <= limit)
                .count();
    }

    public static void main(String[] args) {
        int n = 5;
        int limit = 2;
        System.out.println(countWays(n, limit)); // Output: 3
    }
}

解释

方法:

该题解使用了组合数学中的Stars and Bars定理来解决分糖果问题。Stars and Bars定理用于计算将n个相同的物体分配到k个不同的箱子中的方式数。在本题中,我们需要将n颗糖果分给3个小朋友,并满足每位小朋友的糖果数不超过limit。首先,计算不考虑限制的分配方法数,然后使用容斥原理(Inclusion-Exclusion Principle)来去除那些违反条件的分配情况。具体来说,先计算所有可能的分配方法数,再减去至少有一位小朋友得到超过limit颗糖果的情况,然后加上至少有两位小朋友得到超过limit的情况,最后减去所有三位小朋友都得到超过limit颗糖果的情况。

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在计算至少有一个小朋友得到超过limit颗糖果的情况时,使用的公式是`3 * C2(n + 2 - (limit + 1))`?这里的`3`和`(limit + 1)`是如何确定的?
在本题中,计算至少有一个小朋友得到超过limit颗糖果的情况时,`3`代表三种可能的情况——每一位小朋友可能是超过limit的那一位。`limit + 1`是因为我们要计算某个小朋友获得的糖果数超过limit,即至少是`limit + 1`颗。对于这样的情况,我们需要从总糖果数n中去除这个超过的部分(即`limit + 1`),然后计算剩余糖果的分配方式,这就是`n + 2 - (limit + 1)`中的`(limit + 1)`的由来。
🦆
Stars and Bars定理在这种有限制条件的情况下是如何应用的?请解释如何从无限制情况转化到有限制情况。
Stars and Bars定理通常用于计算将n个相同的物体分配到k个不同的箱子中的方式数。在无限制情况下,我们可以直接应用这个定理。但在有限制的情况下,如本题中每个小朋友获取的糖果数不能超过limit,我们需要使用容斥原理来调整计算方法。首先计算所有可能的分配方法(即无限制情况),然后逐步减去违反限制的情况(比如超过limit的情况),通过多次调整,最终得到满足所有条件的分配方法数。
🦆
在使用容斥原理计算时,如何确保`n + 2 - k * (limit + 1)`(其中k为1, 2, 3)的值非负,这对于解题有什么限制或影响?
在使用容斥原理时,必须确保`n + 2 - k * (limit + 1)`的值非负,因为负数情况下组合数没有意义。这就要求n必须足够大,至少大于等于`k * (limit + 1) - 2`。如果不满足这个条件,某些项就变得无效(即不能有负数的组合数)。这就对n提出了一个最小值的限制,确保所有计算项都有效,影响了算法的适用范围和正确性。
🦆
在题解中提到的`C2`函数是如何确保正确计算组合数的,特别是当输入的n小于2时?
`C2`函数设计用于计算从n个不同物体中选择两个的组合数,即C(n, 2)。函数中有一个条件检查,如果n小于2,则直接返回0,因为从少于2个元素中选择2个是不可能的。这种处理确保了函数在所有输入情况下都能返回正确的组合数,避免了对负数或不合逻辑值的计算,保证了函数的稳健性。

相关问题