【算法学习】LCP 06 拿硬币（java / c / c

发表于

这是我参与11月更文挑战的第2天，活动详情查看：2021最后一次更文挑战

非常感谢你阅读本文~
欢迎【👍点赞】【⭐收藏】【📝评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子 https://juejin.cn/user/2771185768884824/posts 博客原创~

LCP 06. 拿硬币：

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

样例 1

1
2
3
4
5
6
7
8
markdown复制代码输入：
	[4,2,1]
	
输出：
	4

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

样例 2

1
2
3
4
5
markdown复制代码输入：
	[2,3,10]

输出：
	8

提示

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

分析

  • 这道算法题二当家的相信大家都能做出来，但是不是已经仔细优化过了呢？
  • 每次任意选择一堆去拿，很显然每一堆之间互不影响，所以累加计算每一堆最少拿几次之和就是想要的结果。
  • 每次可以拿一枚或两枚，孩子也知道往多了拿嘛，肯定每次都拿两枚是最快的，只不过如果某一堆硬币是奇数，那最后一次就只能拿一枚。
  • 直接用二取整除的话，奇数就会少算一次，所以我们需要判断奇数还是偶数，如果是奇数就要多算一次。
  • 是不是可以统一处理奇数和偶数呢？可以直接先加一再用二取整除 (coins[i] + 1) / 2。如果原本是偶数，则不影响取整除的结果，如果是奇数则会使取整除的结果加一。
  • 位运算要比算术运算快，所以我们可以优化为 (coins[i] + 1) >> 1。

题解

java

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

c

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

c++

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

python

1
2
3
python复制代码class Solution:
    def minCount(self, coins: List[int]) -> int:
        return sum([(c + 1) >> 1 for c in coins])

go

1
2
3
4
5
6
7
go复制代码func minCount(coins []int) int {
    ans := 0
	for _, c := range coins {
		ans += (c + 1) >> 1
	}
	return ans
}

rust

1
2
3
4
5
6
7
rust复制代码impl Solution {
    pub fn min_count(coins: Vec<i32>) -> i32 {
        coins.iter().map(|c|{
            (c + 1) >> 1
        }).sum()
    }
}

在这里插入图片描述

原题传送门：https://leetcode-cn.com/problems/na-ying-bi/

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%