LeetCode:2171. 拿出最少数目的魔法豆(C++、Java 排序 + 前后缀)

这篇具有很好参考价值的文章主要介绍了LeetCode:2171. 拿出最少数目的魔法豆(C++、Java 排序 + 前后缀)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

2171. 拿出最少数目的魔法豆

题目描述:

实现原理与解析:

排序 + 前后缀

原理思路:


2171. 拿出最少数目的魔法豆

题目描述:

        给定一个 正整数 数组 beans ,其中每个整数表示一个袋子里装的魔法豆的数目。

请你从每个袋子中 拿出 一些豆子(也可以 不拿出),使得剩下的 非空 袋子中(即 至少还有一颗 魔法豆的袋子)魔法豆的数目 相等。一旦把魔法豆从袋子中取出,你不能再将它放到任何袋子中。

请返回你需要拿出魔法豆的 最少数目

示例 1:

输入:beans = [4,1,6,5]
输出:4
解释:
- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。
  剩下袋子中魔法豆的数目为:[4,0,6,5]
- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为:[4,0,4,5]
- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。
  剩下袋子中魔法豆的数目为:[4,0,4,4]
总共拿出了 1 + 2 + 1 = 4 个魔法豆,剩下非空袋子中魔法豆的数目相等。
没有比取出 4 个魔法豆更少的方案。

示例 2:

输入:beans = [2,10,3,2]
输出:7
解释:
- 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为:[0,10,3,2]
- 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为:[0,10,3,0]
- 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。
  剩下袋子中魔法豆的数目为:[0,10,0,0]
总共拿出了 2 + 2 + 3 = 7 个魔法豆,剩下非空袋子中魔法豆的数目相等。
没有比取出 7 个魔法豆更少的方案。

提示:

  • 1 <= beans.length <= 105
  • 1 <= beans[i] <= 105

实现原理与解析:

排序 + 前后缀

C++

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        
        int n = beans.size();

        sort(beans.begin(), beans.end());
        long long res = LONG_MAX;
        long long pre_sum = 0;
        vector<long long> suf(beans.size() + 1); // 后缀,表示以beans[i]为标准,需要去除的豆子个数
        long long j = 1; // 可以想象一下图,是很多矩形组成,这个j就是长度,差值是高度
        for (int i = n - 2; i >= 0; i--, j++) {
            suf[i] = (beans[i + 1] - beans[i]) * j + suf[i + 1];
        }
        for (int i = 0; i < n; i++) {
            long long cur = pre_sum;
            pre_sum += beans[i];
            
            res = min(res, cur + suf[i]);
        }

        return res;
    }
};

Java

class Solution {
    public long minimumRemoval(int[] beans) {
        
        Arrays.sort(beans);
        int n = beans.length;
        long[] suf = new long[n];

        long j = 1;

        for (int i = n - 2; i >= 0; i--, j++) {
            suf[i] = (beans[i + 1] - beans[i]) * j + suf[i + 1]; 
        }

        long res = Long.MAX_VALUE;
        long pre = 0;
        for (int i = 0; i < n; i++) {
            long cur = pre;
            pre += beans[i];
            res = Math.min(res, cur + suf[i]);
        }

        return res;
    }
}

原理思路:

        理解题目,其实就算选中一个袋子,大于其豆子数量的袋子减去响应豆子变成和其一样的,小于的直接清零。所以很明显,我们需要排序。

        如果直接循环,根据数据范围,会超时,所以利用前后缀先预处理出选取不同i的前缀和,以及后缀,当然后缀取的是,需要去掉的豆子总和,在求后缀时,可以想象一下二维矩形图,其实是就是很多小矩形组成,这个j就是长度,差值是高度。

        这里我前缀直接在遍历的时候再求的,也可以提前求出来,是一样的。

        最后遍历一下就行,注意开long long。文章来源地址https://www.toymoban.com/news/detail-807296.html

到了这里,关于LeetCode:2171. 拿出最少数目的魔法豆(C++、Java 排序 + 前后缀)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 问,由于java存在性能上,以及部分功能上的缺点,请问如何正确使用C,C++,Go,这三个语言,提升Java Web项目的性能?

    拓展阅读:版本任你发,我用java8 我明白Java虽然在许多方面表现出色,但在某些特定场景下可能会遇到性能瓶颈或功能限制。为了提升Java Web项目的性能,可以考虑将C、C++和Go这三种语言用于特定的组件或服务。以下是如何正确使用这些语言来提升性能的一些建议: 1. **性能

    2024年04月23日
    浏览(37)
  • LeetCode:207. 课程表、210. 课程表 II(拓扑排序 C++)

    目录 207. 课程表 题目描述: 实现代码与解析: 拓扑排序 210. 课程表 II 题目描述: 实现代码与解析: 拓扑排序 原理思路:         你这个学期必须选修  numCourses  门课程,记为  0  到  numCourses - 1  。 在选修某些课程之前需要一些先修课程。 先修课程按数组  prereq

    2024年02月09日
    浏览(43)
  • 【leetcode题解C++】34.在排序数值中查找第一个和最后一个位置

    给你一个按照非递减顺序排列的整数数组  nums ,和一个目标值  target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值  target ,返回  [-1, -1] 。 你必须设计并实现时间复杂度为  O(log n)  的算法解决此问题。 示例 1: 示例 2: 示例 3: 思路

    2024年01月16日
    浏览(40)
  • Leetcode刷题笔记题解(C++):83. 删除排序链表中的重复元素

    思路:链表相关的问题建议就是画图去解决,虽然理解起来很容易,但就是写代码写不出来有时候,依次去遍历第二节点如果与前一个节点相等则跳过,不相等则遍历第三个节点

    2024年02月22日
    浏览(68)
  • 【经典算法】 leetcode88.合并排序的数组(Java/C/Python3实现含注释说明,Easy)

    作者主页: 🔗进朱者赤的博客 精选专栏:🔗经典算法 作者简介:阿里非典型程序员一枚 ,记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法( 公众号同名 ) ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论,💬支持博主,记得点个大大的 关

    2024年04月22日
    浏览(41)
  • java设计模式-目的及思想

    某类问题的通用解决方案; 代码重用性 相同功能的代码,不用多次编写 可读性 编程规范,便于其他程序员阅读和理解 可扩展性 新增功能时,非常的方便 可靠性 新增功能时,对原功能无影响 高内聚、低耦合 使程序高内聚、低耦合 找出应用中可能变化之处,把他们独立出

    2024年02月08日
    浏览(44)
  • Java项目的性能优化样例

    场景一:高并发频繁的数据库访问 解决方案: 总所周知的是:加缓存,最常见的是:加缓存中间件如 Redis,当然了这里要说的不是这个,增加一个中间件多少有点费事儿; 通过Java类的方式解决 POM添加jar包 //在 service 层或者 DAO 层创建了一个名为 consumerCache 的缓存池,这里用

    2024年02月08日
    浏览(42)
  • 分别用JavaScript,Java,PHP,C++实现桶排序的算法(附带源码)

    桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点: 在额外空间充足的情况下,尽量增大桶的数量 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中 同时,对于桶中

    2024年02月22日
    浏览(49)
  • 2023年以就业为目的学习Java还有必要吗?

    现在学 Java 找工作还有优势吗? 在某乎上可以看到大家对此问题的热议:“2023年以就业为目的学习Java还有必要吗?” 。有人说市场饱和,最好是学点当前最流行的技术;也有人说 Java 应用广泛,以找工作为目的学习它还是很有必要的。 放眼国内市场,可能有些场景有 Jav

    2024年02月08日
    浏览(44)
  • 华为OD机试 - 启动多任务排序(Java & JS & Python & C & C++)

    哈喽,本题库完全免费,收费是为了防止被爬,大家订阅专栏后可以私信联系退款。感谢支持 一个应用启动时,会有多个初始化任务需要执行,并且任务之间有依赖关系,例如A任务依赖B任务,那么必须在B任务执行完成之后,才能开始执行A任务。 现在给出多条任务依赖关系

    2024年04月10日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包