草庐IT

贪心2|122.买卖股票的最佳时机II|55.跳跃游戏|45.跳跃游戏II

顾小九 2023-04-04 原文

贪心2|122.买卖股票的最佳时机II|55.跳跃游戏|45.跳跃游戏II

一、122.买卖股票的最佳时机II

题目链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

  1. 需要理解最终利润是可以分解的，假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。

    相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

  2. 将最终利润分解为每天利润之和，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。

  3. 局部最优：收集每天的正利润，全局最优：求得最大利润。局部最优可以推出全局最优，且找不出反例，用贪心算法。

class Solution {
    public int maxProfit(int[] prices) {
        int count;
        int sum = 0;
        for(int i = 1; i < prices.length; i++){
            count = prices[i] - prices[i - 1];
            if(count > 0){
                sum += count;
            }
        }
        return sum;
    }
}

二、55.跳跃游戏

题目连接：55. 跳跃游戏 - 力扣（LeetCode）

  1. 此题能否跳到终点问题关键在于可跳的覆盖范围 ，这个问题可转化为跳跃覆盖范围究竟可不可以覆盖到终点。每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
  2. 贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。局部最优推出全局最优，找不出反例，试试贪心算法。
class Solution {
    public boolean canJump(int[] nums) {
        int cover = 0;
        if(nums.length == 1) return true;
        for(int i = 0; i <= cover; i++){
            cover = Math.max(i + nums[i], cover);
            if(cover >= nums.length - 1) return true;
        }
        return false;
    }
}

三、45.跳跃游戏II

题目链接：45. 跳跃游戏 II - 力扣（LeetCode）

  1. 贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。 以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！
  2. 如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。
  3. 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。
class Solution {
    public int jump(int[] nums) {
        if(nums.length == 1) return 0;
        int cur = 0;
        int next = 0;
        int result = 0;
        for(int i = 0; i < nums.length; i++){
            next = Math.max(i + nums[i], next);
            if(i == cur){
                if(cur != nums.length - 1){
                    result++;
                    cur = next;
                    if(cur >= nums.length - 1) break;
                }else break;
            }
        }
        return result;
    }
}
122游戏spanclasstoken贪心算法$leetcode$java$数据结构$算法

有关贪心2|122.买卖股票的最佳时机II|55.跳跃游戏|45.跳跃游戏II的更多相关文章

  1. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  3. ruby-on-rails - Rails 中同一个类的多个关联的最佳实践？ - 2

    我认为我的问题最好用一个例子来描述。假设我有一个名为“Thing”的简单模型，它有一些简单数据类型的属性。像...Thing-foo:string-goo:string-bar:int这并不难。数据库表将包含具有这三个属性的三列，我可以使用@thing.foo或@thing.bar之类的东西访问它们。但我要解决的问题是当“foo”或“goo”不再包含在简单数据类型中时会发生什么？假设foo和goo代表相同类型的对象。也就是说，它们都是“Whazit”的实例，只是数据不同。所以现在事情可能看起来像这样......Thing-bar:int但是现在有一个新的模型叫做“Whazit”，看起来

  4. ruby-on-rails - 向 Rails 3 添加 Ruby 扩展方法的最佳实践？ - 2

    我有一个要在我的Rails3项目中使用的数组扩展方法。它应该住在哪里？我有一个应用程序/类，我最初把它放在(array_extensions.rb)中，在我的config/application.rb中我加载路径:config.autoload_paths+=%W(#{Rails.root}/应用程序/类)。但是，当我转到railsconsole时，未加载扩展。是否有一个预定义的位置可以放置我的Rails3扩展方法？或者，一种预先定义的方式来添加它们？我知道Rails有自己的数组扩展方法。我应该将我的添加到active_support/core_ext/array/conversion

  5. ruby - 最佳原则中的原则 - 2

    我似乎经常遇到一些设计问题，但我不知道是什么是真的很合适。一方面我经常听到我应该限制耦合和坚持单一职责，但当我这样做时，我常常发现它很困难到在需要时将信息获取到程序的一部分。为了例如，classSingerdefinitialize(name)@name=nameendattr:nameend那么Song应该是:classSongdefnew(singer)@singer=singerendend或classSongdefnew(singer_name)@singer_name=singer_nameendend后者耦合性小，按道理应该用。但如果我以后发现宋有什么需要了解更多歌手，我的

  6. ruby - 我需要从 facebook 游戏中抓取数据——使用 ruby - 2

    修改(澄清问题)我已经花了几天时间试图弄清楚如何从Facebook游戏中抓取特定信息；但是，我遇到了一堵又一堵砖墙。据我所知，主要问题如下。我可以使用Chrome的检查元素工具手动查找我需要的html-它似乎位于iframe中。但是，当我尝试抓取该iframe时，它​​是空的(属性除外):如果我使用浏览器的“查看页面源代码”工具，这与我看到的输出相同。我不明白为什么我看不到iframe中的数据。答案不是它是由AJAX之后添加的。(我知道这既是因为“查看页面源代码”可以读取Ajax添加的数据，也是因为我有b/c我一直等到我可以看到数据页面之后才抓取它，但它仍然不存在)。发生这种情况是因为

  7. ruby-on-rails - 与 ActiveMerchant 一起使用的最佳支付网关是什么？ - 2

    我需要使用ActiveMerchant库在我们的一个Rails应用程序中设置支付解决方案。尽管这个问题非常主观，但人们对主要网关(BrainTree、Authorize.net等)的体验如何？它必须:处理定期付款。有能力记入个人帐户。能够取消付款。有办法存储用户的付款详细信息(例如Authotize.netsCIM)。干杯 最佳答案 ActiveMerchant很棒，但在过去一年左右的时间里，我在使用它时发现了一些问题。首先，虽然某些网关可能会得到“支持”——但并非所有功能都包含在内。查看功能矩阵以确保完全支持您选择的网关-http

  8. ruby - 将 ruby​​ 哈希转换为数组的最佳方法是什么 - 2

    我有一个像这样的ruby​​散列{"stuff_attributes"=>{"1"=>{"foo"=>"bar","baz"=>"quux"},"2"=>{"foo"=>"bar","baz"=>"quux"}}}我想把它变成一个看起来像这样的散列{"stuff_attributes"=>[{"foo"=>"bar","baz"=>"quux"},{"foo"=>"bar","baz"=>"quux"}]}我还需要保留键的数字顺序，并且键的数量是可变的。上面是super简化的，但我在底部包含了一个真实的例子。执行此操作的最佳方法是什么？附言还需要递归就递归而言，这是我们可以假设的:1)

  9. Ruby 最佳实践 : working with classes - 2

    参见下面的示例，我想最好使用第二种方法，但第一种也可以。哪种方法最好，使用另一种的后果是什么？classTestdefstartp"started"endtest=Test.newtest.startendclassTest2defstartp"started"endendtest2=Test2.newtest2.start 最佳答案 我肯定会说第二种变体更有意义。第一个不会导致错误，但对象实例化完全过时且毫无意义。外部变量在类的范围内不可见:var="string"classAvar=A.newendputsvar#=>strin

  10. python - Ruby 或 Python 的 3d 游戏引擎？ - 2

    关闭。这个问题不符合StackOverflowguidelines.它目前不接受答案。要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于StackOverflow来说是偏离主题的，因为它们往往会吸引自以为是的答案和垃圾邮件。相反，describetheproblem以及迄今为止为解决该问题所做的工作。关闭9年前。Improvethisquestion是否有适用于这些的3d游戏引擎？

随机推荐