javascript - 几乎递增序列 - 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));