Le sugiero que cree su propio OffsetIntegerMap que pueda mapear entre enteros y manejar un desplazamiento en las claves y valores.

Usted no necesariamente tiene que implementar HashMap desde cero, defina su propia interfaz limitada e impleméntela con una Map<Integer, Integer> existente a través de la composición.

Al manejar las compensaciones por separado de las claves y valores, la complejidad de las operaciones de compensación terminan en O (1) en lugar de O (n) cuando se realizan nuevos cálculos y Map<> las operaciones put y get permanecen en su O (1) original.

Un ejemplo de » 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; } } 

Al encapsular la lógica de compensación, el ciclo de procesamiento también se vuelve mucho más simple sin refactorizar gran parte de nada. 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; } 

Comentarios

• Gracias. Parece una mejor implementación. Verificaré esta lógica.
• Encuentro esta respuesta arriba. Usar una clase separada de probar todos los casos.keyWithoutOffset y valueWithoutOffset (creo que vi un error en el código original w.r..t. a eso). Los nombres claros (compensación). Solo los nombres de los métodos están centrados en el mapa en lugar de los de los requisitos.
• Puede usar el ejemplo de la pregunta. Simplemente reemplace [] por {}. queryType es String[] y query es int[][].
• Ah, pasé por alto eso. Y yo ‘ estoy demasiado echado a perder al codificar sitios de desafío simplemente dándome una » Run » botón :-). Modifiqué esta solución en mi propia respuesta ahora.
• ¡La compensación no será la misma para todas las claves en hashmap! – comience con el conjunto de claves (1,2,3) – agregue 10 a todas las claves, ahora el conjunto de claves es (10,11,12) – inserte una nueva clave (5), ahora el conjunto de claves es (10,11,12,5) – agregue 10 para todas las claves, ahora el conjunto de claves es (20,21,22,15). Entonces, las primeras 3 claves efectivamente tenían un desplazamiento 20 agregado, pero la última clave tenía un desplazamiento solo 10 (es decir, las adiciones de claves realizadas antes de que se insertara esta clave (5) se ignorarán).

Tengo algunas sugerencias para ti.

Extrae parte de la lógica de los métodos.

En tu código, cuando la consulta es insert y get, tiene dos grandes bloques de código que son similares; puede extraer a un método y reutilizar el método en ambas secciones.

Sugiero un método que devuelva un valor booleano basado en la condición if, por lo que estará capaz de establecer las variables currValue y currKey en cero.

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

Además, para verificar la consulta actual currQuery, puede extraer cada una de ellas en un método.

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

Utilice siempre las primitivas cuando sea posible

Cuando sabe que es imposible obtener un valor nulo con el número, intente usar las primitivas; toman menos memoria y es más rápido que la clase contenedora.

Antes de

 Integer currKey = 0; Integer currValue = 0;  

Después de

 int currKey = 0; int currValue = 0;  

Intenta poner menos código en switch bloques

En mi opinión, el código se vuelve menos legible cuando hay más de 3 líneas de códigos en un bloque de interruptores; Le sugiero que lo convierta a is-else-if. Esta conversión hará que el código sea más corto y legible.

Antes de

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

Después de

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

Código refactorizado

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

La mayoría operación costosa es la addToKey x que agrega x a todas las claves en el mapa, porque básicamente tienes que crear una nueva clave de entrada, valor + x en tu hashmap y elimine la clave de entrada anterior, value. Para evitar la necesidad de almacenar en caché la entrada anterior mientras se itera sobre el mapa, puede distinguir dos casos:

x > 0, entonces si ha iterado sobre un keyset ordenado descendente no hay necesidad de almacenar en caché las entradas antiguas

x < 0, mismo enfoque pero el keyset está ordenado ascendente

Debido a que está utilizando hashmap, no hay un orden de clave garantizado, por lo que necesita un dato estructura para almacenar las claves a ordenar, antes de iterar sobre las claves como se muestra a continuación:

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

Excluí el caso 0 porque map permanece intacto. Otras operaciones no necesitan el orden de las claves y, como ya se sugirió, sería mejor intentar aislar cada operación en un método privado.

Comentarios

• Gracias @dariosicily por la respuesta. ¿No ‘ t ordenar cada vez que la operación addToKey también es costosa? ¿O puedo usar a SortedMap para mantener el orden de inserción descendente. Por ejemplo, SortedMap<Integer, Integer>values = new TreeMap<Integer, Integer>(Collections.reverseOrder());
• @Praveen De nada. Sí, lo es ordenando cada vez, pero con ArrayList después de ordenar se procede de forma lineal.Me condenaron que solo podía usar HashMap; si puede usar TreeMap en lugar de HashMap, puede usar un iterador y un iterador inverso e iterar sobre su TreeMap de forma directa.

Versión modificada de Respuesta de Johnbot sin una clase adicional. Creo que la clase adicional es excesiva y distrae bastante del algoritmo, ya que tengo que buscar en una gran cantidad de código (mucho de eso es repetitivo) para ver qué está pasando. No es esa clase adicional lo que hace que el ciclo de procesamiento sea mucho más simple. Es el algoritmo.

Más cambios:

• keyOffset no me queda claro en qué dirección se desplaza, así que lo renombré a addedToKey (también para el valor).
• Ordené la operación nombres como en la especificación del problema, tanto para estar cerca de la especificación como porque ese orden tiene más sentido para mí.
• Introduje args para ahorrar algo de repetición de código.
• Se usó long / Long para todo, no solo para la suma. Después de todo, agregar claves / valores podría hacer que se desborden si usamos 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; } 

Comentarios

• ¿Por qué se agrega uniformemente addedToKey al El valor ‘ s clave no funciona, pero restarlo para las acciones insert y get sí ¿Funciona?

¿Qué pasa con almacenar un valor de compensación para claves y valores y construir métodos de envoltura alrededor del hashmaps métodos get / put para tener en cuenta este desplazamiento.