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 博客原创~