LCP 06. 拿硬币

Posted on | In
Words count in article: 314 | Reading time ≈ 1

题目

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

示例 1:

1
2
3
4
5
输入：[4,2,1]

输出：4

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

示例2:

1
2
3
输入：[2,3,10]

输出：8

提示：

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

解法

解法一：

要求求出拿光硬币的最小次数，那就意味着每次都要拿最多的2个硬币。那么奇数堆拿光的次数就是（N - 1 ）/ 2 + 1 或者是（N + 1） / 2，偶数堆则是N / 2.

JAVA

1
2
3
4
5
6
7
8
9
10
11
public int minCount(int[] coins) {
        int sum = 0;
        for (int coin : coins) {
            if (coin % 2 == 1) {
                sum += (coin - 1) / 2 + 1;
            } else {
                sum += coin / 2;
            }
        }
        return sum;
    }

解法二：

除2得时候不需要判断奇偶，直接在原数上加一，除以2就行，原先偶数的加一之后，除2得到的值还是原来偶数除2的值。

JAVA

1
2
3
4
5
6
7
public int minCount(int[] coins) {
        int res = 0;
        for (int coin: coins) {
            res += (coin + 1) / 2;
        }
        return res;
    }
0%