难度: Easy
桌上有 n
堆力扣币,每堆的数量保存在数组 coins
中。我们每次可以选择任意一堆,拿走其中的一枚或者两枚,求拿完所有力扣币的最少次数。
示例 1:
输入:
[4,2,1]
输出:
4
解释:第一堆力扣币最少需要拿 2 次,第二堆最少需要拿 1 次,第三堆最少需要拿 1 次,总共 4 次即可拿完。
示例 2:
输入:
[2,3,10]
输出:
8
限制:
1 <= n <= 4
1 <= coins[i] <= 10
难度: Easy
桌上有 n
堆力扣币,每堆的数量保存在数组 coins
中。我们每次可以选择任意一堆,拿走其中的一枚或者两枚,求拿完所有力扣币的最少次数。
示例 1:
输入:
[4,2,1]
输出:
4
解释:第一堆力扣币最少需要拿 2 次,第二堆最少需要拿 1 次,第三堆最少需要拿 1 次,总共 4 次即可拿完。
示例 2:
输入:
[2,3,10]
输出:
8
限制:
1 <= n <= 4
1 <= coins[i] <= 10
运行时间: 19 ms
内存: 16.1 MB
class Solution: def minCount(self, coins: List[int]) -> int: i = 0 for c in coins: i += c//2 + c%2 return i
题解采用了直接的数学方法来解决问题。对于每堆硬币,我们可以每次最多拿走两枚,因此对于每堆的硬币数c,拿完需要的次数是c除以2的商加上c除以2的余数。商(c//2)表示完全以两枚为单位拿取时的次数,余数(c%2)处理剩下的不满两枚的情况(要么1要么0)。通过对所有硬币堆进行此操作并求和,可以得到总的最少次数。
时间复杂度: O(n)
空间复杂度: O(1)
# 解法类定义 class Solution: def minCount(self, coins: List[int]) -> int: i = 0 # 初始化计数器 for c in coins: # 遍历每堆硬币 i += c//2 + c%2 # 计算拿完这堆硬币所需的最少次数 return i # 返回总的最少次数
因为每次拿取的最大数量限制为两枚,这种策略是在这个限制下最优的。每堆硬币每次拿取两枚可以最大限度地减少拿取的次数。例如,对于任意给定的硬币数c,如果每次只拿一枚,那么需要拿c次,显然比每次尽可能拿两枚的次数(c//2 + c%2)要多。简单来说,每次拿两枚硬币,可以在同样的拿取次数内拿取更多的硬币,从而减少总次数。
实际上,`c//2 + c%2`可以简化为`(c + 1) // 2`。这是因为`c//2`计算的是c被2整除的部分,而`c%2`计算的是除以2后的余数(0或1)。当c为奇数时,`c%2`为1,表示还需要额外一次来拿走最后一枚硬币;当c为偶数时,`c%2`为0,不需要额外操作。因此,`c//2 + c%2`的结果与`(c + 1) // 2`相等,后者表示将c加1后再除以2,本质上处理了向上取整的问题,也就是确保每次拿取的是最大量的两枚硬币,以及最后可能剩下的一枚。两种方式计算结果相同,但`(c + 1) // 2`更简洁易懂。
这个问题的特定性质使得复杂的算法如动态规划或更复杂的贪心策略并不提供额外的优势。问题本质上要求最小化拿取次数,且每次拿取数量的上限为两枚。在这种情况下,每次尽可能拿两枚是最直接且有效的方法,这本身就是一种贪心策略。使用动态规划等更复杂的算法在这个特定问题中不会提供更好的解决方案,因为问题的约束和目标已经明确,且操作简单。因此,虽然算法的选择有限,但已足够解决问题,无需更复杂的策略。