LCP 06. 拿硬币：
桌上有 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] + 1) / 2。如果原本是偶数，则不影响取整除的结果，如果是奇数则会使取整除的结果加一。 - 位运算要比算术运算快，所以我们可以优化为
(coins[i] + 1) >> 1。
题解
java
class Solution {
public int minCount(int[] coins) {
int ans = 0;
for (int c : coins) {
ans += (c + 1) >> 1;
}
return ans;
}
}c
int minCount(int* coins, int coinsSize){
int ans = 0;
for (int i = 0; i < coinsSize; ++i) {
ans += (coins[i] + 1) >> 1;
}
return ans;
}c++
class Solution {
public:
int minCount(vector<int>& coins) {
int ans = 0;
for (int& c : coins) {
ans += (c + 1) >> 1;
}
return ans;
}
};python
class Solution:
def minCount(self, coins: List[int]) -> int:
return sum([(c + 1) >> 1 for c in coins])go
func minCount(coins []int) int {
ans := 0
for _, c := range coins {
ans += (c + 1) >> 1
}
return ans
}rust
impl Solution {
pub fn min_count(coins: Vec<i32>) -> i32 {
coins.iter().map(|c|{
(c + 1) >> 1
}).sum()
}
}
原题传送门：https://leetcode-cn.com/problems/na-ying-bi/
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
