JavaScript-Interview: So implementieren Sie die Methode zur Array-Abflachung

1. Was ist Array-Flattening?

Das Konzept ist einfach, es bedeutet, die Dimensionalität eines „mehrdimensionalen“ Arrays zu reduzieren, zum Beispiel:

// Das ursprüngliche Array ist ein „dreidimensionales“ Array const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
 
// kann auf zweidimensional reduziert werden newArray1 = [1, 2, 3, 4, [5, 6], 7, 8, 9]
 
// Es kann auch auf eine Dimension reduziert werden newArray2 = [1, 2, 3, 4, 5, 6, 7, 8, 9]

Array-Flattening wird auch Array-Flattening und Array-Dimensionsreduzierung genannt.

2 Array-Flattening-Methode in der JS-Standardbibliothek

Die JavaScript-Standardbibliothek hat die Array-Flattening-Methode Array.prototype.flat() implementiert

Die Methode flat() durchläuft ein Array rekursiv bis zu einer angegebenen Tiefe, fügt alle Elemente mit den Elementen im durchlaufenen Teilarray zu einem neuen Array zusammen und gibt es zurück.

Syntax: var newArray = arr.flat([Tiefe])

Parameter: Tiefe ist ein optionaler Wert, der die Tiefe des zu durchlaufenden mehrdimensionalen Arrays angibt. Der Standardwert ist 1. Es kann als die Anzahl der Ebenen verstanden werden, die Sie erweitern (oder deren Dimension Sie reduzieren möchten).

Rückgabewert: ein neues Array, das aus den durchlaufenen Elementen und den Elementen des Subarrays besteht

Beispiel:

Konstantes Array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
const newArray1 = array.flat() // entspricht array.flat(1); reduziere 1 Dimension // newArray1: [1, 2, 3, 4, [ 5, 6 ], 7, 8, 9]
 
const newArray2 = array.flat(2) // 2 Dimensionen reduzieren // newArray2: [1, 2, 3, 4, 5, 6, 7, 8, 9]

besonders:

Wenn die Tiefe <= 0 ist, hat das zurückgegebene Array die gleiche Dimension wie das ursprüngliche Array (beachten Sie, dass nur die Dimension gleich ist, siehe Punkt 3 für den leeren Bereich).

Konstantes Array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
array.flach(-1)
// [1, 2, [3, 4, [5, 6], 7], 8, 9]

Tiefe = Unendlich, das zurückgegebene Array wird eindimensional

array.flat(Unendlich)
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

Wenn es im ursprünglichen Array freie Stellen gibt, werden diese mit der Flat-Methode eliminiert. Sogar flat(0) wird sie eliminieren, der erste Punkt ist also „nur die Anzahl der Dimensionen ist gleich“. Und der leere Raum wird auf der Ebene beseitigt, auf die sich die flache Methode ausdehnt, und der leere Raum auf einer tieferen Ebene wird nicht beseitigt.

const array1 = [1, , 2, [3, ,4, [5, 6], 7], 8, 9] 
// Beachten Sie, dass dieses Array zwei leere Felder hat array.flat(0)
// [ 1, 2, [ 3, ，4, [ 5, 6 ], 7 ], 8, 9 ]
// Die erste Stelle ist weg, aber die zweite Stelle ist noch da

3 Implementierung einer Flat-Methode

Die Schritte der flachen Methode zum Erweitern einer Ebene (Reduzieren einer Dimension) lauten wie folgt: Durchlaufen Sie das Array und bestimmen Sie, ob das aktuelle Element ein Array ist. Wenn es kein Array ist, speichern Sie es direkt. Wenn es ein Array ist, erweitern Sie es und speichern Sie es

Die flache Methode erweitert mehrere Ebenen (reduziert mehrere Dimensionen), indem sie basierend auf der Erweiterung einer Ebene rekursiv dieselbe Operation an den Unterelementen des Arrays ausführt.

Diese Methode kann in drei Schritte unterteilt werden:

1. So durchlaufen Sie ein Array

2. So bestimmen Sie, ob ein Element ein Array ist

3. Rekursion

Implementieren Sie die oben genannten drei Schritte und kombinieren Sie sie, um verschiedene flache Implementierungen zu erhalten

3.1 So durchlaufen Sie ein Array

Es gibt viele Methoden, hier sind 3 Kategorien:

1. für verwandte

• for-Schleife
• für...von

for...in ist für die Iteration über Objekteigenschaften gedacht und wird nicht für die Verwendung mit Arrays empfohlen.

Konstantes Array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
// for-Schleife for (let i = 0; i < array.length; i++) {
    konstantes Element = Array[i];
}
// für...von
für (const Element des Arrays) {
    
}

2. Array-Methode: Eine Methode, mit der Array-Elemente direkt abgerufen werden können

• fürJedes()
• reduzieren()
• Karte()

// fürJedes()
array.fürJedes(element => {
    
});
// reduzieren()
array.reduce((vorher, aktuell) => {
    Konstantes Element = aktuell
}, [])
// Karte()
array.map(element => {
  
})

3. Array-Methoden: Methoden, die Iteratorobjekte zurückgeben

• Schlüssel()
• Werte()
• Einträge()
  

// Diese drei Methoden dienen nur zum Abrufen des Traversierungsobjekts und müssen auch mit for...of verwendet werden, um // keys() zu durchlaufen.
für (let i von array.keys()) {
  konstantes Element = Array[i]
}
// Werte()
für (let Element von Array.Values()) {
  
}
// Einträge()
für (let [i, element] of array.entries()) {
  konsole.log(array[i])
  console.log(Element)
}

3.2 So bestimmen Sie, ob ein Element ein Array ist

Angenommen, es gibt eine Variable a. Bestimmen Sie, ob es sich um ein Array handelt. Hier sind 4 Methoden:

• Array verfügt über eine statische Methode Array.isArray(), mit der bestimmt wird, ob eine Variable ein Array ist.
• Der Operator „instanceof“ wird verwendet, um zu erkennen, ob die Prototype-Eigenschaft der Konstruktorfunktion in der Prototype-Kette eines Instanzobjekts vorkommt.
  Wenn es sich bei a um ein Array handelt, wird Array.prototype in seiner Prototypenkette angezeigt.
• Wird durch den Konstruktor des Objekts bestimmt (diese Methode kann fehlschlagen, da der Konstruktor manuell geändert werden kann)
• Nach Object.prototype.toString() kann diese Methode eine Zeichenfolge zurückgeben, die das Objekt darstellt

// Methode 1
Array.istArray(a)
// Methode 2
eine Instanz eines Arrays
// Methode 3
a.Konstruktor === Array
// Methode 4
//Verwenden Sie call, um die toString-Methode auf Object.prototype aufzurufen. Object.prototype.toString.call(a) === '[object Array]'
 
// Dies kann nicht beurteilt werden, da dieser toString bereits Object.prototype.toString überschrieben hat.
// Nur Object.prototype.toString kann den Typ a.toString() korrekt bestimmen

3.3 Rekursion

Rekursion: Führen Sie die gleiche Operation für untergeordnete Elemente aus.

Funktion flat() {
  lass res = []
  Durchlaufe das Array {
    if (das aktuelle Element ist ein Array) {
      flat(aktuelles Element) ruft ein eindimensionales Array ab und verkettet das eindimensionale Array zu res} else {
      res.push(aktuelles Element)
    }
  }
  Rückgabewert
}

3.4 Vorläufige Implementierung der Flat-Methode

Durch Auswahl der Traversierungsmethode und der Array-Beurteilungsmethode können Sie die flache Methode vorläufig mit Rekursion implementieren, beispielsweise:

Funktion meineFlat(arr) {
  lass res = [];
  für (const item of arr) {
    wenn (Array.isArray(item)) {
      res = res.concat(meinFlat(Artikel));
      // Beachten Sie, dass die Methode concat ein neues Array zurückgibt und das ursprüngliche Array nicht ändert} else {
      res.push(Element);
    }
  }
  Rückgabewert;
}

Die Methode myFlat kann ein mehrdimensionales Array in ein eindimensionales Array reduzieren, kann jedoch die Tiefe der Erweiterung nicht angeben und kann keine leeren Arrays verarbeiten.

4 Optimierung

4.1 Festlegung der Spreiztiefe

Es ist eigentlich sehr einfach, die Expansionstiefe zu handhaben. Wir können eine rekursive Beendigungsbedingung hinzufügen, d. h. Tiefe <= 0. Der Code lautet wie folgt:

Funktion myFlat(arr, Tiefe = 1) {
  // Wenn Tiefe <= 0, direkt zurückkehren, wenn (Tiefe <= 0) {
      Rückflug an
  }
  lass res = [];
  für (const item of arr) {
    wenn (Array.isArray(item)) {
      // Jeder rekursive Aufruf erhöht die Tiefe um 1
      res = res.concat(myFlat(Element, Tiefe - 1));
    } anders {
      res.push(Element);
    }
  }
  Rückgabewert;
}

4.2 Array-Leerstellenverarbeitung

Tatsächlich sollten wir versuchen, leere Arrays zu vermeiden.

Wir haben zuvor unterschiedliche Möglichkeiten zum Durchlaufen eines Arrays erwähnt, und sie behandeln leere Positionen im Array unterschiedlich.

ForEach, Reduce und Map ignorieren beim Durchlaufen leere Leerzeichen, aber for...of ignoriert leere Leerzeichen nicht und behandelt sie als undefiniert.

4.2.1 for...of fügt leeres Raumurteil hinzu

Daher müssen wir die Methode myFlat verbessern, die das Array in for...of durchläuft:

Funktion myFlat(arr, Tiefe = 1) {
  wenn (Tiefe <= 0) {
    Rückflug an;
  }
  lass res = [];
  für (const item of arr) {
    wenn (Array.isArray(item)) {
      res = res.concat(myFlat(Element, Tiefe - 1));
    } anders {
      // Bestimmen Sie, ob das Array leer ist. Element !== undefined && res.push(item);
    }
  }
  Rückgabewert;
}

4.2.2 Durchlaufen der forEach- und Map-Methode

Natürlich können Sie auch die Methoden forEach und Map verwenden, um das Array zu durchlaufen, sodass Sie nicht manuell beurteilen müssen.

Es gibt jedoch einen Sonderfall, der berücksichtigt werden muss: Wenn die Tiefe <= 0 ist, verwenden wir die Filtermethode, um freie Stellen im Array zu beseitigen.

// fürJedes
Funktion myFlat(arr, Tiefe = 1) {
  wenn (Tiefe <= 0) {
    Rückgabewert arr.filter(item => item !== undefiniert);
  }
  lass res = [];
  arr.fürEach((Artikel) => {
    wenn (Array.isArray(item)) {
      res = res.concat(myFlat(Element, Tiefe - 1));
    } anders {
      res.push(Element);
    }
  });
  Rückgabewert;
}
 
// Karte
Funktion myFlat(arr, Tiefe = 1) {
  wenn (Tiefe <= 0) {
    Rückgabewert arr.filter(item => item !== undefiniert);
  }
  lass res = [];
  arr.map((Artikel) => {
    wenn (Array.isArray(item)) {
      res = res.concat(myFlat(Element, Tiefe - 1));
    } anders {
      res.push(Element);
    }
  });
  Rückgabewert;
}

4.2.3 Reduzierungsmethode

Unter ihnen ist die Reduce-Methode die prägnanteste und gehört auch zu den Methoden, die in Interviews am häufigsten getestet werden.

Funktion myFlat(arr, Tiefe = 1) {
  Rücklauftiefe > 0
    ? arr.reduzieren(
        (vorher, aktuell) =>
          vor.concat(Array.isArray(aktuell) ? meineFlat(aktuell, Tiefe - 1) : aktuell),
        []
      )
    : arr.filter((item) => item !== undefiniert);
}

5 Andere

5.1 Stapel

Theoretisch können rekursive Methoden normalerweise in nicht-rekursive Methoden umgewandelt werden, d. h. mithilfe eines Stapels

Funktion meineFlat(arr) {
  lass res = [];
  const stack = [].concat(arr);
  während (Stapellänge > 0) {
    const item = stack.pop();
    wenn (Array.isArray(item)) {
      // Erweitern Sie eine Ebene mit dem Spread-Operator stack.push(...item);
    } anders {
      Element !== undefiniert && res.unshift(Element);
    }
  }
  Rückgabewert;
}

Allerdings kann bei dieser Methode die Erweiterungstiefe nicht angegeben werden und eine vollständige Erweiterung ist nur in ein eindimensionales Array möglich.

5.2 Verbesserungen

Um den Nachteil zu beheben, dass der Stack die Expansionstiefe nicht angeben kann, lautet der Code wie folgt:

Funktion myFlat(arr, Tiefe = 1) {
  wenn (Tiefe <= 0) {
    return arr.filter((Element) => Element !== undefiniert);
  }
  lass res;
  lass Warteschlange = [].concat(arr);
  während (Tiefe > 0) {
    res = [];
    Warteschlange.fürJeden((Element) => {
      wenn (Array.isArray(item)) {
        // Beachten Sie, dass Sie vor der Verwendung des Spread-Operators zum Erweitern des Arrays die Filtermethode verwenden müssen, um die leeren Stellen zu entfernen res.push(...item.filter((e) => e !== undefined));
      } anders {
        res.push(Element);
      }
    });
    Tiefe--;
    Warteschlange = Res;
  }
  Rückgabewert;
}

Zusammenfassen

Dies ist das Ende dieses Artikels über die Implementierung der Array-Abflachung in JavaScript-Interviews. Weitere Informationen zur Implementierung der Array-Abflachung in JS finden Sie in früheren Artikeln auf 123WORDPRESS.COM oder in den folgenden verwandten Artikeln. Ich hoffe, Sie werden 123WORDPRESS.COM auch in Zukunft unterstützen!