CTF of Z2BNS
0%

拿硬币

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 767 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

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

示例1：

1
2
3
输入：[4,2,1]
输出：4
解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。

示例2：

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

限制：

  • 1 <= n <= 4
  • 1 <= coins[i] <= 10
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

遍历n堆力扣币coins，对每一堆判断是否大于0，有则次数加1，币数减2循环计算。

c++代码：(执行用时0ms，击败100.00%，内存消耗8.4M，击败9.29%）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minCount(vector<int>& coins) {
        int result=0;
        for(int i=0;i<coins.size();++i){
            while(coins[i]>0){
                ++result;
                coins[i]-=2;
            }
        }
    return result;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

题意概述
有 n 堆硬币，每次从任意一堆拿走一枚或者两枚。问最少几次能够全部拿完。

题解
题目中虽然给了 n 堆硬币，但是最终每一堆都是要拿完的。而每一堆拿的情况又不影响其他硬币堆，因此每一堆硬币的拿法实际上是互相独立的。

于是我们可以只考虑一堆的情况。假设一堆有 x 枚硬币，既然我们的目的是尽早拿完所有硬币堆，那么两枚两枚的拿显然是更快的。

求单堆硬币最小次数：(x+1)//2

那么，拿完所有硬币堆只需要循环对所有硬币堆都计算一次，然后求和就可以了。

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

复杂度分析

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

官方题解是python解法，用官方的思路c++实现跟我的代码效率也差不多!。

------------- THE END! THANKS! -------------