欢迎来到
银狐的个人博客

【算法学习】LCP 06. 拿硬币(java / c / c++ / python / go / rust)


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


文章目录 LCP 06. 拿硬币:样例 1样例 2提示分析题解javacc++pythongorust 原题传送门:https://leetcode-cn.com/problems/na-ying-bi/


LCP 06. 拿硬币:

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

样例 1

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

样例 2

输入:[2,3,10]输出:8

提示 1 <= n <= 41 <= coins[i] <= 10


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


题解 java

class Solution {    public int minCount(int[] co【算法学习】LCP 06. 拿硬币(java / c / c++ / python / go / rust) 第1张图片-银狐博客ins) {        int ans = 0;        for (int c : coins) {            ans += (c + 1) >> 1;        }        return ans;    }}

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++

class Solution {public:    int minCount(vector<int>& coins) {        int ans = 0;        for (int& c : coins) {            ans += (c + 1) >> 1;        }        return ans;    }};

python

class Soluti【算法学习】LCP 06. 拿硬币(java / c / c++ / python / go / rust) 第2张图片-银狐博客on:    def minCount(self, coins: List[int]) -> int:        return sum([(c + 1) >> 1 for c in coins])

go

func minCount(coins []int) int {    ans := 0for _, c := range coins {ans += (c + 1) >> 1}return ans}

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) 打赏
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《【算法学习】LCP 06. 拿硬币(java / c / c++ / python / go / rust)》
文章链接:https://www.yinhu3.com/1677.html
本站资源仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。
如果文章侵犯到你的权益,请查看本站免责声明:《免责声明》

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

愿意请我喝杯矿泉水吗

支付宝扫一扫打赏