Ich würde vorschlagen, dass Sie Ihre eigene OffsetIntegerMap erstellen, die zwischen ganzen Zahlen abbilden und einen Versatz für die Schlüssel und Werte verarbeiten kann.

Sie Sie müssen die HashMap nicht unbedingt von Grund auf neu implementieren, Ihre eigene eingeschränkte Schnittstelle definieren und sie mit einer vorhandenen Map<Integer, Integer> durch Komposition implementieren.

Durch die getrennte Behandlung der Offsets von den Schlüsseln und Werten wird die Komplexität der Offset-Operationen bei Neuberechnungen zu O (1) anstelle von O (n) und Map<> Put- und Get-Operationen bleiben auf ihrem ursprünglichen O (1).

Ein Beispiel für ein “ OffsetIntegerMap „:

import java.util.HashMap; import java.util.Map; public class OffsetIntegerMap { private final Map<Integer, Integer> actualMap; private int keyOffset = 0; private int valueOffset = 0; public OffsetIntegerMap() { actualMap = new HashMap<>(); } public int size() { return actualMap.size(); } public boolean isEmpty() { return actualMap.isEmpty(); } public boolean containsKey(int key) { var keyWithoutOffset = key - keyOffset; return actualMap.containsKey(keyWithoutOffset); } public boolean containsValue(int value) { var valueWithoutOffset = value - valueOffset; return actualMap.containsValue(valueWithoutOffset); } public Integer get(int key) { var keyWithoutOffset = key - keyOffset; var value = actualMap.get(keyWithoutOffset); if (value == null) return null; return value + valueOffset; } public Integer put(int key, int value) { var keyWithoutOffset = key - keyOffset; var valueWithoutOffset = value - valueOffset; var oldValue = actualMap.put(keyWithoutOffset, valueWithoutOffset); if (oldValue == null) return null; return oldValue + valueOffset; } public Integer remove(int key) { var keyWithoutOffset = key - keyOffset; var oldValue = actualMap.remove(keyWithoutOffset); if (oldValue == null) return null; return oldValue + valueOffset; } public void clear() { actualMap.clear(); keyOffset = 0; valueOffset = 0; } public int getKeyOffset() { return keyOffset; } public void setKeyOffset(int keyOffset) { this.keyOffset = keyOffset; } public int getValueOffset() { return valueOffset; } public void setValueOffset(int valueOffset) { this.valueOffset = valueOffset; } public void addToValues(int toAdd) { this.valueOffset += toAdd; } public void addToKeys(int toAdd) { this.keyOffset += toAdd; } } 

Durch die Kapselung der Offset-Logik wird die Verarbeitungsschleife auch viel einfacher, ohne viel von irgendetwas umzugestalten ing:

static long hashMap(String[] queryType, int[][] query) { long sum = 0; var map = new OffsetIntegerMap(); for (int i = 0; i < queryType.length; i++) { String currQuery = queryType[i]; switch (currQuery) { case "insert": map.put(query[i][0], query[i][1]); break; case "addToValue": map.addToValues(query[i][0]); break; case "addToKey": map.addToKeys(query[i][0]); break; case "get": sum += map.get(query[i][0]); } } return sum; } 

Kommentare

• Vielen Dank. Sieht nach einer besseren Implementierung aus. Ich werde diese Logik überprüfen.
• Ich finde diese Antwort oben. Verwenden einer Klasse, die vom Testen aller Fälle getrennt ist.keyWithoutOffset und valueWithoutOffset (Ich glaube, ich habe einen Fehler im Originalcode w.r..t. dazu gesehen). Die eindeutigen Namen (Offset). Nur die Methodennamen sind Map-zentriert anstelle der in den Anforderungen angegebenen.
• Sie können das Beispiel aus der Frage verwenden. Ersetzen Sie einfach [] durch {}. queryType ist String[] und query ist int[][].
• Ah, das habe ich übersehen. Und ich ‚ bin zu verwöhnt, indem ich Challenge-Sites codiere, die mir nur einen “ Run “ geben Taste :-). Diese Lösung wurde jetzt in meine eigene Antwort geändert.
• Der Versatz ist nicht für jeden Schlüssel in der Hashmap gleich! – Beginnen Sie mit dem Keyset (1,2,3) – fügen Sie 10 zu allen Schlüsseln hinzu, jetzt ist das Keyset (10,11,12) – fügen Sie den neuen Schlüssel (5) ein, jetzt ist das Keyset (10,11,12,5) – fügen Sie hinzu 10 für alle Tasten, jetzt ist der Keyset (20,21,22,15). Den ersten 3 Schlüsseln wurde also effektiv ein Versatz von 20 hinzugefügt, aber der letzte Schlüssel hatte nur einen Versatz von 10 (dh das Hinzufügen von Schlüsseln, die vor dem Einfügen dieses Schlüssels (5) vorgenommen wurden, wird ignoriert).

Ich habe einige Vorschläge für Sie.

Extrahieren Sie einen Teil der Logik in Methoden.

In Ihrem Code: Wenn die Abfrage insert und get lautet, haben Sie zwei große Codeblöcke, die ähnlich sind. Sie können in eine Methode extrahieren und die Methode in beiden Abschnitten wiederverwenden.

Ich schlage eine Methode vor, die einen Booleschen Wert basierend auf der Bedingung if zurückgibt Die Variablen currValue und currKey können auf Null gesetzt werden.

  long hashMap(String[] queryType, int[][] query) { //[...] switch (currQuery) { //[...] case "insert": if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } values.put(query[i][0], query[i][1]); break; //[...] } //[...] } private boolean didWeCopiedValuesToMap(Integer currKey, Integer currValue, Map<Integer, Integer> values, HashMap<Integer, Integer> copiedValues) { if (currKey != 0 || currValue != 0) { Set<Integer> keys = values.keySet(); for (Integer key : keys) { copiedValues.put(key + currKey, values.get(key) + currValue); } values.clear(); values.putAll(copiedValues); return true; } return false; }  

Um die aktuelle Abfrage currQuery zu überprüfen, können Sie jede dieser Abfragen in einer Methode extrahieren.

 private boolean isGet(String currQuery) { return "get".equals(currQuery); } private boolean isAddToKey(String currQuery) { return "addToKey".equals(currQuery); } private boolean isAddToValue(String currQuery) { return "addToValue".equals(currQuery); } private boolean isInsert(String currQuery) { return "insert".equals(currQuery); }  

Verwenden Sie nach Möglichkeit immer die Grundelemente

Wenn Sie wissen, dass es unmöglich ist, mit der Zahl einen Nullwert zu erhalten, versuchen Sie, die Grundelemente zu verwenden; sie benötigen weniger Speicher und sind schneller als die Wrapper-Klasse.

Vor

 Integer currKey = 0; Integer currValue = 0;  

Nach

 int currKey = 0; int currValue = 0;  

Versuchen Sie, weniger Code in switch -Blöcke

einzufügen Meiner Meinung nach wird der Code weniger lesbar, wenn ein Schaltblock mehr als 3 Codezeilen enthält. Ich schlage vor, dass Sie es in eine is-else-if konvertieren. Durch diese Konvertierung wird der Code kürzer und lesbarer.

Vor

switch (currQuery) { case "insert": if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } values.put(query[i][0], query[i][1]); break; case "addToValue": currValue += values.isEmpty() ? 0 : query[i][0]; break; case "addToKey": currKey += values.isEmpty() ? 0 : query[i][0]; break; case "get": if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } sum += values.get(query[i][0]); }

Nach

 if ("insert".equals(currQuery)) { if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } values.put(query[i][0], query[i][1]); } else if ("addToValue".equals(currQuery)) { currValue += values.isEmpty() ? 0 : query[i][0]; } else if ("addToKey".equals(currQuery)) { currKey += values.isEmpty() ? 0 : query[i][0]; } else if ("get".equals(currQuery)) { if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } sum += values.get(query[i][0]); }  

Refactored Code

  long hashMap(String[] queryType, int[][] query) { long sum = 0; int currKey = 0; int currValue = 0; Map<Integer, Integer> values = new HashMap<>(); for (int i = 0; i < queryType.length; i++) { String currQuery = queryType[i]; if (isInsert(currQuery)) { if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } values.put(query[i][0], query[i][1]); } else if (isAddToValue(currQuery)) { currValue += values.isEmpty() ? 0 : query[i][0]; } else if (isAddToKey(currQuery)) { currKey += values.isEmpty() ? 0 : query[i][0]; } else if (isGet(currQuery)) { if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } sum += values.get(query[i][0]); } } return sum; } private boolean isGet(String currQuery) { return "get".equals(currQuery); } private boolean isAddToKey(String currQuery) { return "addToKey".equals(currQuery); } private boolean isAddToValue(String currQuery) { return "addToValue".equals(currQuery); } private boolean isInsert(String currQuery) { return "insert".equals(currQuery); } private boolean didWeCopiedValuesToMap(int currKey, int currValue, Map<Integer, Integer> values) { HashMap<Integer, Integer> copiedValues = new HashMap<>(); if (currKey != 0 || currValue != 0) { Set<Integer> keys = values.keySet(); for (Integer key : keys) { copiedValues.put(key + currKey, values.get(key) + currValue); } values.clear(); values.putAll(copiedValues); return true; } return false; }  

Am häufigsten Eine teure Operation ist die addToKey x, die allen Schlüsseln in der Karte x hinzufügt, da Sie im Wesentlichen einen neuen Eingabeschlüssel mit dem Wert + x in Ihrer hashmap und lösche den alten Eingabeschlüssel, Wert. Um zu vermeiden, dass der alte Eintrag beim Durchlaufen der Karte zwischengespeichert werden muss, können Sie zwei Fälle unterscheiden:

x > 0. Wenn Sie dann über a iterieren keyset in absteigender Reihenfolge geordnet, müssen die alten Einträge nicht zwischengespeichert werden.

x < 0, der gleiche Ansatz, aber der keyset ist aufsteigend geordnet

Da Sie hashmap verwenden, ist keine Schlüsselreihenfolge garantiert, sodass Sie Daten benötigen Struktur zum Speichern der zu bestellenden Schlüssel, bevor die folgenden Schlüssel durchlaufen werden:

private static void addtoKey(Map<Integer, Integer> map, int i) { if (i != 0) { List<Integer> list = new ArrayList<>(map.keySet()); if (i > 0) { Collections.sort(list, Collections.reverseOrder()); } else { Collections.sort(list); } for(int key : list) { map.put(key + i, map.get(key)); map.remove(key); } } } 

Ich habe den Fall 0 ausgeschlossen weil map unberührt bleibt. Andere Operationen benötigen keine Reihenfolge der Schlüssel und wie bereits vorgeschlagen, könnte es besser sein, jede Operation in einer privaten Methode zu isolieren.

Kommentare

• Vielen Dank an @dariosicily für die Antwort. Ist ‚ nicht jedes Mal zu sortieren, während die addToKey -Operation ebenfalls kostspielig ist? Oder kann ich sie verwenden? a SortedMap, um die Einfügereihenfolge absteigend zu halten. SortedMap<Integer, Integer>values = new TreeMap<Integer, Integer>(Collections.reverseOrder());
• @Praveen Gern geschehen. Ja, das ist es Jedes Mal sortieren, aber mit ArrayList nach dem Sortieren gehen Sie linear vor.Ich wurde verurteilt, dass Sie nur HashMap verwenden können. Wenn Sie TreeMap anstelle von HashMap verwenden können, können Sie einen Iterator und einen umgekehrten Iterator verwenden und über Ihren auf einfache Weise.

Geänderte Version von Johnbots Antwort ohne eine zusätzliche Klasse. Ich denke, die zusätzliche Klasse ist übertrieben und lenkt eher vom Algorithmus ab, da ich viel Code durchsuchen muss (viel davon Boilerplate) um zu sehen, was los ist. Es ist nicht diese zusätzliche Klasse, die die Verarbeitungsschleife viel einfacher macht. Es ist der Algorithmus.

Weitere Änderungen:

• keyOffset ist mir nicht klar, in welche Richtung es versetzt ist, deshalb habe ich das in addedToKey umbenannt (ebenfalls für Wert).
• Die Operation wurde angeordnet Namen wie in der Problemspezifikation, sowohl um nahe an der Spezifikation zu bleiben als auch weil diese Reihenfolge für mich sinnvoller ist.
• args eingeführt, um einige Code-Wiederholungen zu sparen.
• Verwendet long / Long für alles, nicht nur für die Summe. Wenn Sie die Schlüssel / Werte hinzufügen, können sie schließlich überlaufen, wenn Sie nur int / Integer verwenden.

static long hashMap(String[] queryType, int[][] query) { Map<Long, Long> map = new HashMap<>(); long sum = 0, addedToKey = 0, addedToValue = 0; for (int i = 0; i < query.length; i++) { int[] args = query[i]; switch (queryType[i]) { case "insert": map.put(args[0] - addedToKey, args[1] - addedToValue); break; case "get": sum += map.get(args[0] - addedToKey) + addedToValue; break; case "addToKey": addedToKey += args[0]; break; case "addToValue": addedToValue += args[0]; } } return sum; } 

Kommentare

• Warum wird addedToKey einheitlich zum hinzugefügt Der Schlüssel von value ‚ funktioniert nicht, subtrahiert ihn jedoch für die Aktionen insert und get Arbeit?

Wie wäre es, wenn Sie nur einen Versatzwert für Schlüssel und Werte speichern und Wrapper-Methoden um das herum erstellen Hashmaps erhalten / setzen Methoden, um diesen Offset zu berücksichtigen.