几乎增加序列 - Javascript

Question

大家好，我在学习算法和数据结构时同时使用 Codefights，但我似乎无法解决这个问题。

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

我的代码由于性能而失败，我有一个大致的想法，为什么要考虑复制原始数组并循环遍历两者。但我想不出更优化的方法。

function almostIncreasingSequence(sequence) {
    let result = false;
    for(let i = 0; i < sequence.length; i++) {
        let newSequence = [...sequence]
        newSequence.splice(i,1)
        result = isArraySequential(newSequence)
        if (result) {
            return result;
        }
    }
        return result;
}

function isArraySequential(array) {
    let isSequential = true;
    for(let i = 0; i < array.length; i++) {
        if(i == array.length - 1) {return isSequential}
         if (array[i + 1] < array[i] || array[i + 1] == array[i]) {
            return !isSequential;
        }
    }
}

Answer 1

您不需要经常检查整个数组，也不需要使用多个循环。

问题可以分解为更小的问题。对于列表中的每个元素...

• 当前元素是否大于最后一个（增加）？
  • 是的...
    • 好的！我们不需要做任何事情。
  • 不...
    • 这已经发生了吗？如果是这样，它几乎不会增加。
    • 如果我们删除前一个项目，周围的项目是否固定？
    • 不？如果我们删除当前项目呢？
    • 还是不行？那么这意味着我们不能一步解决这个问题。几乎没有增加。

代码看起来像这样：

function almostIncreasingSequence(sequence) {
  let invalidItemsCount = 0;
  
  for (let i = 1; i < sequence.length; i++) {
    if (sequence[i] <= sequence[i-1]) {
      invalidItemsCount++;
      if (invalidItemsCount > 1) return false;
      if (sequence[i] <= sequence[i-2] && sequence[i+1] <= sequence[i-1]) return false;
    }
  }
  
  return true;
}

var test1 = [0,1,2,3,4,7,6,7,8,9,10];
var test2 = [0,1,2,4,3,4,5,7,6,7,8,9,10];

console.log(almostIncreasingSequence(test1));
console.log(almostIncreasingSequence(test2));

评论版：

function almostIncreasingSequence(sequence) {
  //Keep track of how many replacements we've had to make
  let invalidItemsCount = 0;
  
  //Start our loop at 1 so that [i-1] doesn't refer to index "-1"
  for (let i = 1; i < sequence.length; i++) {
  
    //If this item is not increasing, we'll need to address it
    if (sequence[i] <= sequence[i-1]) {
    
      //Increment our invalidItemsCount
      invalidItemsCount++;               
      
      //If this is our second invalidItem, then it's not almost increasing.
      if (invalidItemsCount > 1) return false;  
      
      //If removing the previous element doesn't help, and removing the current item doesn't help,
      //then we can't solve this in one move. It's not almost increasing.
      if (sequence[i] <= sequence[i-2] && sequence[i+1] <= sequence[i-1]) return false;
      
    }
  }
  
  //We've made it through the entire loop without fail. This is almost increasing.
  return true;
}

var test1 = [0,1,2,3,4,7,6,7,8,9,10];
var test2 = [0,1,2,4,3,4,5,7,6,7,8,9,10];

console.log(almostIncreasingSequence(test1));
console.log(almostIncreasingSequence(test2));