1103. 分糖果 II

image.png
image.png

方法1--直接遍历

思想：首先定义一个动态数组，把其中元素全部赋0。然后就是循环了，如果循环到最后一个数组元素，那么我们把下标再变为第一个数组元素下标，这样就可以一直循环下去了，。最后，我们再把仅剩下的少量没分完的糖果分给循环结束后那个数组元素就行了。

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        alist = [0]*num_people
        count = 1
        while candies>0:
            for i in range(num_people):
                if candies > count:
                    alist[i] += count
                    candies -= count
                    count += 1
                else:
                    alist[i] += candies
                    candies = 0
                    break
        return alist

方法2--代码精进

这个i%num_people就很棒，随着i的增长，i对num_people进行取余数返回的数会一直是相应小朋友的正确下标

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        # 给小朋友们每人发个碗，用于装糖
        kids = [0] * num_people
        # 初始化第一轮
        i = 0

        # 只要糖还有，咱就继续发
        while candies > 0:
            # 这个i%num_people就很棒，随着i的增长，i对num_people进行取余数
            # 返回的数会一直是相应小朋友的正确下标
            # 用+=进行累加每一轮的新发的糖果
            # min的作用是，如果有一天糖不够了，就把那些最后剩余的糖给最后那个孩子
            kids[i % num_people] += min(i + 1, candies)
            
            # 手中糖的数量要记得减去每次发糖的数量
            candies -= i - 1
            # 这个小朋友发完了，下一位
            i += 1
        return kids

时间复杂度O(N)O(N)，一个简单的while循环
空间复杂度O(N)O(N)，因为建立了一个长度为len(num_people)的kids列表