草庐IT

【算法刷题】贪心算法题型及方法归纳

辰阳星宇 2024-06-29 原文

贪心算法特点

从局部最优解推出全局最优，并且想不出来反例。贪心没有明确有规律的套路，而对于贪心的难题，更多的是难在思路上，要用一些转化问题的思维方法，然后，再根据局部最优解推出全局最优。

参考文章：贪心算法理论基础

1、发饼干

先排序，按饼干从小到大的顺序，依次分给从小到大排序的小朋友。

127、【贪心算法】leetcode ——455. 分发饼干：DFS+双指针法（C++版本）

2、0 水准线

  1. count用来记录当前子序列的相加和，当count大于0时，继续相加。当count小于或等于0时，重新开始选取子序列。
    以count是否为0判定的原因：若后续为正数时，没有这个负数更好，若后续为负数时，越加只会越小）
    129、【贪心算法】leetcode ——53. 最大子数组和（贪心算法）（C++版本）

  2. 满足条件的差值总和一定大于等于0，起始点之后区间一定大于等于0，区间小于时，更新起始点。
    134、【贪心算法】leetcode ——134. 加油站（贪心策略）（C++版本）

3、高度差模型问题

将问题图形化为高度差模型，根据题中会有的情况，出现某一坡度情形时，执行对应的情况。

  1. 获取每个“小山峰”（前升坡，后降坡）
    128、【贪心算法】leetcode ——376. 摆动序列（C++版本）：判定之前高度差和当前高度差的正负情况

  2. 获取每个“上升坡度”
    130、【贪心算法/动态规划】leetcode ——122. 买卖股票的最佳时机 II（贪心算法）（C++版本）：升坡时进行一次买卖，降坡或平坡时只买不卖。
    股票买卖一：167、【贪心算法】AcWing ——83. 股票的最大利润 （C++版本），找到一个最大值和最大值前方的最小值。

4、区间问题

（1）区间范围问题

将问题转化为区间覆盖问题，更新区间右边界，看最大区间能否覆盖到最后一个位置

  1. 每次获取最大跳跃步数
    131、【贪心算法】leetcode ——55. 跳跃游戏（贪心策略）（贪心算法）（C++版本）：每次在区间范围内移动，获取最大可覆盖范围

  2. 在当前可获取的最大跳跃范围内，找到最优位置
    132、【贪心算法】leetcode ——45. 跳跃游戏 II（贪心策略）（C++版本） ：在给定的跳跃范围内寻找最优跳跃位置（后续跳跃距离更远），到达最大范围边界时，进行跳跃更新。

  3. 更新最远区间边界
    140、【贪心算法】leetcode ——763. 划分字母区间（区间边界更新）（C++版本）：先记录每个字母的最远位置，每获取一个字母就查看是否会有更远区间，更新区间边界，到达边界时，更新起始边界继续遍历。

（2）区间重叠问题

先按从打到小或从小到大排序，每次对前后两个区间关系进行判断，对重叠区间或非重叠进行操作。

两区间关系：
（1）不重叠

（2）交叉重叠

（3）包含重叠

  1. 更新区间
    138、【贪心算法】leetcode ——452. 用最少数量的箭引爆气球（贪心重叠问题）（C++版本）：重叠时候更新最后一个气球的右区间，不重叠时弓箭数加一。

  2. 法一： 以左边界排序，更新右边界，法二： 以有边界排序，记录不重叠区间
    139、【贪心算法】leetcode ——435. 无重叠区间（更新区间+记录不重叠区间）（C++版本）

  3. 合并重叠区间
    141、【贪心算法】leetcode ——56. 合并区间（区间重叠解法+双指针解法）（C++版本）：前后量区间对比，有重叠合并，无重叠，将前面的加入结果集。

5、多维度问题

需要考虑多个条件，若仅一趟遍历会很复杂，因此将每一个维度分成一趟遍历情况。

  1. 左值大于右值，左值小于右值，两个维度
    135、【贪心算法】leetcode ——135. 分发糖果（多维度贪心）（C++版本）：第一趟，从左到右遍历，对于左值<右值，进行加一。第二趟，再从右到左遍历，对于右值＞左值，取max(上述已完成数值， 右值+1)。

  2. 身高从大到小，大于此身高的个数，两个维度
    137、【贪心算法】leetcode ——406. 根据身高重建队列（多维度贪心）（C++版本）：第一趟，按从大到小排列。第二趟，在第一趟的基础上，将人数作为插入下标，插入结果集。

6、模拟变化

  1. K次取反
    133、【贪心算法】leetcode ——1005. K 次取反后最大化的数组和（模拟变化+贪心策略）（C++版本）：先变负数，若K对负数操作完后还不为0，对最小非负数进行操作，奇数时取反，偶数时不变。

  2. 根据各种情况进行操作
    135、【贪心算法】leetcode ——860. 柠檬水找零（贪心策略）（C++版本）：先找大钱，再找小钱

7、单调递增的数字

根据最大递增数的特性，当不满足情况时，改变第i位为9，第i - 1位的数值位数减一。
143、【回溯算法】leetcode ——738. 单调递增的数字：暴力法+贪心法（C++版本）

题型算法xffxff0cxff0贪心算法leetcode

有关【算法刷题】贪心算法题型及方法归纳的更多相关文章

  1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

    我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

  2. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  3. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  4. ruby - Facter::Util::Uptime:Module 的未定义方法 get_uptime (NoMethodError) - 2

    我正在尝试设置一个puppet节点，但ruby​​gems似乎不正常。如果我通过它自己的二进制文件(/usr/lib/ruby/gems/1.8/gems/facter-1.5.8/bin/facter)在cli上运行facter，它工作正常，但如果我通过由ruby​​gems(/usr/bin/facter)安装的二进制文件，它抛出:/usr/lib/ruby/1.8/facter/uptime.rb:11:undefinedmethod`get_uptime'forFacter::Util::Uptime:Module(NoMethodError)from/usr/lib/ruby

  5. Ruby 方法() 方法 - 2

    我想了解Ruby方法methods()是如何工作的。我尝试使用“ruby方法”在Google上搜索，但这不是我需要的。我也看过ruby​​-doc.org，但我没有找到这种方法。你能详细解释一下它是如何工作的或者给我一个链接吗？更新我用methods()方法做了实验，得到了这样的结果:'labrat'代码classFirstdeffirst_instance_mymethodenddefself.first_class_mymethodendendclassSecond使用类#returnsavailablemethodslistforclassandancestorsputsSeco

  6. ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2

    我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer

  7. ruby - Highline 询问方法不会使用同一行 - 2

    设置:狂欢ruby1.9.2高线(1.6.13)描述:我已经相当习惯在其他一些项目中使用highline，但已经有几个月没有使用它了。现在，在Ruby1.9.2上全新安装时，它似乎不允许在同一行回答提示。所以以前我会看到类似的东西:require"highline/import"ask"Whatisyourfavoritecolor?"并得到:Whatisyourfavoritecolor?|现在我看到类似的东西:Whatisyourfavoritecolor?|竖线(|)符号是我的终端光标。知道为什么会发生这种变化吗？ 最佳答案

  8. ruby - 主要 :Object when running build from sublime 的未定义方法 `require_relative' - 2

    我已经从我的命令行中获得了一切，所以我可以运行rubymyfile并且它可以正常工作。但是当我尝试从sublime中运行它时，我得到了undefinedmethod`require_relative'formain:Object有人知道我的sublime设置中缺少什么吗？我正在使用OSX并安装了rvm。 最佳答案 或者，您可以只使用“require”，它应该可以正常工作。我认为“require_relative”仅适用于ruby​​1.9+ 关于ruby-主要:Objectwhenrun

  9. ruby - 多个属性的 update_column 方法 - 2

    我有一个具有一些属性的模型:attr1、attr2和attr3。我需要在不执行回调和验证的情况下更新此属性。我找到了update_column方法，但我想同时更新三个属性。我需要这样的东西:update_columns({attr1:val1,attr2:val2,attr3:val3})代替update_column(attr1,val1)update_column(attr2,val2)update_column(attr3,val3) 最佳答案 您可以使用update_columns(attr1:val1,attr2:val2

  10. ruby - 检查方法参数的类型 - 2

    我不确定传递给方法的对象的类型是否正确。我可能会将一个字符串传递给一个只能处理整数的函数。某种运行时保证怎么样？我看不到比以下更好的选择:defsomeFixNumMangler(input)raise"wrongtype:integerrequired"unlessinput.class==FixNumother_stuffend有更好的选择吗？ 最佳答案 使用Kernel#Integer在使用之前转换输入的方法。当无法以任何合理的方式将输入转换为整数时，它将引发ArgumentError。defmy_method(number)

随机推荐