美文网首页
1103.分糖果

1103.分糖果

作者: 等不了天明等时光 | 来源:发表于2020-03-17 12:49 被阅读0次

解题思路

解法一:暴力法

对小朋友们进行遍历,每次都发小朋友们应得数量的糖,直到剩下的糖不足以分发应得数量,就直接给最后那位倒霉孩子。

复杂度分析
时间复杂度:O(max(sqrt{G}, N)),G 为糖果数量,N 为人数。

本方法的时间复杂度取决于循环到底走多少步。设总的步数为 s,用等差数列求和公式可以求得 s 步时发放的糖果数量为 s(s+1)/2。那么只要 s^2+s≥2G 糖果就可以保证被发完。而只要当 s≥sqrt{2G}时,就有 s^2≥2G,显然也有 s^2+s≥2G。因此可知总的步数 s≤⌈sqr{2G}⌉,时间复杂度为 O(sqrt{G})。
另外建立糖果分配数组并初值赋值需要 O(N) 的时间,因此总的时间复杂度为O(max(sqrt{G},N))。

空间复杂度:O(1),除了答案数组只需要常数空间来存储若干变量。

解法二:数学法

代码

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 -= min(i+1, candies)
            # 轮数加1
            i += 1
        return kids

相关文章

  • 1103.分糖果

    解题思路 解法一:暴力法 对小朋友们进行遍历,每次都发小朋友们应得数量的糖,直到剩下的糖不足以分发应得数量,就直接...

  • LeetCode 1103. 分糖果

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

  • 1103.分糖果 II

    原题 https://leetcode-cn.com/problems/distribute-candies-to...

  • LeetCode 1103. 分糖果 II Distribute

    【题目描述】排排坐,分糖果。我们买了一些糖果 candies,打算把它们分给排好队的 n = num_people...

  • leetcode-1103-分糖果

    1103. 分糖果 II 方法1--直接遍历 思想:首先定义一个动态数组,把其中元素全部赋0。然后就是循环了,如果...

  • 2021-03-07 1103. 分糖果 II

    题目地址 https://leetcode-cn.com/problems/distribute-candies-...

  • 分糖果

    给定一个偶数长度的数组,其中不同的数字代表着不同种类的糖果,每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟...

  • 分糖果

    来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/distri...

  • NOIP训练营内部试题-分糖果

    NOIP训练营内部试题-分糖果 摘自:清北学堂NOIP训练营试题T2 题目:分糖果 分糖果 (candy) Tim...

  • 20221031 专业英语11

    1101. flat belt 平带 1102. chain drive 链传动 1103. idle chain...

网友评论

      本文标题:1103.分糖果

      本文链接:https://www.haomeiwen.com/subject/sbftyhtx.html