跳转至

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)\)。

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

1
2
3
4
5
6
7
8
9
class Solution {
    public int minCount(int[] coins) {
        int ans = 0;
        for (int x : coins) {
            ans += (x + 1) >> 1;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int minCount(vector<int>& coins) {
        int ans = 0;
        for (int x : coins) {
            ans += (x + 1) >> 1;
        }
        return ans;
    }
};

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    /**
     * @param Integer[] $coins
     * @return Integer
     */
    function minCount($coins) {
        $ans = 0;
        foreach ($coins as $x) {
            $ans += ($x + 1) >> 1;
        }
        return $ans;
    }
}

1
2
3
4
5
6
7
int minCount(int* coins, int coinsSize) {
    int ans = 0;
    for (int i = 0; i < coinsSize; ++i) {
        ans += (coins[i] + 1) >> 1;
    }
    return ans;
}

1
2
3
4
5
6
7
8
9
class Solution {
    func minCount(_ coins: [Int]) -> Int {
        var ans = 0
        for x in coins {
            ans += (x + 1) >> 1
        }
        return ans
    }
}

评论