本文最后更新于 383 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
桌上有 n
堆力扣币,每堆的数量保存在数组 coins
中。我们每次可以选择任意一堆,拿走其中的一枚或者两枚,求拿完所有力扣币的最少次数。
示例 1:
输入:
[4,2,1]
输出:
4
解释:第一堆力扣币最少需要拿 2 次,第二堆最少需要拿 1 次,第三堆最少需要拿 1 次,总共 4 次即可拿完。
示例 2:
输入:
[2,3,10]
输出:
8
限制:
1 <= n <= 4
1 <= coins[i] <= 10
解法一:贪心 + 模拟
算法思路:
对于每一堆硬币,我们每次可以拿一枚或者两枚硬币,根据贪心策略,想要拿的次数少,每次就得多拿,因此我们每次都拿两枚,共 coins[i] / 2
此,如果是奇数个硬币,则还要多拿一次。
代码实现:
class Solution {
public int minCount(int[] coins) {
int res = 0;
for(int coin : coins){
res += (coin + 1) / 2;
}
return res;
}
}
一行代码实现:
class Solution {
public int minCount(int[] coins) {
return Arrays.stream(coins)
.map(coin -> (coin + 1) / 2)
.sum();
}
}
复杂度分析:
时间复杂度: O(n),n 为数组长度
空间复杂度: O(1)