TIL: LIFO-Lösung und reguläre Ausdruckstechniken【CodeWars】

Übersicht ?

Bei der Herausforderung „Routenreduzierung“ werden Sie aufgefordert, die kürzeste Route aus einer Anordnung von Wegbeschreibungen zu finden.

Beispiele:

Input
-> Output
["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
-> ["WEST"]
/* 
Because moving "NORTH" and "SOUTH", or "EAST" and "WEST", is unnecessary.
*/

/* 
Case: omit the first "NORTH"-"SOUTH" pair 
["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
-> ["SOUTH", "EAST", "WEST", "NORTH", "WEST"]

Case: omit the "EAST"-"WEST" pair 
-> ["SOUTH", "NORTH", "WEST"]

Case: omit the "NORTH"-"SOUTH" pair 
-> ["WEST"]
*/

// this case cannot be reduced:
["NORTH", "WEST", "SOUTH", "EAST"]
-> ["NORTH", "WEST", "SOUTH", "EAST"]

---

Lösungen 1: LIFO

function dirReduc(plan) {
  var opposite = {
    'NORTH': 'SOUTH', 'EAST': 'WEST', 'SOUTH': 'NORTH', 'WEST': 'EAST'};
  return plan.reduce(function(dirs, dir){
      if (dirs[dirs.length - 1] === opposite[dir])
        dirs.pop(); // Remove last direction if it's the opposite
      else
        dirs.push(dir); // Otherwise, add current direction to the stack
      return dirs;
    }, []);
}

Dies ist ein LIFO-Ansatz (Last-in-First-out), der mithilfe von Reduce implementiert wird.

Schritte:

1. Deklarieren Sie einen leeren Stapel (Verzeichnisse)
2. Überprüfen Sie für jede Richtung im Eingabearray (Plan), ob das letzte Element des Stapels (Verzeichnisse) das Gegenteil der aktuellen Richtung ist
3. Wenn es sich um Gegensätze handelt, entfernen Sie das letzte Element vom Stapel (und überspringen Sie die aktuelle Richtung). Andernfalls schieben Sie die aktuelle Richtung auf den Stapel.
4. Wiederholen Sie diesen Vorgang, bis alle Anweisungen verarbeitet wurden.

---

Lösungen 2: Regulärer Ausdruck

function dirReduce(arr) {
  let str = arr.join(''), pattern = /NORTHSOUTH|EASTWEST|SOUTHNORTH|WESTEAST/;
  while (pattern.test(str)) str = str.replace(pattern,''); // Remove pairs while they exist
  return str.match(/(NORTH|SOUTH|EAST|WEST)/g)||[];
}

Alternative Version:

function dirReduc(arr) {
  const pattern = /NORTHSOUTH|EASTWEST|SOUTHNORTH|WESTEAST/;
  let str = arr.join('');

  while (pattern.test(str)) {
    str = str.replace(pattern, ''); // Remove pairs while they exist
  }

  const result = str.match(/(NORTH|SOUTH|EAST|WEST)/g);
  return result || [];
}

Schritte:

1. Fügen Sie das Eingabearray (arr) zu einer einzigen Zeichenfolge zusammen, damit wir es mit regulären Ausdrücken bearbeiten können.
2. Definieren Sie einen regulären Ausdruck (Muster), der mit Paaren in entgegengesetzter Richtung übereinstimmt (z. B. „NORTHSOUTH“, „EASTWEST“).
3. Verwenden Sie die Ersetzungsmethode in einer Schleife, um alle vom regulären Ausdruck gefundenen Richtungspaare zu entfernen.
4. Nachdem alle Paare entfernt wurden, verwenden Sie die Match-Methode, um die verbleibenden Richtungen aus der Zeichenfolge zu extrahieren und sie als Array zurückzugeben.

---

Diskussion und Einblicke?

Ich glaube, der Mindestfall für diese Lösung ist wie folgt:

1. ["SOUTH", "EAST", "WEST", "NORTH"]
-> []

2. ["NORTH", "WEST", "SOUTH", "EAST"]
-> ["NORTH", "WEST", "SOUTH", "EAST"]

Ich bevorzuge Lösung 2, da sie prägnant ist und reguläre Ausdrücke auf clevere Weise verwendet. Anfangs konnte ich mir nicht vorstellen, es mit regulären Ausdrücken zu lösen, aber die Verwendung von Join-, Match-, While-, Replacement- und Testmethoden zum Eliminieren von Paaren ist beeindruckend.

Wenn Sie neugierig auf diese Lösungen sind oder weitere Herausforderungen erkunden möchten, besuchen Sie hier.
Gerne können Sie unten einen Kommentar hinterlassen!

Danke fürs Lesen?

Das obige ist der detaillierte Inhalt vonTIL: LIFO-Lösung und reguläre Ausdruckstechniken【CodeWars】. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!