算法刷题——拿出最少数目的魔法豆(力扣)

这篇具有很好参考价值的文章主要介绍了算法刷题——拿出最少数目的魔法豆(力扣)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

传送门
拿出最少数目的魔法豆:给定一个正整数 数组beans ,其中每个整数表示一个袋子里装的魔法豆的数目。请你从每个袋子中拿出 一些豆子(也可以 拿出),使得剩下的非空袋子中(即至少还有一颗魔法豆的袋子)魔法豆的数目相等。一旦把魔法豆从袋子中取出,你不能再将它放到任何袋子中。
请返回你需要拿出魔法豆的最少数目。

我的解法

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        if(beans.size() == 1) return 0;
        sort(beans.begin(),beans.end());

        long long res = LONG_MAX, temp = 0;
        for(int i = 0 ; i < beans.size(); ++i){
            temp = 0;
            if(i > 0) temp = accumulate(beans.begin(), beans.begin() + i, 0);
            for(int j = i + 1; j < beans.size(); ++j){
                temp += (beans[j] - beans[i]);
            }
            if(temp < res){
                res = temp;
            }
        }
        return res;
    }
};

思路

暴力求解,先对数组进行排序,然后从小到大分别以不同数量的豆子作为基准(非空袋子中剩下的豆子数量),求解答案。

结果

算法刷题——拿出最少数目的魔法豆(力扣),算法,leetcode,c++

分析

时间复杂度
O(n2)。

空间复杂度
O(logn),即为排序的栈空间开销。

官方题解

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        int n = beans.size();
        sort(beans.begin(), beans.end());
        long long total = accumulate(beans.begin(), beans.end(), 0LL); // 豆子总数
        long long res = total; // 最少需要移除的豆子数
        for (int i = 0; i < n; i++) {
            res = min(res, total - (long long)beans[i] * (n - i));
        }
        return res;
    }
};

分析

时间复杂度
O(nlogn),排序算法。

空间复杂度
O(logn),即为排序的栈空间开销。

查漏补缺

暴力算法超出时间范围,需要思考其他的解决方案。两次循环求和可以通过总数减去一定的值得到结果(需要自己多一份思考,而不是直接暴力求解)。

更新日期

2024.01.18

参考来源

力扣链接文章来源地址https://www.toymoban.com/news/detail-804914.html

到了这里,关于算法刷题——拿出最少数目的魔法豆(力扣)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Leetcode力扣秋招刷题路-0854

    从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 对于某些非负整数 k ,如果交换 s1 中两个字母的位置恰好 k 次,能够使结果字符串等于 s2 ,则认为字符串 s1 和 s2 的 相似度为 k 。 给你两个字母异位词 s1 和 s2 ,返回 s1 和 s2 的相似度 k 的最小值。 示例

    2024年02月02日
    浏览(48)
  • Leetcode力扣秋招刷题路-0609

    从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 给你一个目录信息列表 paths ,包括目录路径,以及该目录中的所有文件及其内容,请你按路径返回文件系统中的所有重复文件。答案可按 任意顺序 返回。 一组重复的文件至少包括 两个 具有完全相同内容

    2023年04月24日
    浏览(82)
  • Leetcode力扣秋招刷题路-0721

    从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 给定一个列表 accounts,每个元素 accounts[i] 是一个字符串列表,其中第一个元素 accounts[i][0] 是 名称 (name),其余元素是 emails 表示该账户的邮箱地址。 现在,我们想合并这些账户。如果两个账户都有一些共同

    2023年04月27日
    浏览(85)
  • Leetcode力扣秋招刷题路-0447

    从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 给定平面上 n 对 互不相同 的点 points ,其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ,其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等(需要考虑元组的顺序)。 返回平面上所有回旋镖的

    2023年04月22日
    浏览(77)
  • Leetcode力扣秋招刷题路-0189

    从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。 示例 1: 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转

    2023年04月16日
    浏览(52)
  • Leetcode力扣秋招刷题路-0399

    从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件,其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。 另有一些以数组 queries 表

    2023年04月22日
    浏览(34)
  • Leetcode力扣秋招刷题路-0902

    从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如,如果 digits = [‘1’,‘3’,‘5’],我们可以写数字,如 ‘13’, ‘551’, 和 ‘1351315’。 返回 可以生成的小于或

    2024年02月02日
    浏览(49)
  • 【leetcode 力扣刷题】汇总区间//合并区间//插入区间

    题目链接:228.汇总区间 题目内容: 看题目真是没懂这个题到底是要干啥……实际上题目要求的 恰好覆盖数组中所有数字 的 最小有序 区间范围列表,这个最小是指一个区间范围小。比如能够覆盖{2,3,4,6}的区间可以是[2,6],但是5在区间内,却不在数组内,因此这个区间不是最

    2024年02月10日
    浏览(38)
  • leetcode 力扣刷题 旋转矩阵(循环过程边界控制)

    下面的题目的主要考察点都是,二维数组从左上角开始顺时针(或者逆时针)按圈遍历数组的过程。顺时针按圈遍历的过程如下: 对于每一圈,分为四条边 ,循环遍历就好。这时,对于 四个角 的元素的处理,可以将四条边的遍历分为以下两种情况: 第一种:每条边都从对

    2024年02月12日
    浏览(48)
  • 力扣python刷题day03|LeetCode203、707、206

    题目 题目链接:203:移除链表元素 方法一: 知识点: 设置虚拟头结点 题目 来源:力扣(LeetCode) 提示: 0 = index, val = 1000 请不要使用内置的 LinkedList 库。 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。 方法一:单链表法 方法二:双链表法 (有点难

    2024年02月16日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包