草庐IT

javascript - 动态规划 : Code Wars: twice linear: algorithm times out

coder 2024-07-17 原文

我在 Code Wars 中遇到了卡塔: https://www.codewars.com/kata/5672682212c8ecf83e000050/train/javascript
这个想法是创建一个数字序列，其中每个数字都是按照以下两个公式隐式创建的:

y=2x + 1  
z=3x + 1

x 是序列中的当前数字。

从 1 开始，序列会像这样增长:

sequence = [1]  
x = 1  
y = 2*1 +1 = 3  
z = 3*1 + 1 = 4  
leading to sequence = [1, 3, 4]

将它应用到下一个数字会导致:

x = 3  
y = 2*3 + 1 = 7  
z = 3*3 + 1 = 10  
leading to sequence = [1, 3, 4, 7, 10]  

x = 4  
y = 2*4 + 1 = 9  
z = 3*4 + 1 = 13  
sequence [1, 3, 4, 7, 9, 10, 13]

等等。请注意，我在最后一步对序列进行了排序，因为 x=4(9 和 13)的结果必须与 x=3(7 和 10)的结果混合以保持有序序列。

[1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

我能够正确解决问题，但实现应该是高效的，但我超时了。我的代码:

function dblLinear(n) {
  cache = {};
  cache[0] = 1;
  res = [1];
  lengthCounter = 0
  if (n === 0) {
    return 1;
  }
  for (var i = 1; i < n + 10; i++) {
    //console.log("i ", i)
    if (cache[i] === undefined && res.includes(i)) {
      //console.log('i: ', i, ' el1: ', i * 2 + 1, ' el2: ', i * 3 + 1);
      cache[i] = [i * 2 + 1, i * 3 + 1]
      if (!res.includes(i * 2 + 1)) {
        res.push(i * 2 + 1);
      }
      if (!res.includes(i * 3 + 1)) {
        res.push(i * 3 + 1);
      }
      //console.log("res ", res)
    }
    if (res.length !== lengthCounter) {
      var arrStart = res.slice(0, Math.floor(res.length / 2));
      var arrEnd = res.slice(Math.floor(res.length / 2), res.length)
      arrEnd.sort(function(a, b) {
        return a - b;
      });
      res = arrStart.concat(arrEnd)
      lengthCounter = res.length
    }
  }
  //console.log('res ', res);
  return res[n];
}

正如您在我的代码中看到的那样，我尝试了一些简单的技巧来提高效率，但我猜我需要更多的速度增益。你认为问题是什么，我怎样才能提高效率？

任何帮助将不胜感激!

干杯

曼纽尔

最佳答案

这个问题可以在 O(n) 中解决。这个想法是跟踪最后生成的元素并添加两种可能性中较小的一种，因此元素按顺序添加。此代码轻松通过所有测试。

function dblLinear(n) {
    let u = [1], x = 0, y = 0
    for (let i = 0; i < n; i++) {
        let nextX = 2 * u[x] + 1, nextY = 3 * u[y] + 1
        if (nextX <= nextY) {
            u.push(nextX)
            x++
            if (nextX == nextY)
                y++
        } else {
            u.push(nextY)
            y++
        }
    }
    return u[n]
}

console.log(dblLinear(10) + " = " + 22)
console.log(dblLinear(20) + " = " + 57)
console.log(dblLinear(30) + " = " + 91)
console.log(dblLinear(50) + " = " + 175)
console.log(dblLinear(100) + " = " + 447)

关于javascript - 动态规划 : Code Wars: twice linear: algorithm times out，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49360883/

javascriptalgorithmsectionresconsoleperformancedynamic-programming

有关javascript - 动态规划 : Code Wars: twice linear: algorithm times out的更多相关文章

  1. ruby - 在 Ruby 中动态创建数组 - 2

    有没有办法在Ruby中动态创建数组？例如，假设我想遍历用户输入的书籍数组:books=gets.chomp用户输入:"TheGreatGatsby,CrimeandPunishment,Dracula,Fahrenheit451,PrideandPrejudice,SenseandSensibility,Slaughterhouse-Five,TheAdventuresofHuckleberryFinn"我把它变成一个数组:books_array=books.split(",")现在，对于用户输入的每一本书，我想用Ruby创建一个数组。伪代码来做到这一点:x=0books_array.

  2. ruby - 是否可以将 IRB 提示配置为动态更改？ - 2

    我想在IRB中浏览文件系统并让提示更改以反射(reflect)当前工作目录，但我不知道如何在每个命令后进行提示更新。最终，我想在日常工作中更多地使用IRB，让bash溜走。我在我的.irbrc中试过这个:require'fileutils'includeFileUtilsIRB.conf[:PROMPT][:CUSTOM]={:PROMPT_N=>"\e[1m:\e[m",:PROMPT_I=>"\e[1m#{pwd}>\e[m",:PROMPT_S=>"FOO",:PROMPT_C=>"\e[1m#{pwd}>\e[m",:RETURN=>""}IRB.conf[:PROMPT_MO

  3. ruby-on-rails - 使用 javascript 更改数据方法不会更改 ajax 调用用户的什么方法？ - 2

    我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的

  4. ruby-on-rails - carrierwave:在序列化动态属性上安装 uploader - 2

    首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟

  5. ruby - 在 Ruby 中动态生成多维数组 - 2

    我正在尝试动态构建一个多维数组。我想要的基本上是这样的(为简单起见写出来):b=0test=[[]]test[b]这给了我错误:NoMethodError:undefinedmethod`test=[[],[],[]]而且它工作正常，但在我的实际使用中，我不会事先知道需要多少个数组。有一个更好的方法吗？谢谢 最佳答案 不需要像您正在使用的索引变量。只需将每个数组附加到您的test数组:irb>test=[]=>[]irb>test[["a","b","c"]]irb>test[["a","b","c"],["d","e","f"]]

  6. ruby-on-rails - 使用 gmaps4rails 动态加载谷歌地图标记 - 2

    如何只加载map边界内的标记gmaps4rails？当然，在平移和/或缩放后加载新的。与此直接相关的是，如何获取map的当前边界和缩放级别？ 最佳答案 我是这样做的，我只在用户完成平移或缩放后替换标记，如果您需要不同的行为，请使用不同的事件监听器:在你看来(index.html.erb):{"zoom"=>15,"auto_adjust"=>false,"detect_location"=>true,"center_on_user"=>true}},false,true)%>在View的底部添加:functiongmaps4rail

  7. ruby - 动态方法链？ - 2

    如何在对象上调用方法名称的嵌套哈希？例如，给定以下哈希:hash={:a=>{:b=>{:c=>:d}}}我想创建一个方法，给定上面的散列，执行以下操作:object.send(:a).send(:b).send(:c).send(:d)我的想法是我需要从一个未知的关联中获取一个特定的属性(这个方法不知道，但程序员知道)。我希望能够指定一个方法链来以嵌套哈希的形式检索该属性。例如:hash={:manufacturer=>{:addresses=>{:first=>:postal_code}}}car.execute_method_hash(hash)=>90210

  8. ruby - 如何使用 method_missing 动态声明方法？ - 2

    我有一个ruby​​程序，我想接受用户创建的方法，并使用该名称创建一个新方法。我试过这个:defmethod_missing(meth,*args,&block)name=meth.to_sclass我收到以下错误:`define_method':interningemptystring(ArgumentError)in'method_missing'有什么想法吗？谢谢。编辑:我以不同的方式让它工作，但我仍然很好奇如何以这种方式做到这一点。这是我的代码:defmethod_missing(meth,*args,&block)Adder.class_evaldodefine_method

  9. ruby - 动态扩展现有方法或覆盖 ruby​​ 中的发送方法 - 2

    假设我们有A、B、C类。Adefself.inherited(sub)#metaprogramminggoeshere#takeclassthathasjustinheritedclassA#andforfooclassesinjectprepare_foo()as#firstlineofmethodthenrunrestofthecodeenddefprepare_foo#=>prepare_foo()neededhere#somecodeendendBprepare_foo()neededhere#somecodeendend如您所见，我正在尝试将foo_prepare()调用注入

  10. ruby - 使用 jbuilder 创建具有动态哈希键的 JSON - 2

    这里我想输出带有动态组名的json而不是单词组@tickets.eachdo|group,v|json.group{json.array!vdo|ticket|json.partial!'tickets/ticket',ticket:ticketend}end@ticket是这样的散列{a:[....],b:[.....]}我想要这样的输出{a:[.....],b:[....]} 最佳答案 感谢@AntarrByrd，这个问题有类似的答案:JBuilderdynamickeysformodelattributes使用上面的逻辑我已经

随机推荐