可以创建n个元素的ulam序列的快速算法-解网

问：

我一直在尝试解决代码战上的这个套路。我有一个算法，但它显然太慢了，无法通过测试。它可以在不到 2450 秒的时间内创建 1.6 个数字的序列。我不需要解决方案，而是需要提示或其他东西来帮助我更快地实现算法。

function ulamSequence(u0, u1, n) {
  // create an array with first two elements in it
  const seq = [u0, u1];
  
  // create a loop that checks if next number is valid and if it is, push it in seq
  num: for (let i = u1 + 1; seq.length < n; i++) {
    let sumCount = 0;
    for (let k = 0; k < seq.length - 1; k++) {
      if (seq.indexOf(i - seq[k]) > k && ++sumCount === 2) { continue num; }
    }
    sumCount === 1 ? seq.push(i) : "";
  }
  
  return seq;
}

JavaScript 性能循环序列

function ulamSequence(u0, u1, n) {
  const seq = [u0, u1];
  const set = new Set(seq);

  for (let i = u1 + 2; seq.length < n; i++) {
    let sumCount = 0;
    for (let k = 0; k < seq.length - 1; k++) {
      if (set.has(i - seq[k])) {
        sumCount++;
        if (sumCount === 2) {
          continue;
        }
      }
    }
    if (sumCount === 1) {
      seq.push(i);
      set.add(i);
    }
  }
  return seq;
}

这里有一个想法：有一个数组，以便保持的可能求和数。例如，对于 U（1,2）将是 1 和 2 （1+4， 2+3）。在每个步骤中，找到最小值，以便和 .添加到结果中，然后将其与所有先前的项目相加并相应地更新。sumssums[N]Nsums[3]sums[5]NN > last itemsums[N] == 1Nsums

function ulam(u0, u1, len) {
    let seq = [u0, u1]
    let sums = []
    let last = u1

    sums[u0 + u1] = 1

    while (seq.length < len) {
        last += 1
        while (sums[last] !== 1) {
            last += 1
        }
        for (let n of seq) {
            let s = n + last
            sums[s] = (sums[s] || 0) + 1
        }
        seq.push(last)
    }
    return seq
}

console.time()
ulam(1, 2, 2450)
console.timeEnd()

上一个：我有一个循环播放的动画图像序列。如何将其连接到在播放和暂停之间切换的按钮？

下一个：JavaScript 承诺链，提取不按顺序

可以创建n个元素的ulam序列的快速算法

Fast Algorithm That Can Create Ulam Sequence of n Elements

评论

评论