草庐IT

「贪心」构成特定和需要添加的最少元素(力扣第1785题)

孤星·璀璨 2023-03-28 原文

本题为12月16日力扣每日一题

题目来源:力扣第1785题

题目tag:贪心

题面

题目描述

给你一个整数数组nums，和两个整数limit与goal。数组nums有一条重要属性：abs(nums[i]) <= limit 。

返回使数组元素总和等于goal所需要向数组中添加的最少元素数量，添加元素不应改变数组中abs(nums[i]) <= limit这一属性。

注意，如果x >= 0，那么abs(x)等于x；否则，等于-x。

示例

示例 1

输入：

nums = [1,-1,1], limit = 3, goal = -4

输出：

2

解释：

可以将-2和-3添加到数组中，数组的元素总和变为1 - 1 + 1 - 2 - 3 = -4。

示例 2

输入：

nums = [1,-10,9,1], limit = 100, goal = 0

输出：

1

提示

1 <= nums.length <= 105
1 <= limit <= 106
-limit <= nums[i] <= limit
-109 <= goal <= 109

思路分析

一道简单的思维题.

先考虑当前总和(下记为sum)小于goal的情况,此时需要添加一些正数,来填满中间的差.显然应该贪心地每次均填limit,这样可以保证每次填得最多,使得填的次数最少.如果最后恰好放满了,答案即为(goal - sum) / limit.当然,有可能会出现最后一次不够limit,这时只填剩下的差即可,此时答案即为(goal - sum) / limit + 1.

接着考虑sum大于goal的情况,此时需要添加一些负数,来砍掉多出的部分.显然应该贪心地每次砍limit(放入-limit),这样可以保证每次砍得最多,使砍的次数最少.如果最后恰好砍完了,答案即为(sum - goal) / limit.当然,有可能会出现最后一次砍limit太多,这时只砍掉剩下的多出来的部分即可,此时答案即为(sum - goal) / limit + 1.

综上,直接用|goal - sum|作为差值即可统一上面两种情况,得出最后的答案.

参考代码

class Solution
{
public:
    int minElements(vector<int> &nums, int limit, int goal)
    {
        // 求和
        long long sum = 0;
        for (auto i : nums)
        {
            sum += i;
        }

        // 计算差,利用绝对值排除正负干扰(由于个人学校的oj中的abs存在bug,所以个人习惯用fabs取绝对值)
        long long diff = fabs(goal - sum);

        // 分类计算需要几个数
        if (diff % limit == 0)
        {
            return diff / limit;
        }
        else
        {
            return diff / limit + 1;
        }
    }
};

"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德

定和1785codelimitgoal算法与数据结构

有关「贪心」构成特定和需要添加的最少元素(力扣第1785题)的更多相关文章

  1. ruby - 我需要将 Bundler 本身添加到 Gemfile 中吗？ - 2

    当我使用Bundler时，是否需要在我的Gemfile中将其列为依赖项？毕竟，我的代码中有些地方需要它。例如，当我进行Bundler设置时:require"bundler/setup" 最佳答案 没有。您可以尝试，但首先您必须用鞋带将自己抬离地面。 关于ruby-我需要将Bundler本身添加到Gemfile中吗？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/4758609/

  2. ruby - 将 Bootstrap Less 添加到 Sinatra - 2

    我有一个ModularSinatra应用程序，我正在尝试将Bootstrap添加到应用程序中。get'/bootstrap/application.css'doless:"bootstrap/bootstrap"end我在views/bootstrap中有所有less文件，包括bootstrap.less。我收到这个错误:Less::ParseErrorat/bootstrap/application.css'reset.less'wasn'tfound.Bootstrap.less的第一行是://CSSReset@import"reset.less";我尝试了所有不同的路径格式，但它

  3. ruby - 续集在添加关联时访问many_to_many连接表 - 2

    我正在使用Sequel构建一个愿望list系统。我有一个wishlists和itemstable和一个items_wishlists连接表(该名称是续集选择的名称)。items_wishlists表还有一个用于facebookid的额外列(因此我可以存储opengraph操作)，这是一个NOTNULL列。我还有Wishlist和Item具有续集many_to_many关联的模型已建立。Wishlist类也有:selectmany_to_many关联的选项设置为select:[:items.*,:items_wishlists__facebook_action_id].有没有一种方法可以

  4. ruby - rspec 需要 .rspec 文件中的 spec_helper - 2

    我注意到像bundler这样的项目在每个specfile中执行requirespec_helper我还注意到rspec使用选项--require，它允许您在引导rspec时要求一个文件。您还可以将其添加到.rspec文件中，因此只要您运行不带参数的rspec就会添加它。使用上述方法有什么缺点可以解释为什么像bundler这样的项目选择在每个规范文件中都需要spec_helper吗？ 最佳答案 我不在Bundler上工作，所以我不能直接谈论他们的做法。并非所有项目都checkin.rspec文件。原因是这个文件，通常按照当前的惯例，只

  5. ruby - 如何在 Lion 上安装 Xcode 4.6，需要用 RVM 升级 ruby - 2

    我实际上是在尝试使用RVM在我的OSX10.7.5上更新ruby，并在输入以下命令后:rvminstallruby我得到了以下回复:Searchingforbinaryrubies,thismighttakesometime.Checkingrequirementsforosx.Installingrequirementsforosx.Updatingsystem.......Errorrunning'requirements_osx_brew_update_systemruby-2.0.0-p247',pleaseread/Users/username/.rvm/log/138121

  6. ruby - 可以通过多少种方法将方法添加到 ruby​​ 对象？ - 2

    当谈到运行时自省(introspection)和动态代码生成时，我认为ruby​​没有任何竞争对手，可能除了一些lisp方言。前几天，我正在做一些代码练习来探索ruby​​的动态功能，我开始想知道如何向现有对象添加方法。以下是我能想到的3种方法:obj=Object.new#addamethoddirectlydefobj.new_method...end#addamethodindirectlywiththesingletonclassclass这只是冰山一角，因为我还没有探索instance_eval、module_eval和define_method的各种组合。是否有在线/离线资

  7. ruby - 如何在 Ruby 中向现有方法定义添加语句 - 2

    我注意到类定义，如果我打开classMyClass，并在不覆盖的情况下添加一些东西我仍然得到了之前定义的原始方法。添加的新语句扩充了现有语句。但是对于方法定义，我仍然想要与类定义相同的行为，但是当我打开defmy_method时似乎,def中的现有语句和end被覆盖了，我需要重写一遍。那么有什么方法可以使方法定义的行为与定义相同，类似于super，但不一定是子类？ 最佳答案 我想您正在寻找alias_method:classAalias_method:old_func,:funcdeffuncold_func#similartoca

  8. ruby-on-rails - 添加回形针新样式不影响旧上传的图像 - 2

    我有带有Logo图像的公司模型has_attached_file:logo我用他们的Logo创建了许多公司。现在，我需要添加新样式has_attached_file:logo,:styles=>{:small=>"30x15>",:medium=>"155x85>"}我是否应该重新上传所有旧数据以重新生成新样式？我不这么认为……或者有什么rake任务可以重新生成样式吗？ 最佳答案 参见Thumbnail-Generation.如果rake任务不适合你，你应该能够在控制台中使用一个片段来调用重新处理!关于相关公司

  9. ruby - 在哈希的键数组中追加元素 - 2

    查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

  10. ruby - 为什么在 ruby​​ 中创建 Rational 不需要新方法 - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Rubysyntaxquestion:Rational(a,b)andRational.new!(a,b)我正在阅读ruby镐书，我对创建有理数的语法感到困惑。Rational(3,4)*Rational(1,2)产生=>3/8为什么Rational不需要new方法(我还注意到例如我可以在没有new方法的情况下创建字符串)？

随机推荐