0
votes

Javascript: vérifie si le tableau est une séquence presque croissante

Je travaille sur quelques défis Javascript sur Code Signal et suis tombé sur cette question:

Étant donné une séquence d'entiers sous forme de tableau, déterminez s'il est possible d'obtenir une séquence strictement croissante en ne supprimant pas plus d'un élément du tableau. **
Remarque: la séquence a0, a1, ..., an est considérée comme strictement croissante si a0 <a1 <... <an. Une séquence contenant un seul élément est également considérée comme strictement croissante.
Exemple Pour sequence = [1, 3, 2, 1], la sortie doit être presqueIncreasingSequence (sequence) = false.
Il n'y a pas un élément dans ce tableau qui puisse être supprimé pour obtenir une séquence strictement croissante. Pour sequence = [1, 3, 2], la sortie doit être presqueIncreasingSequence (sequence) = true.
Vous pouvez supprimer 3 du tableau pour obtenir la séquence strictement croissante [1, 2]. Vous pouvez également supprimer 2 pour obtenir la séquence strictement croissante [1, 3].

Mon approche consiste à parcourir le tableau de séquences, à vérifier si l'élément actuel est supérieur à l'élément suivant, le cas échéant, à supprimer l'élément actuel. Ensuite, incrémentez un compteur, si le compteur est inférieur à 2, retournez true, sinon retournez false.

Voici mon code:

function almostIncreasingSequence(sequence) {
    // If array has 1 or 2 elements it passes
    if(sequence.length <= 2) {
        return true;
    }

    // Keeps track of numbers removed
    let numberRemoved = 0;

    // Iterate through array, check if current element is greater than next element
    // If so, increment numberRemoved and remove current element
    for(let i = 0; i < sequence.length; i++) {        
        if(sequence[i] >= sequence[i + 1]) {
            numberRemoved++;

            // Removed element if it's greater than next element
            let removed = sequence.splice([i], 1);
            i = 0;

            console.log(sequence);
        }

    }

    // Second pass through the array checks if there are 2 or more out of order        
    // elements. Inefficient and sloppy, need to find a better approach
    for(let j = 0; j < sequence.length; j++) {
        if(sequence[j] >= sequence[j + 1]) {
            numberRemoved++;
        }
    }

    // If number is less than 2, the sequence passes
    if(numberRemoved < 2) {
        return true;
    }
    else {
        return false;
    }  
}

Cette solution résout 17/19 cas de test. Je rencontre un cas de pointe où parfois, si i> = [i + 1], la bonne approche serait de supprimer [i + 1] , pas i . Par exemple:

Dans le cas de la séquence: [3, 5, 67, 98, 3]
Pour les boucles vérifie si 98 est> = 3
Supprime 98
La séquence échoue car [3, 5, 67, 3] échoue
Dans ce cas, nous ne devrions pas supprimer 98, nous devrions supprimer 3
La séquence passe alors: [3, 5, 67, 98] renvoie vrai
Pour ce cas de bord, nous ne voulons pas faire: let enlevé = sequence.splice ([i], 1);
Nous voulons faire: let enlevé = sequence.splice ([i + 1], 1);
Cela supprimerait 3
[3, 5, 67, 98] renvoie vrai

Comment puis-je gérer ce cas de bord? Dans certains cas, si la séquence [i]> = [i + 1], vous devez supprimer la séquence [i] , dans d'autres cas, vous devez supprimer [i + 1] . Comment puis-je résoudre ce problème sans utiliser une seconde boucle for et passer une seconde fois dans le tableau?

javascript for-loop arrays iteration comparison

1 commentaires

Vérifiez si [i+1] < [i-1] . Si c'est le cas, supprimez [i+1] au lieu de [i] .

6 Réponses :

1
votes

La question est principalement "devons-nous supprimer un élément ou moins pour obtenir une séquence croissante?". Vous n'avez donc pas besoin de supprimer quoi que ce soit, comptez simplement le nombre d'éléments à supprimer.

De plus, vous devez continuer la vérification sans que la numérotation hors séquence n'échoue aux vérifications suivantes. Dans ce cas, attribuez à prev le nombre le plus bas entre le courant et le prev .

function almostIncreasingSequence(sequence) {
  let removed = 0;
  let i = 0;
  let prev = -Infinity;
  
  // as long as removed less than 2 times, and i is under arrays length
  while(removed < 2 && i < sequence.length) {
    if(sequence[i] > prev) { // if current is bigger the previous
      prev = sequence[i]; // assign current to previous
    } else {
      prev = Math.min(prev, sequence[i]); // take the lowest
      removed++; // increment removed
    }
    
    i++;
  }

  return removed < 2; // true if removed are under 2
}

console.log(almostIncreasingSequence([1, 3, 2, 1])); // false
console.log(almostIncreasingSequence([1, 3, 2])); // true
console.log(almostIncreasingSequence([3, 5, 67, 98, 3])); // true
console.log(almostIncreasingSequence([4, 3, 5, 67, 98, 3])); // false
console.log(almostIncreasingSequence([1, 4, 2, 3])); // true

0 commentaires

0
votes

Je ne suis pas sûr de bien comprendre la question, mais je pense que celle-ci pourrait être votre réponse ...

function testSequence(arraySequence)
  {
  let prev = -Infinity
    , ret  = true
    , out  = false
    ;
  for(let val of arraySequence) 
    {
    if (val<=prev)
      {
      if (out) { ret=false; break }
      else     { out=true         }
      }
    prev=val
    }
  return ret
  }


console.log(testSequence([1, 3, 2, 1]));         // false
console.log(testSequence([1, 3, 2]));            // true
console.log(testSequence([3, 5, 67, 98, 3]));    // true
console.log(testSequence([4, 3, 5, 67, 98, 3])); // false

0 commentaires

1
votes

Chaque fois qu'un nombre décroissant est trouvé, nous devons déterminer lequel des 2 nombres consécutifs doit être supprimé. Cela peut être soit:

Le dernier numéro est trop grand
Le nombre actuel est trop petit

Si aucun d'eux ne peut corriger la diminution, le tableau n'est déjà pas une "séquence presque croissante", car cela signifie qu'au moins une autre suppression est nécessaire.

function almostIncreasingSequence(sequence) {
  let removed = 0;
  let i = 0;
  let prev = -Infinity;
  
  // as long as removed less than 2 times, and i is under arrays length
  while(removed < 2 && i < sequence.length) {
    if(sequence[i] > prev) { // if current is bigger the previous
      prev = sequence[i]; // assign current to previous
      // remove the latter number, if it fixes the decrease
    } else if (i === sequence.length - 1 || sequence[i+1] > sequence[i-1]) {
      removed++; // increment removed
    } else if (i < 2 || sequence[i] > sequence[i-2]) {
      // remove the former number, if it fixes the decrease
      removed++;
      prev = sequence[i];
    } else {
      // neither option fixes the decrease, so at least 2 removal is needed
      return false;
    }
    i++;
  }

  return removed < 2; // true if removed are under 2
}

console.log(almostIncreasingSequence([1, 3, 2, 1])); // false
console.log(almostIncreasingSequence([1, 3, 2])); // true
console.log(almostIncreasingSequence([3, 5, 67, 98, 3])); // true
console.log(almostIncreasingSequence([4, 3, 5, 67, 98, 3])); // false
console.log(almostIncreasingSequence([1, 4, 2, 3])); // true
console.log(almostIncreasingSequence([10, 13, 2, 9])); // false

2 commentaires

Bonne prise. J'ai supprimé la partie "Cela échouerait" de votre réponse, car elle a été corrigée. La prochaine fois, un commentaire sur ma réponse, détaillant le problème, serait bien.

Merci pour la mise à jour. J'ai pensé qu'un commentaire serait aussi plus approprié, mais mon compte ne peut pas encore ajouter de commentaires.

0
votes

Vous pourriez prendre un index trouvé.

Cette approche teste soit trois éléments consécutifs, comme

.as-console-wrapper { max-height: 100% !important; top: 0; }

ou prend pour la boucle suivante une vérification qui omet la valeur trouvée en vérifiant l'index trouvé.

function inSequence(array) {
    var i,
        found;
        
    for (i = 1; i < array.length - 1; i++) {
        if ((found === i - 1 || array[i - 1] < array[i]) && array[i] < array[i + 1]) continue;
        if (array[i - 1] >= array[i + 1] || found !== undefined) return false;
        found = i;
    }
    return true;
}

console.log(inSequence([2, 1]));
console.log(inSequence([1, 2, 3]));
console.log(inSequence([2, 1, 3]));
console.log(inSequence([1, 2, 4, 3]));
console.log(inSequence([1, 2, 3, 8, 4, 5, 6, 7]));
console.log(inSequence([1, 2, 3, 8, 4, 5, 6, 9, 7]));
console.log(inSequence([2, 1, 3, 4, 5, 2]));
console.log(inSequence([1, 2, 3, 1, 2, 5, 6, 7]));
console.log(inSequence([1, 2, 3, 8, 2, 5, 6, 7]));

Ensuite, sinon dans l'ordre, les éléments adjacents sont vérifiés pour éviter ce modèle

            v
1   2   3   1   2   5   6   7
        3   >   2

            v
1   2   3   8   2   5   6   7
        3   >   2

et s'il est trouvé, plus d'un élément est en mauvaise position.

                v
1   2   3  [8   4   5]  6   7
            ^ omit value on found index

            v
1   2  [3   8   4]  5   6   7   -> found at index 3

0 commentaires

0
votes

La question demande que vous trouviez si, lorsqu'un index dans un tableau est supprimé, le tableau serait une séquence croissante. Par conséquent, si nous ignorons un index qui désobéit à la règle

a i <a i + 1

alors l'autre index doit obéir à la règle.

function almostIncreasingSequence(sequence) {
let unorderedIndex = 0;
for(let i = 1; i < sequence.length; i++ ){
if( sequence[i-1] >= sequence[i] ) {
    unorderedIndex++;

// an array that's almost increasing would just have one unordered index
    if( unorderedIndex > 1 ) return false;
    
    if( sequence[i-2] >= sequence[i] && sequence[i-1] >= sequence[i+1])
        return false;
    }
} 
return true;
    }

0 commentaires

0
votes

Voici une solution simple.

function almostIncreasingSequence(sequence) {
  // initialize removedCount to 0.
  let removedCount = 0;

  // iterate through sequence
  for(let i=0; i<sequence.length-1; i++) {
    // if current value is greater than the next value ex. [3, 1, 2]; 3 > 1
    if(sequence[i] > sequence[i+1]) {
      // increase count
      removedCount++;
    } 
  }
  // if our count is more than 2 return false, otherwise return true 
  return removedCount <= 1;
}

0 commentaires