Je vous suggère de créer votre propre OffsetIntegerMap qui peut mapper entre des entiers et gérer un décalage sur les clés et les valeurs.

Vous vous navez pas nécessairement à implémenter le HashMap à partir de zéro, à définir votre propre interface limitée et à limplémenter avec un Map<Integer, Integer> existant via la composition.

En gérant les décalages séparément des clés et des valeurs, la complexité des opérations de décalage finit par O (1) au lieu de O (n) lors des recalculs et Map<> les opérations put et get restent à leur O (1) dorigine.

Un exemple an  » 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; } } 

En encapsulant la logique de décalage, la boucle de traitement devient également beaucoup plus simple sans refactoriser une grande partie de tout 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; } 

Commentaires

• Merci. On dirait une meilleure implémentation. Je vais vérifier cette logique.
• Je trouve cette réponse en tête. Utiliser une classe distincte du test de tous les cas.keyWithoutOffset et valueWithoutOffset (je pense avoir vu un bug dans le code original w.r..t. à cela). Les noms clairs (offset). Seuls les noms de méthode sont centrés sur la carte au lieu de ceux des exigences
• Vous pouvez utiliser lexemple de la question. Remplacez simplement [] par {}. queryType est String[] et query est int[][].
• Ah, jai oublié ça. Et je ‘ je suis trop gâté par le codage des sites de défis en me donnant simplement un  » Exécuter  » bouton :-). Jai modifié cette solution dans ma propre réponse maintenant.
• Le décalage ne sera pas le même pour chaque clé de hashmap! – commencer par le jeu de clés (1,2,3) – ajouter 10 à toutes les clés, maintenant le jeu de clés est (10,11,12) – insérer une nouvelle clé (5), maintenant le jeu de clés est (10,11,12,5) – ajouter 10 à toutes les clés, maintenant le jeu de clés est (20,21,22,15). Ainsi, les 3 premières clés avaient effectivement un décalage de 20 ajouté, mais la dernière clé navait quun décalage de 10 (cest-à-dire que les ajouts de clés effectués avant linsertion de cette clé (5) seront ignorés).

Jai quelques suggestions pour vous.

Extrayez une partie de la logique des méthodes.

Dans votre code, lorsque la requête est insert et get, vous avez deux gros blocs de code qui sont similaires; vous pouvez extraire une méthode et réutiliser la méthode dans les deux sections.

Je suggère une méthode qui renvoie un booléen basé sur la condition if, donc vous serez capable de définir les variables currValue et currKey sur zéro.

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

De plus, pour vérifier la requête actuelle currQuery, vous pouvez extraire chacun deux dans une méthode.

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

Utilisez toujours les primitives lorsque cela est possible

Lorsque vous sachez quil est impossible dobtenir une valeur nulle avec le nombre, essayez dutiliser les primitives; elles prennent moins de mémoire et sont plus rapides que la classe wrapper.

Avant

 Integer currKey = 0; Integer currValue = 0;  

Après

 int currKey = 0; int currValue = 0;  

Essayez de mettre moins de code dans les switch blocs

À mon avis, le code devient moins lisible lorsquil y a plus de 3 lignes de codes dans un bloc de commutation; Je vous suggère de le convertir en is-else-if. Cette conversion rendra le code plus court et plus lisible.

Avant

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

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

Le plus lopération coûteuse est addToKey x qui ajoute x à toutes les clés de la carte, car vous devez essentiellement créer une nouvelle clé dentrée, valeur + x dans votre hashmap et supprimez lancienne clé dentrée, valeur. Pour éviter davoir à mettre en cache lancienne entrée lors de litération sur la carte, vous pouvez distinguer deux cas:

x > 0, alors si vous avez une itération sur un keyset en ordre décroissant, il nest pas nécessaire de mettre en cache les anciennes entrées

x < 0, même approche mais le keyset est ordonné par ordre croissant

Comme vous utilisez hashmap, il ny a pas dordre de clé garanti, vous avez donc besoin de données structure pour stocker les clés à commander, avant ditérer sur les clés comme ci-dessous:

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

Jai exclu le cas 0 car map reste intact. Dautres opérations nont pas besoin de lordre des clés et, comme déjà suggéré, il serait préférable dessayer disoler chaque opération dans une méthode privée.

Commentaires

• Merci @dariosicily pour la réponse. Le tri ‘ t à chaque fois lors de lopération addToKey est également coûteux? Ou puis-je utiliser a SortedMap pour maintenir lordre dinsertion décroissant. Comme, SortedMap<Integer, Integer>values = new TreeMap<Integer, Integer>(Collections.reverseOrder());
• @Praveen Vous êtes les bienvenus. Oui, cest tri à chaque fois, mais avec ArrayList après le tri, vous procédez de manière linéaire.Jai été condamné, vous ne pouviez utiliser que HashMap; si vous pouvez utiliser TreeMap au lieu de HashMap, vous pouvez utiliser un itérateur et un itérateur inversé et itérer sur votre TreeMap de manière directe.

Version modifiée de Réponse de Johnbot sans une classe supplémentaire. Je pense que la classe supplémentaire est exagérée et distrait plutôt de lalgorithme, car je dois rechercher beaucoup de code (beaucoup de passe-partout) pour voir ce qui se passe. Ce nest pas cette classe supplémentaire qui rend la boucle de traitement beaucoup plus simple. Cest lalgorithme.

Autres modifications:

• keyOffset ne mest pas clair dans quelle direction il est décalé, alors je lai renommé en addedToKey (de même pour la valeur).
• Jai commandé lopération noms comme dans la spécification du problème, à la fois pour rester proche de la spécification et parce que cet ordre a plus de sens pour moi.
• Introduit args pour éviter la répétition du code.
• Utilisé long / Long pour tout, pas seulement pour la somme. Après tout, lajout aux clés / valeurs pourrait les faire déborder si nous nutilisons que 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; } 

Commentaires

• Pourquoi ajouter uniformément addedToKey au La clé de la valeur ‘ ne fonctionne pas, mais la soustraire pour les actions insert et get fonctionne fonctionne?

Quen est-il simplement de stocker une valeur de décalage pour les clés et les valeurs et de créer des méthodes dencapsulation autour du hashmaps get / put méthodes pour tenir compte de ce décalage.