排排坐，分糖果。

我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。

给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。

然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。

重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。

返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

 

示例 1：

输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

示例 2：

输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。

 

提示：

  • 1 <= candies <= 10^9

  • 1 <= num_people <= 1000

解题思路

方法一：暴力破解/线性扫描

暴力破解比较直观，通过逐步将糖果分发给每个小朋友，直到糖果分发完毕。这个方法的时间复杂度为 O(n)，其中 n 是糖果的数量。

方法二：等差数列/数学计算

利用等差数列的性质进行糖果分配，时间复杂度为 O(k)，其中 k 是需要分发的轮次数。

具体步骤如下：

  1. 计算可以完整分发的糖果数 candies_total = (1 + i) * i / 2。

  2. 如果 candies_total < candies，则继续下一轮次的分发。

  3. 每个人的位置，可以用 (i-1) % num_people 来计算。

  4. 剩余的糖果不足一个轮次时，将剩余糖果全部分配给当前的小朋友。

通过这样的方法可以极大地减少循环次数，提升效率量级。

补充完整代码：

from typing import List


class Solution:
    """
    分配糖果的解决方案类

    方法:
        - distributeCandies: 分发糖果的入口方法
        - Solution1: 暴力破解/线性扫描方式分发糖果
        - Solution2: 等差数列/数学计算方式分发糖果
    """

    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        """
        根据给定的糖果数量和人数，选择解决方案1进行分发。

        参数:
            candies (int): 总糖果数量
            num_people (int): 分发糖果的人数

        返回:
            List[int]: 每个人得到的糖果数量列表
        """
        return self.Solution1(candies=candies, num_people=num_people)  # 调用暴力破解方式分发糖果

    def Solution1(self, candies: int, num_people: int) -> List[int]:
        """
        使用暴力破解/线性扫描的方式分配糖果。

        参数:
            candies (int): 总糖果数量
            num_people (int): 分发糖果的人数

        返回:
            List[int]: 每个人得到的糖果数量列表
        """
        res = [0] * num_people  # 初始化结果列表，长度为num_people，所有元素初始值为0
        current_candy = 0  # 当前要分配的糖果数量
        person_index = 0  # 当前分配糖果的人的索引

        # 当还有糖果剩余时继续分发
        while candies > 0:
            current_candy += 1  # 当前轮次要分配的糖果数量
            # 分配糖果，如果剩余糖果不够当前要分配的数量，则只分配剩余的糖果
            res[person_index] += min(candies, current_candy)  # * if比min快4.5倍, 追求极致可以用if
            candies -= current_candy  # 扣除已经分配的糖果数量
            person_index = (person_index + 1) % num_people  # 移动到下一个人分配糖果

        return res  # 返回结果列表

    def Solution2(self, candies: int, num_people: int) -> List[int]:
        """
        使用等差数列/数学计算的方式分配糖果。

        参数:
            candies (int): 总糖果数量
            num_people (int): 分发糖果的人数

        返回:
            List[int]: 每个人得到的糖果数量列表
        """
        res = [0] * num_people  # 初始化结果列表，长度为num_people，所有元素初始值为0

        for i in range(1, candies):
            # 计算前i个数的和 (1 + i) * i / 2 是否小于 candies
            if (1 + i) * i / 2 < candies:
                # 如果小于，那么将当前的i个糖果分配给下一个人
                res[(i - 1) % num_people] += i
            else:
                # 如果超过糖果总数，则将剩余的糖果全部分配给当前的人
                res[(i - 1) % num_people] += int(candies - (1 + i) * i / 2 + i)
                break  # 糖果用完，退出循环

        return res  # 返回结果列表