2928.给小朋友们分糖果 I

【LetMeFly】2928.给小朋友们分糖果 I：Java提交的运行时间超过了61%的用户

力扣题目链接：https://leetcode.cn/problems/distribute-candies-among-children-i/

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

 

示例 1：

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2：

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(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) 和 (3, 0, 0) 。

 

提示：

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

解题方法：模拟

用$x$从$0$到$\min(limit, n)$模拟第一个小朋友，用$y$从$0$到$\min(limit, n-x)$模拟第二个小朋友，则第三个小朋友能分到$n-x-y$个。如果$n-x-y\leq limit$，则视为一种可行方案。

• 时间复杂度$O(n^2)$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int distributeCandies(int n, int limit) {
        int ans = 0;
        for (int x = 0; x <= n && x <= limit; x++) {
            for (int y = 0; y <= n - x && y <= limit; y++) {
                if (n - x - y <= limit) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

Go

// package main

func distributeCandies(n int, limit int) int {
    ans := 0
    for x := 0; x <= n && x <= limit; x++ {
        for y := 0; y <= n - x && y <= limit; y++ {
            if n - x - y <= limit {
                ans++
            }
        }
    }
    return ans
}

Java

class Solution {
    public int distributeCandies(int n, int limit) {
        int ans = 0;
        for (int x = 0; x <= n && x <= limit; x++) {
            for (int y = 0; y <= n - x && y <= limit; y++) {
                if (n - x - y <= limit) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

• 执行用时分布1 ms，击败61.78%使用Java的用户；
• 消耗内存分布40.03 MB，击败5.10%使用Java的用户。

Python

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        ans = 0
        for x in range(min(limit, n) + 1):
            for y in range(min(n - x, limit) + 1):
                if n - x - y <= limit:
                    ans += 1
        return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/139380754