下载插件

难度: Easy

小扣打算给自己的 **VS code** 安装使用插件，初始状态下带宽每分钟可以完成 `1` 个插件的下载。假定每分钟选择以下两种策略之一: - 使用当前带宽下载插件 - 将带宽加倍（下载插件数量随之加倍）请返回小扣完成下载 `n` 个插件最少需要多少分钟。注意：实际的下载的插件数量可以超过 `n` 个 **示例 1：** >输入：`n = 2` > >输出：`2` > >解释： > 以下两个方案，都能实现 2 分钟内下载 2 个插件 >- 方案一：第一分钟带宽加倍，带宽可每分钟下载 2 个插件；第二分钟下载 2 个插件 >- 方案二：第一分钟下载 1 个插件，第二分钟下载 1 个插件 **示例 2：** >输入：`n = 4` > >输出：`3` > >解释： > 最少需要 3 分钟可完成 4 个插件的下载，以下是其中一种方案: > 第一分钟带宽加倍，带宽可每分钟下载 2 个插件; > 第二分钟下载 2 个插件; > 第三分钟下载 2 个插件。 **提示：** - `1 <= n <= 10^5`

Submission

运行时间: 20 ms

内存: 16.0 MB

class Solution:
    def leastMinutes(self, n: int) -> int:
        if n == 1:
            return 1
        m = n
        p = 0
        while True:
            m //= 2
            p += 1
            if m == 1 or m == 0:
                break
        t = 2**p
        return p + (n+t-1)//t

Explain

此题解采用了一种迭代方法来计算下载插件所需的最少分钟数。首先，当只需下载一个插件时，直接返回1分钟。对于需要下载多个插件的情况，题解通过不断将需要下载的插件数除以2并累计操作次数，以此确定直到带宽能够在一分钟内下载所有插件所需要的倍增操作次数。这一步是确定需要多少次带宽倍增才能在一分钟内完成下载。变量 'p' 记录带宽加倍次数，每次带宽加倍实际上是计算需要多少次将带宽加倍到可以在一分钟内下载足够的插件。然后通过计算 '2**p' 来确定加倍后的带宽大小。最后返回加倍操作次数加上下载所需分钟数，下载所需分钟数是通过向上取整计算得出，以确保所有插件都能在整数分钟内下载完成。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def leastMinutes(self, n: int) -> int:
        # 特殊情况，当只需要下载一个插件时
        if n == 1:
            return 1
        m = n  # m用于记录剩余需要下载的插件数
        p = 0  # p记录带宽倍增所需的步数
        # 通过不断地将插件数减半来计算达到所需带宽的倍增次数
        while True:
            m //= 2
            p += 1
            # 当剩余插件数为1或0时，退出循环
            if m == 1 or m == 0:
                break
        t = 2**p  # 计算加倍后的带宽大小
        # 返回带宽加倍操作的次数加上利用当前带宽完成下载的时间
        return p + (n + t - 1) // t

Explore

循环中的目标是计算必须的带宽倍增次数，以便在一分钟内下载所有插件。每次循环将插件数减半，直到插件数减至1或0时，这表示不需要进一步增加带宽就能在一分钟内完成下载。如果在插件数减到n的一半时停止，可能会忽略需要进一步加倍以确保一分钟内下载完成的情况。因此，将插件数减到1或0是确保已经计算了足够的带宽倍增，以便在最短时间内完成下载。

变量p是通过不断将插件数m减半直至1或0，计算需要多少次带宽倍增直到可以在一分钟内下载所有插件。实际上，p可以直接通过计算n的二进制表示中最高位的位数来确定，这是因为每次带宽加倍都相当于在二进制中向左移动一位。可以使用数学公式 `p = ceil(log2(n))` 来直接计算出带宽需要加倍的次数，这里的log2是以2为底的对数，ceil表示向上取整。

表达式 `(n + t - 1) // t` 是一个常用的数学技巧来实现向上取整除法。这里，n是插件总数，t是经过p次加倍后的带宽，即一分钟内可以下载的插件数。直接使用n // t只能得到向下取整的结果，即完整下载的分钟数，但不考虑最后不满t的插件。通过添加 (t - 1) 和使用整数除法 //，可以确保即使剩余不足t的插件也会计算为额外的一分钟，从而确保所有插件都能在整数分钟内下载完毕。