Ik zou willen voorstellen dat je je eigen OffsetIntegerMap maakt die kan toewijzen tussen gehele getallen en een offset op de sleutels en waarden kan verwerken.

Jij hoef niet per se de HashMap helemaal opnieuw te implementeren, definieer je eigen beperkte interface en implementeer deze met een bestaande Map<Integer, Integer> via compositie.

Door de offsets apart van de toetsen en waarden af te handelen, wordt de complexiteit van de offsetbewerkingen O (1) in plaats van O (n) bij herberekeningen en de Map<> put- en get-bewerkingen blijven op hun oorspronkelijke O (1).

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

Door de offsetlogica in te kapselen wordt de verwerkingslus ook veel eenvoudiger zonder veel van iets te refactoren 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; } 

Reacties

• Bedankt. Ziet eruit als een betere implementatie. Ik zal deze logica controleren.
• Ik vind dit antwoord bovenaan. Een klasse gebruiken die losstaat van het testen van alle gevallen.keyWithoutOffset en valueWithoutOffset (ik denk dat ik een bug in de originele code zag w.r..t. daarmee). De duidelijke namen (offset). Alleen de namen van de methoden zijn kaartcentrisch in plaats van die in de vereisten.
• U kunt het voorbeeld uit de vraag gebruiken. Vervang gewoon [] door {}. queryType is String[] en query is int[][].
• Ah, dat heb ik over het hoofd gezien. En ik ‘ ben te verwend met het coderen van uitdagingsites door me alleen een ” Run ” te geven knop :-). Ik heb deze oplossing nu gewijzigd in mijn eigen antwoord.
• Offset zal niet voor elke sleutel in hashmap hetzelfde zijn! – begin met keyset (1,2,3) – voeg 10 toe aan alle sleutels, nu keyset is (10,11,12) – voeg nieuwe key (5) in, nu keyset is (10,11,12,5) – toevoegen 10 voor alle sleutels, nu is de keyset (20,21,22,15). Dus aan de eerste 3 sleutels was in feite offset 20 toegevoegd, maar de laatste sleutel had slechts een offset van 10 (dwz toevoegingen die zijn gedaan voordat deze sleutel (5) werd ingevoegd, worden genegeerd).

Ik heb een paar suggesties voor je.

Pak een deel van de logica van methoden uit.

In je code, als de zoekopdracht insert en get is, heb je twee grote blokken code die op elkaar lijken; je kunt naar een methode extraheren en de methode in beide secties opnieuw gebruiken.

Ik stel een methode voor die een booleaanse waarde retourneert op basis van de if -voorwaarde, dus je zult in staat om de variabelen currValue en currKey variabelen op nul te zetten.

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

Om de huidige zoekopdracht currQuery te controleren, kunt u ze ook allemaal met een methode extraheren.

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

Gebruik altijd de primitieven indien mogelijk

Wanneer je weet dat het onmogelijk is om een null-waarde te krijgen met het nummer, probeer de primitieven te gebruiken; ze nemen minder geheugen in beslag en zijn sneller dan de wrapper-klasse.

Voor

 Integer currKey = 0; Integer currValue = 0;  

Na

 int currKey = 0; int currValue = 0;  

Probeer minder code in switch blokken

Naar mijn mening wordt de code minder leesbaar als er meer dan 3 regels codes in een schakelblok zitten; Ik stel voor dat je het converteert naar een is-else-if. Deze conversie maakt de code korter en beter leesbaar.

Voor

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

Na

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

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

De meeste dure operatie is de addToKey x die x toevoegt aan alle sleutels op de kaart, omdat je substantieel een nieuwe toegangssleutel moet maken, waarde + x in je hashmap en verwijder de oude toegangssleutel, value. Om te voorkomen dat het oude item in het cachegeheugen moet worden opgeslagen tijdens het itereren van de kaart, kunt u twee gevallen onderscheiden:

x > 0, als u iteratie over een keyset aflopend geordend, het is niet nodig om de oude items in de cache op te slaan

x < 0, dezelfde benadering maar de keyset is oplopend gerangschikt

Omdat je hashmap gebruikt, is er geen sleutelvolgorde gegarandeerd, dus je hebt een structuur om sleutels op te slaan die moeten worden besteld, voordat de sleutels worden herhaald zoals hieronder:

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

Ik heb de hoofdletter 0 uitgesloten omdat map onaangetast blijft. Andere operaties hebben geen “volgorde van de sleutels nodig en zoals reeds gesuggereerd, zou het beter kunnen zijn om elke operatie in een privé methode te isoleren.

Reacties

• Bedankt @dariosicily voor het antwoord. Is niet ‘ t sorteren elke keer dat addToKey bewerking ook duur is ?. Of kan ik gebruiken een SortedMap om de invoegvolgorde aflopend te houden. Zoals SortedMap<Integer, Integer>values = new TreeMap<Integer, Integer>(Collections.reverseOrder());
• @Praveen Graag gedaan. Ja, dat is zo elke keer sorteren, maar met ArrayList na het sorteren ga je op een lineaire manier te werk.Ik ben veroordeeld dat je alleen HashMap; als je TreeMap kunt gebruiken in plaats van HashMap, kun je een iterator en een omgekeerde iterator gebruiken en je op een directe manier.

Gewijzigde versie van Johnbots antwoord zonder een extra klas. Ik denk dat de extra klas overdreven is en nogal afleidt van het algoritme, aangezien ik veel code moet doorzoeken (veel boilerplate) om te zien wat er aan de hand is. Het is niet die extra klasse die de verwerkingslus veel eenvoudiger maakt. Het is het algoritme.

Verdere wijzigingen:

• keyOffset is mij niet duidelijk in welke richting het verschoven is, dus heb ik dat hernoemd naar addedToKey (eveneens voor waarde).
• Bestelde de bewerking namen zoals in de probleemspecificatie, zowel om dicht bij de specificatie te blijven als omdat die volgorde voor mij logischer is.
• Geïntroduceerd args om wat codeherhaling te besparen.
• Gebruikt long / Long voor alles, niet alleen voor de som. Het toevoegen aan de sleutels / waarden zou ze tenslotte kunnen doen overlopen als we int / Integer gebruiken.

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

Reacties

• Waarom wordt addedToKey uniform toegevoegd aan de waarde ‘ s sleutel werkt niet, maar aftrekken voor de insert en get acties werkt wel werk?

Hoe zit het met het opslaan van een offsetwaarde voor sleutels en waarden en het bouwen van wrapper-methoden rond de hashmaps krijgen / put-methoden om rekening te houden met deze verschuiving.