почти возрастающая последовательность - 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

Так что я делаю CodeFights на python.И я застрял с этим заданием.Каждый ответ на StackOverflow, который я нашел, содержал много длительных условий.Поэтому я полагаю, что людям может быть полезно увидеть мое решение.Я уверен, что его можно переписать в лучшем стиле, но у этого подхода больше интуиции

def almostIncreasingSequence(sequence):
    def isIncreasingSequence(sequence, skip = None):
        to_use = list.copy(sequence)
        if skip != None:
            del to_use[skip]
        for i in range(1, len(to_use)):
            if to_use[i] <= to_use[i-1]:
                return False
        return True

    for i in range(1, len(sequence)):
        if(sequence[i - 1] >= sequence[i]):
            return isIncreasingSequence(sequence, i-1) or  isIncreasingSequence(sequence, i)
    return True

Answer 2

Я придумал это решение в TypeScript, я добавил сюда, чтобы получить обратную связь.Это работает, потому что логическое значение изначально не определено.

function almostIncreasingSequence(sequence: number[]): boolean {

let joker : boolean;
console.log(joker);
for (let index = 1; index < sequence.length; index++) {
    const element = sequence[index];
    if (sequence[index] <= sequence[index-1]) {
        if (!joker) {
            joker = true;     
        } else {
            return false;
        }
    } 
}
return true;
}

Answer 3

Как я уже упоминал в своем комментарии, вам не нужно постоянно проверять весь массив или использовать несколько циклов.

Проблема может быть разбита на более мелкие вопросы.Для каждого элемента в списке ...

• Текущий элемент больше, чем последний (увеличивается)?
  • Да ...
    • Хорошо!Нам ничего не нужно делать.
  • Нет ...
    • Это уже произошло?Если это так, почти не увеличивается.
    • Если мы удалим предыдущий элемент, будут ли исправлены окружающие элементы?
    • Нет?Что, если вместо этого мы удалим текущий элемент?
    • Все еще нет?Тогда это означает, что мы не можем решить это за один ход. Это почти не увеличивается.

Код будет выглядеть примерно так:

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