我怎样才能更快地做到这一点。通过从数组中删除一个元素，检查数组是否增加了seuence [英] how can I make this faster. By removing one element from an array, check if array is increasing seuence

问题描述

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

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.

示例

对于sequence = [1,3,2,1]，输出应为
almostIncreasingSequence（sequence）= false;

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.

对于sequence = [1， 3，2]，输出应该是
almostIncreasingSequence（sequence）= true。

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

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

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

[input] array.integer sequence

保证约束：
2≤sequence.length≤105，
-105≤sequence[i]≤105。

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

[输出] boolean

[output] boolean

函数almostIncreasingSequence（arr）{

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.

推荐答案

如果不是这个（你的链接不起作用，答案没有按要求更新）。然后要求是：

If it't this one (your link didn't work and answer isn't updated with requirements). Then the requirements are:

给定一系列整数，检查是否可以获得严格增加通过从中删除不超过一个元素的顺序。

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.

这比预期更棘手。有一些时间来解决一些失败的边缘情况，但实际上无法测试代码战或代码战，因为没有服务器错误就不会加载链接。

This turned out to be trickier than expected. Had some time to work out some failing edge cases but can't actually test on codewars or codefights because the links won't load without server errors.

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

Pass a checkFunction into a function that will check sequence (array) this checkFunction will receive current element in array and next element. In our case checkFunction will check if current element is smaller than next element:

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

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

That uses the return value of isInSequece which is a partially applied function with the checkFunction set to a function checking current element smaller than next.

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

If checkFunction fails then there are 4 situations:

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. [1,2,3,2] Last and second last element fails, just remove the last element
2. [1,10,2,3] If current index is 1 (the number 10) then current would be checked with 2 and fail. Removing 10 (current) would be best.
3. [1,2,0,3] If current index is 1 (the number 2) then 2 would be checked with 0 and fail. Removing 0 would be best not the current number but the next
4. [2,1,2,3] First and second element fails, just remove first.

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

Situation 1 and 4 does not need the checkFunction as the decision of what number to remove can be made depending on the currentIndex and array.length. In situation 2 and 3 the checkFunction is used with previous and next value to determine if it's best to remove the current or the next item:

//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次失误：

The following code I've added for completeness since my code takes a maxMissed that can be higher than 1. In your case you can only miss one but if you can have more than one misses the following case would wrongfully fail [0,1,100,101,2,3,4,5] with 2 misses allowed:

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)");

这篇关于我怎样才能更快地做到这一点。通过从数组中删除一个元素，检查数组是否增加了seuence的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！