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

思路分析

首先我们应该要先理解一下题目意思，题目会给我们一个长度为n整数数组coins，代表桌子上有n堆硬币，我们每次可以选择任意一堆，拿走其中的一枚或者两枚，需要我们计算取完桌面上所有硬币所需要的次数，这里需要注意一下，我们每次取硬币的时候只能取同一堆硬币里的，也就是说如果有两堆数量都为1的硬币时，我们也不可以同时将两个硬币取走，我们每次只能选择其中一堆进行取硬币操作。

如：[1,1,1]，这里有三堆硬币，虽然每一堆都只有一个硬币，但我们不能跨堆混取硬币，我们只能先将一堆的硬币取完，所以我们需要取三次才可以将硬币取完，每次选择任意一堆，将那一堆的1枚硬币取走即可。

理解了题目之后，我们会发现题目其实并不难，我们只需要遍历数组，求出每堆硬币取完所需次数，再计算总和即可。因为每次只能取一枚或两枚硬币，为了减少取硬币的次数，我们肯定是优先取两枚，直到硬币数量少于两枚的时候再取一枚，所以这里我们可以直接使用每堆的硬币数除以2并向上取整就可以得到当前硬币堆取完所需的次数。

let res = 0;
coins.forEach((coin) => {
    res += Math.ceil(coin / 2);
});

AC 代码

完整 AC 代码如下：

/**
 * @param {number[]} coins
 * @return {number}
 */
var minCount = function (coins) {
  let res = 0;
  coins.forEach((coin) => {
    res += Math.ceil(coin / 2);
  });
  return res;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。