javascript - how can I make this faster. By removing one element from an array, check if array is increasing seuence

Question

Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

Example

For sequence = [1, 3, 2, 1], the output should be almostIncreasingSequence(sequence) = false;

There is no one element in this array that can be removed in order to get a strictly increasing sequence.

For sequence = [1, 3, 2], the output should be almostIncreasingSequence(sequence) = true.

You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

[input] array.integer sequence

Guaranteed constraints: 2 ≤ sequence.length ≤ 105, -105 ≤ sequence[i] ≤ 105.

[output] boolean

function 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])

 }

My code is slow. How can be improved.

标签： javascriptarray-algorithms

Answer 1

如果不是这个（您的链接不起作用并且答案未根据要求更新）。那么要求是：

给定一个整数序列，检查是否有可能通过从其中删除不超过一个元素来获得一个严格递增的序列。

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

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

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

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

如果 checkFunction 失败，则有 4 种情况：

1. [1,2,3,2] last 和 second last 元素失败，只删除最后一个元素
2. [1,10,2,3] 如果当前索引为 1（数字 10），则当前将使用 2 检查并失败。最好删除 10（当前）。
3. [1,2,0,3] 如果当前索引为 1（数字 2），则 2 将被检查为 0 并失败。删除 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)");

为了完整起见，我添加了以下代码，因为我的代码采用的 maxMissed 可能高于 1。在您的情况下，您只能错过一个，但如果您可以有多个未命中，则以下情况将错误地失败[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)");