javascript - 我怎样才能让它更快。通过从数组中删除一个元素，检查数组是否在增加序列

Question

给定一个整数序列作为数组，确定是否可以通过从数组中删除不超过一个元素来获得严格递增的序列。

例子

对于序列 = [1, 3, 2, 1]，输出应该是 almostIncreasingSequence(sequence) = false;

为了得到严格递增的序列，这个数组中没有一个元素可以被删除。

对于序列 = [1, 3, 2]，输出应该是 almostIncreasingSequence(sequence) = true.

您可以从数组中删除 3 以获得严格递增的序列 [1, 2]。或者，您可以删除 2 以获得严格递增的序列 [1, 3]。

[输入]数组.整数序列

保证约束: 2 ≤ sequence.length ≤ 105, -105 ≤ sequence[i] ≤ 105.

[输出] bool 值

函数 almostIncreasingSequence(arr) {

for (let i = 0; i < arr.length; i++) {
    if (isSeq(arr.slice(0, i).concat(arr.slice(i + 1)))) {
        return true;
        break;
    }

}
return false

function isSeq(subseq) {
    var sliced1 = subseq.slice(0, subseq.length - 1);
    var sliced2 = subseq.slice(1);
    return sliced1.every((el, index) => el < sliced2[index])

 }

我的代码很慢。如何改进。

Answer 1

如果不是this one (您的链接无效，答案未根据要求更新)。那么要求是:

Given a sequence of integers, check whether it is possible to obtain a strictly increasing sequence by erasing no more than one element from it.

事实证明这比预期的要棘手。有一些时间来解决一些失败的边缘情况，但实际上无法在代码战或代码战上进行测试，因为如果没有服务器错误，链接将无法加载。

将 checkFunction 传递到将检查序列(数组)的函数中，此 checkFunction 将接收数组中的当前元素和下一个元素。在我们的例子中，checkFunction 将检查当前元素是否小于下一个元素:

const increasing = isInSequence((current,next)=>current<next);

它使用 isInSequece 的返回值，它是一个部分应用的函数，checkFunction 设置为检查当前元素小于下一个元素的函数。

如果checkFunction失败那么有4种情况:

1. [1,2,3,2] 最后一个和倒数第二个元素失败，只删除最后一个元素
2. [1,10,2,3] 如果当前索引为 1(数字 10)，则将使用 2 检查当前索引并失败。最好删除 10 个(当前)。
3. [1,2,0,3] 如果当前索引为 1(数字 2)，则将使用 0 检查 2 并失败。删除 0 最好不是当前数字，而是下一个
4. [2,1,2,3] 第一个和第二个元素失败，先删除。

情况 1 和 4 不需要 checkFunction，因为可以根据 currentIndex 和 array.length 决定删除什么数字。在情况 2 和 3 中，checkFunction 与上一个和下一个值一起使用，以确定是否最好删除当前项目或下一个项目:

//compare A with C in ABC where A is previous, B is current and C is next
//  we just failed to compare current with next (B with C)
array=(checkFunction(array[currentIndex-1],array[next]))
  //A with C passed, get rid of B
  ? [array[currentIndex-1]].concat(array.slice(next))
  //A with C failed, get rid of C (A with B passed)
  : [array[currentIndex]].concat(array.slice(next+1))

完整代码如下:

const isInSequence = checkFunction => (array,maxMissed) => {
  const recur = (missed,currentIndex,array) => {//compare lastIndex to next index
    if(currentIndex>=array.length-1) return true;//there is no next index to copare to
    var next = currentIndex+1;
    if(!checkFunction(array[next-1],array[next])){//compare
      missed++;
      if(next>=array.length-1){
        //compare to the last one failed, remove last
        array=array.slice(-1);
      }else if(currentIndex-1>=0) {
        //compare A with C in ABC where A is previous, B is current and C is next
        //  we just failed to compare current with next (B with C)
        array=(checkFunction(array[currentIndex-1],array[next]))
          //A with C passed, get rid of B
          ? [array[currentIndex-1]].concat(array.slice(next))
          //A with C failed, get rid of C (A with B passed)
          : [array[currentIndex]].concat(array.slice(next+1))
      }else{
        //There is no previous element from current so remove current
        array = array.slice(currentIndex);
      }
      next = 0;
    }
    if(missed>maxMissed){
      return false;//too many misses, return false
    }
    //recursively call itself
    return recur(missed,next,array);
  }
  return recur(0,0,array);
}

const test = (expected,value,message) =>
  (expected!==value)
    ? console.error("Failed, expected:",expected,"got:",value,"message:",message)
    : console.info("Passed:",message)
;
console.clear();
//partially apply isInSequence with a function that takes 2 arguments
//  and checks if argument one is smaller than argument 2
const increasing = isInSequence((current,next)=>current<next);
test(true,increasing([1,2,3],0),"1,2,3 should return true");
test(false,increasing([1,2,3,2],0),"1,2,3,2 should return false");
test(false,increasing([3,2],0),"3,2 should return false");
test(true,increasing([2,3],0),"2,3 should return true");
test(true,increasing([],0),"[] should return true");
test(true,increasing([2],0),"[2] should return true");
test(true,increasing([2,3,2],1),"2,3,2 should return true (can remove last one)");
test(true,increasing([2,1],1),"2,1 should return true (can miss one)");
test(false,increasing([1,2,1,3,2],1),"1,2,1,3,2 should return false (can only miss one)");
test(false,increasing([4,5,6,1,2,3],1),"4,5,6,1,2,3 should return false");
test(true,increasing([4,5,100,6,7],1),"4,5,100,6,7 should return true (remove 100 would work)");
test(false,increasing([5,1,5,2,3],1),"5,1,5,2,5,3 should return false");
test(true,increasing([1,2,0,3,2],2),"1,2,0,3,2 should return true (can miss two)");

为了完整性，我添加了以下代码，因为我的代码采用了可以高于 1 的 maxMissed。在您的情况下，您只能错过一个，但如果您可以错过多个，则以下情况将错误地失败 [0,1,100,101,2,3,4,5] 允许 2 次失误:

const showDebug = false;
const debugLog = function(){
  if(showDebug){
    console.log.apply(window,Array.from(arguments));
  }
}
const isInSequence = checkFunction => (array,maxMissed) => {
  const recur = (missed,currentIndex,array) => {//compare lastIndex to next index
    debugLog("array:",array,"missed:",missed,"index:",currentIndex);
    if(currentIndex>=array.length-1) return true;//there is no next index to compare to
    var next = currentIndex+1;
    if(!checkFunction(array[next-1],array[next])){//compare
      debugLog("------------miss");
      missed++
      if(missed>maxMissed){
        return false;//too many misses, return false
      }
      if(next>=array.length-1){
        //compare to the last one failed, remove last
        array=array.slice(-1);
      }else if(currentIndex===0) {
        //There is no previous element from current so remove current
        array = array.slice(currentIndex+1);
      }else{
        //try again with current or next element removed, if either returns true
        //  then return true
        return recur(
          missed,0,array.slice(0,currentIndex).concat(array.slice(currentIndex+1))
        ) || recur(
          missed,0,array.slice(0,next).concat(array.slice(next+1))
        )
      }
      next = 0;
    }
    //recursively call itself
    return recur(missed,next,array);
  }
  return recur(0,0,array);
}

const test = (expected,value,message) =>
  (expected!==value)
    ? console.error("Failed, expected:",expected,"got:",value,"message:",message)
    : console.info("Passed:",message)
;
console.clear();
//partially apply isInSequence with a function that takes 2 arguments
//  and checks if argument one is smaller than argument 2
const increasing = isInSequence((current,next)=>current<next);
test(true,increasing([3,2,3],1),"3,2,3 should return true");
test(true,increasing([1,2,3],0),"1,2,3 should return true");
test(false,increasing([1,2,3,2],0),"1,2,3,2 should return false");
test(true,increasing([2,3],0),"2,3 should return true");
test(true,increasing([],0),"[] should return true");
test(true,increasing([2],0),"[2] should return true");
test(true,increasing([2,3,2],1),"2,3,2 should return true (can remove last one)");
test(true,increasing([2,1],1),"2,1 should return true (can miss one)");
test(false,increasing([1,2,1,3,2],1),"1,2,1,3,2 should return false (can only miss one)");
test(false,increasing([4,5,6,1,2,3],1),"4,5,6,1,2,3 should return false");
test(true,increasing([4,5,100,6,7],1),"4,5,100,6,7 should return true (remove 100 would work)");
test(false,increasing([5,1,5,2,3],1),"5,1,5,2,5,3 should return false");
test(true,increasing([1,2,0,3,2],2),"1,2,0,3,2 should return true (can miss two)");
test(false,increasing([3,2],0),"3,2 should return false");

// less performant version to fix this edge case (not your problem since only 1 can fail in your case)
test(true,increasing([0,1,100,101,2,3,4,5],2),"0,1,100,101,2,3,4,5 should return true (can miss two)");