Ti suggerirei di creare il tuo OffsetIntegerMap che può mappare tra interi e gestire un offset sulle chiavi e sui valori.

Tu Non devi necessariamente implementare HashMap da zero, definire la tua interfaccia limitata e implementarla con un Map<Integer, Integer> tramite composizione esistente.

Gestendo gli offset separatamente dalle chiavi e dai valori, la complessità delle operazioni di offset diventa O (1) invece di O (n) quando si eseguono ricalcoli e Map<> le operazioni put e get rimangono al valore O (1) originale.

Un esempio di ” 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; } } 

Incapsulando la logica di offset, il ciclo di elaborazione diventa anche molto più semplice senza refactoring molto di nulla 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; } 

Commenti

• Grazie. Sembra unimplementazione migliore. Controllerò questa logica.
• Trovo questa risposta in alto. Utilizzo di una classe separata dal test di tutti i casi.keyWithoutOffset e valueWithoutOffset (penso di aver visto un bug nel codice originale w.r..t. a quello). I nomi chiari (offset). Solo i nomi dei metodi sono incentrati sulla mappa invece di quelli nei requisiti
• Puoi utilizzare lesempio della domanda. Basta sostituire [] con {}. queryType è String[] e query è int[][].
• Ah, lho trascurato. E io ‘ sono troppo viziato dalla codifica di siti di sfida che mi danno solo un ” Esegui ” pulsante :-). Ho modificato questa soluzione nella mia risposta ora.
• Loffset non sarà lo stesso per ogni chiave in hashmap! – inizia con keyset (1,2,3) – aggiungi 10 a tutte le chiavi, ora keyset è (10,11,12) – inserisci una nuova chiave (5), ora keyset è (10,11,12,5) – aggiungi 10 a tutte le chiavi, ora il keyset è (20,21,22,15). Quindi le prime 3 chiavi avevano effettivamente un offset di 20 aggiunto, ma lultima chiave aveva solo 10 offset (cioè le aggiunte di chiavi fatte prima che questa chiave (5) fosse inserita verranno ignorate).

Ho alcuni suggerimenti per te.

Estrai un po della logica ai metodi.

Nel tuo code, quando la query è insert e get, hai due grandi blocchi di codice simili; puoi estrarre un metodo e riutilizzare il metodo in entrambe le sezioni.

Suggerisco un metodo che restituisca un valore booleano basato sulla condizione if, quindi sarai in grado di impostare le variabili currValue e currKey su zero.

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

Inoltre, per controllare la query corrente currQuery, puoi estrarne ciascuna in un metodo.

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

Usa sempre le primitive quando possibile

Quando sappi che è impossibile ottenere un valore nullo con il numero, prova a utilizzare le primitive; richiedono meno memoria ed è più veloce della classe wrapper.

Prima di

 Integer currKey = 0; Integer currValue = 0;  

Dopo

 int currKey = 0; int currValue = 0;  

Prova a mettere meno codice in switch blocchi

A mio parere, il codice diventa meno leggibile quando ci sono più di 3 righe di codice in un blocco interruttore; Ti suggerisco di convertirlo in un is-else-if. Questa conversione renderà il codice più breve e più leggibile.

Prima di

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

Dopo

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

Codice refactoring

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

Il più operazione costosa è la addToKey x che aggiunge x a tutte le chiavi nella mappa, perché sostanzialmente devi creare una nuova chiave di accesso, valore + x nel tuo hashmap ed elimina la vecchia chiave di accesso, value. Per evitare la necessità di memorizzare nella cache la vecchia voce durante literazione sulla mappa, puoi distinguere due casi:

x > 0, quindi se hai iterato su un keyset in ordine decrescente non è necessario memorizzare nella cache le vecchie voci

x < 0, stesso approccio ma keyset è ordinato in modo crescente

Poiché stai utilizzando hashmap, non è garantito lordine delle chiavi, quindi hai bisogno di un dato struttura per memorizzare le chiavi da ordinare, prima di iterare su chiavi come di seguito:

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

Ho escluso il caso 0 perché map rimane invariato. Altre operazioni non richiedono lordine delle chiavi e come già suggerito potrebbe essere meglio cercare di isolare ogni operazione in un metodo privato.

Commenti

• Grazie @dariosicily per la risposta. ‘ t ordinamento ogni volta mentre si esegue addToKey anche loperazione è costosa ?. Oppure posso usare a SortedMap per mantenere lordine di inserzione decrescente. Ad esempio, SortedMap<Integer, Integer>values = new TreeMap<Integer, Integer>(Collections.reverseOrder());
• @Praveen Sei il benvenuto. Sì, lo è ordinamento ogni volta, ma con ArrayList dopo lordinamento si procede in modo lineare.Sono stato condannato che potresti utilizzare solo HashMap; se puoi utilizzare TreeMap invece di HashMap puoi utilizzare un iteratore e un iteratore inverso e ripetere literazione sul tuo TreeMap in modo diretto.

Versione modificata di Johnbot” la risposta senza una classe in più. Penso che la classe in più sia eccessiva e distrae piuttosto dallalgoritmo, poiché devo cercare un sacco di codice (in gran parte boilerplate) per vedere cosa sta succedendo. Non è quella classe in più che rende il ciclo di elaborazione molto più semplice. È lalgoritmo.

Ulteriori modifiche:

• keyOffset non mi è chiaro in quale direzione è spostato, quindi lho rinominato in addedToKey (allo stesso modo per value).
• Ho ordinato loperazione nomi come nella specifica del problema, sia per rimanere vicini alla specifica sia perché quellordine ha più senso per me.
• Introdotto args per salvare alcune ripetizioni del codice.
• Usato long / Long per tutto, non solo per la somma. Dopotutto, laggiunta di chiavi / valori potrebbe farli traboccare se usiamo solo int / Integer.

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

Commenti

• Perché laggiunta uniforme di addedToKey al valore ‘ s chiave non funziona, ma sottraendolo per le azioni insert e get non funziona funziona?

Che ne dici di memorizzare un valore di offset per chiavi e valori e costruire metodi wrapper attorno al hashmaps get / put metodi per tenere conto di questo offset.