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

解法

方法一：数学

我们可以发现，每堆力扣币拿完的最少次数，等于该堆力扣币数量除以 $2$ 向上取整的结果之和。

因此，我们只需要遍历每堆力扣币 $x_i$，计算每堆力扣币拿完的最少次数 $\left \lceil x_i/2 \right \rceil$，然后累加即可。

时间复杂度 $O(n)$，其中 $n$ 是数组 $coins$ 的长度。空间复杂度 $O(1)$。

Python3

class Solution:
    def minCount(self, coins: List[int]) -> int:
        return sum((x + 1) >> 1 for x in coins)

Java

class Solution {
    public int minCount(int[] coins) {
        int ans = 0;
        for (int x : coins) {
            ans += (x + 1) >> 1;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minCount(vector<int>& coins) {
        int ans = 0;
        for (int x : coins) {
            ans += (x + 1) >> 1;
        }
        return ans;
    }
};

Go

func minCount(coins []int) (ans int) {
	for _, x := range coins {
		ans += (x + 1) >> 1
	}
	return
}

TypeScript

function minCount(coins: number[]): number {
    let ans = 0;
    for (const x of coins) {
        ans += (x + 1) >> 1;
    }
    return ans;
}

Rust

impl Solution {
    pub fn min_count(coins: Vec<i32>) -> i32 {
        coins
            .iter()
            .map(|&x| (x + 1) >> 1)
            .sum::<i32>()
    }
}

C

int minCount(int* coins, int coinsSize) {
    int ans = 0;
    for (int i = 0; i < coinsSize; ++i) {
        ans += (coins[i] + 1) >> 1;
    }
    return ans;
}

PHP

class Solution {
    /**
     * @param Integer[] $coins
     * @return Integer
     */
    function minCount($coins) {
        $ans = 0;
        foreach ($coins as $x) {
            $ans += $x + 1 >> 1;
        }
        return $ans;
    }
}

...