LCP 06. 拿硬币

难度: 简单

来源: 每日一题 2023.09.20

---

桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

示例 1：

输入：[4,2,1]

输出：4

解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。

示例 2：

输入：[2,3,10]

输出：8

限制：

• 1 <= n <= 4
• 1 <= coins[i] <= 10

class Solution {
    public int minCount(int[] coins) {
    }
}

分析与题解

---

• 贪心算法 + 求余 + 整除

  这个题目非常非常的简单, 由于我们知道, 每一次的操作会有如下几种情况

  • 从某一堆中拿出2个

  • 从某一堆中拿出1个

  • 从某一堆中拿出0个

  但是, 为了达成最小的拿取次数, 我们每一次都应该尝试拿取2个硬币. 如果当前堆拿到最后只剩1个, 我们也要做拿取1次的操作. 所以这里, 我们就需要使用 求余 + 整除 求出当前堆的拿取次数, 然后添加到结果中即可.

  int item = coins[i];
  result += item/2;
  result += item%2;
  

  整体的解题过程如下所示.

  整体逻辑代码如下所示.

  class Solution {
      public int minCount(int[] coins) {
          int result = 0;
          for(int i = 0; i < coins.length; i++) {
              int item = coins[i];
              result += item/2;
              result += item%2;
          }
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 一次遍历循环, 时间复杂度与数组长度相关.
  • 空间复杂度: O(1), 常量级别的空间复杂度.

  结果如下所示.

  

• 贪心算法 + 向上整除法

  在上一个解题思路中, 我们利用整除 + 取余 求出整个题解. 这次, 我们使用 向上整除法 来求解整个过程.

  向上整除法 对于这题的思路是这样的, 我们对某一堆硬币数量 + 1 , 然后 / 2.

  我们会发现, 对于原来能整除的数, 结果是不会发生改变的, 对于原来有余数的数, 结果会+1. 这就是我们想要的结果.

  result += (item + 1)/2;
  

  接下来, 我们看一下整体的解题思路.

  class Solution {
      public int minCount(int[] coins) {
          int result = 0;
          for(int i = 0; i < coins.length; i++) {
              int item = coins[i];
              result += (item + 1)/2;
          }
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 一次遍历循环, 时间复杂度与数组长度相关.
  • 空间复杂度: O(1), 常量级别的空间复杂度.

  结果如下所示.