草庐IT

c++ - 他贪心吗？

coder 2024-02-11 原文

我正在解决来自 LeetCode.com 的问题:

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false.

投票最多的解决方案之一 ( here ) 表示以下是使用贪婪方法:

bool canJump(int A[], int n) {
    int last=n-1,i,j;
    for(i=n-2;i>=0;i--){
        if(i+A[i]>=last)last=i;
    }
    return last<=0;
}

我有两个问题:

  1. 为此使用贪心算法背后的直觉是什么？
  2. 上面的解怎么算贪心算法？

我认为这可以通过动态规划来解决。我知道 DP 可以解决的问题可以用贪心法解决，但是这个特殊问题背后的直觉是什么使得用贪心法解决更有意义？

这SO question一定程度上凸显了这种差异。我知道这可能有点多，但如果可能的话，有人可以在这种情况下回答这个问题吗？我将不胜感激。

谢谢。

编辑:我认为造成我困惑的原因之一是输入 [3,3,1,0,4] .根据贪心范式，当 i=0 时，我们不会进行大小为 3 (A[0]) 的跳跃，以便贪婪地达到输出？但这样做实际上是不正确的。

最佳答案

根据维基百科:

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

在这里，我想提请您注意关键词，每个阶段的局部最优选择，这使得算法范式变得贪婪。

Q1. What is the intuition behind using a greedy algorithm for this?

由于在这道题中，我们只关心是否可以到达数组的最后一个索引，所以可以使用贪心算法。贪婪算法会在每一步选择最优选择(跳得最大)，并在最后检查最大索引是否可以到达终点。

比如说，如果我们需要找出每个索引处的跳转大小以到达终点或需要优化跳转次数以到达终点，那么直接使用贪心算法将达不到我们的目的。

Q2. How is the above solution a greedy algorithm?

上面代码中的 if 条件 - if(i+A[i]>=last)last=i; 使算法变得贪婪，因为我们取了最大值如果可能就跳转 (i+A[i]>=last)。

提供的分析here可能对你有帮助。

编辑

让我们谈谈您提到的输入 - [3,3,1,0,4]。

  • 当 i=0 时，算法检查我们可以从 i=0 到达的最大索引是多少。
  • 然后我们将移动到下一个索引并检查我们可以从 i=1 到达的最大索引是多少。由于我们移动到 i=1，因此可以保证我们可以从索引 0 到达索引 1(无论跳跃大小是多少)。

请注意，在这个问题中，我们不关心是否应该在 i=0 处进行大小为 3 的跳跃，尽管我们知道这不会帮助我们到达终点。我们关心的是我们是否可以通过跳跃到达终点或超越终点指标。

关于c++ - 他贪心吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47169611/

amp43codestrongsectionc++algorithmdynamic-programminggreedy

有关c++ - 他贪心吗？的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  3. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  4. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  5. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  6. ruby - Sinatra + Heroku + Datamapper 使用 dm-sqlite-adapter 部署问题 - 2

    出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t

  7. ruby - Ruby 中字符串运算符 + 和 << 的区别 - 2

    我是Ruby和这个网站的新手。下面两个函数是不同的，一个在函数外修改变量，一个不修改。defm1(x)x我想确保我理解正确-当调用m1时，对str的引用被复制并传递给将其视为x的函数。运算符当调用m2时，对str的引用被复制并传递给将其视为x的函数。运算符+创建一个新字符串，赋值x=x+"4"只是将x重定向到新字符串，而原始str变量保持不变。对吧？谢谢 最佳答案 String#+::str+other_str→new_strConcatenation—ReturnsanewStringcontainingother_strconc

  8. ruby - rails 3.2.2(或 3.2.1)+ Postgresql 9.1.3 + Ubuntu 11.10 连接错误 - 2

    我正在使用PostgreSQL9.1.3(x86_64-pc-linux-gnu上的PostgreSQL9.1.3，由gcc-4.6.real(Ubuntu/Linaro4.6.1-9ubuntu3)4.6.1，64位编译)和在ubuntu11.10上运行3.2.2或3.2.1。现在，我可以使用以下命令连接PostgreSQLsupostgres输入密码我可以看到postgres=#我将以下详细信息放在我的config/database.yml中并执行“railsdb”，它工作正常。开发:adapter:postgresqlencoding:utf8reconnect:falsedat

  9. ruby - 在 Ruby + Chef 中检查现有目录失败 - 2

    这是我在ChefRecipe中的一blockRuby:#ifdatadirdoesn'texist,moveoverthedefaultoneif!File.exist?("/vol/postgres/data")execute"mv/var/lib/postgresql/9.1/main/vol/postgres/data"end结果是:Executingmv/var/lib/postgresql/9.1/main/vol/postgres/datamv:inter-devicemovefailed:`/var/lib/postgresql/9.1/main'to`/vol/post

  10. ruby-on-rails - 使用 Pow 作为服务器在 RubyMine 中调试 - Ruby 2.1.1 + Rails 4 - 2

    我已经开始使用RubyMine6。我正在处理Rails4、Ruby2.1.1项目。我无法找到如何使用Pow作为服务器调试到RubyMine。你能给我指明正确的方向吗？ 最佳答案 我能够使用远程调试从RubyMine进行调试。我正在使用RubyMine6、Rails3、Ruby2.1.1。首先创建一个.powenv文件并添加:exportRUBY_DEBUG_PORT=1234exportPOW_WORKERS=1将以下gem添加到您的Gemfile:gem'ruby-debug-ide'gem'debase'创建一个新的初始化器st

随机推荐