Vă sugerez să creați propriul dvs. OffsetIntegerMap care poate mapa între numere întregi și gestiona un offset pe chei și valori.

nu trebuie neapărat să implementați HashMap de la zero, să vă definiți propria interfață limitată și să o implementați cu un Map<Integer, Integer> existent prin compoziție.

Prin manipularea compensărilor separat de taste și valori, complexitatea operațiunilor de compensare ajunge la O (1) în loc de O (n) atunci când se fac recalculări și Map<> operațiile de punere și obținere rămân la O (1) originală.

Un exemplu și un ” 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; } } 

Prin încapsularea logicii de offset, bucla de procesare devine, de asemenea, mult mai simplă, fără a refactora o mare parte din nimic 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; } 

Comentarii

• Mulțumesc. Pare o implementare mai bună. Voi verifica această logică.
• Găsesc acest răspuns de sus. Folosirea unei clase separate de testarea tuturor cazurilor.keyWithoutOffset și valueWithoutOffset (cred că am văzut o eroare în codul original w.r..t. la asta). Numele clare (offset). Numele metodelor sunt centrate pe hartă în locul celor din cerințe.
• Puteți folosi exemplul din întrebare. Doar înlocuiți [] cu {}. queryType este String[] și query este int[][].
• Ah, am trecut cu vederea asta. Și eu ‘ sunt prea răsfăț codând site-urile provocatoare, oferindu-mi doar un ” Run ” buton :-). Am modificat această soluție în propriul meu răspuns acum.
• Decalajul nu va fi același pentru fiecare cheie din hashmap! – începeți cu setul de taste (1,2,3) – adăugați 10 la toate tastele, acum setul de taste este (10,11,12) – introduceți noua cheie (5), acum setul de taste este (10,11,12,5) – adăugați 10 pentru toate tastele, acum setul de taste este (20,21,22,15). Deci, primele 3 chei au compensat efectiv 20 adăugate la ele, dar ultima cheie a compensat doar 10 (adică adăugările de chei făcute înainte de introducerea acestei chei (5) vor fi ignorate).
  

  Răspuns

  Am câteva sugestii pentru dvs.

  Extrageți o parte din logică metodelor.

  În cod, când interogarea este insert și get, aveți două blocuri mari de cod care sunt similare; puteți extrage într-o metodă și reutiliza metoda în ambele secțiuni.

  Vă sugerez o metodă care returnează o metodă booleană pe baza condiției if, așa că veți fi capabil să seteze variabilele currValue și currKey la 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; }  

  De asemenea, pentru a verifica interogarea curentă currQuery, puteți extrage fiecare dintre ele într-o metodă.

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

  Utilizați întotdeauna primitivele când este posibil

  Când știți că este imposibil să obțineți o valoare nulă cu numărul, încercați să utilizați primitivele; acestea ocupă mai puțină memorie și sunt mai rapide decât clasa wrapper.

  Înainte de

   Integer currKey = 0; Integer currValue = 0;  

  După

   int currKey = 0; int currValue = 0;  

  Încercați să puneți mai puțin cod în switch blocuri

  În opinia mea, codul devine mai puțin lizibil atunci când există mai mult de 3 linii de coduri într-un bloc de comutare; Vă sugerez să îl convertiți într-un is-else-if. Această conversie va face codul mai scurt și mai ușor de citit.

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

  După

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

  Cod refactorizat

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

  Răspuns

  Cel mai operațiunea costisitoare este addToKey x care adaugă x la toate cheile din hartă, deoarece în mod substanțial trebuie să creați o nouă cheie de intrare, valoare + x în

  x > 0, atunci dacă ați itera peste keyset ordonat descendent nu este nevoie să memorați în cache vechile intrări

  x < 0, aceeași abordare, dar keyset este comandat crescător

  Deoarece utilizați hashmap, nu există nicio comandă de chei garantată, deci aveți nevoie de date structură pentru a stoca cheile care urmează să fie comandate, înainte de a itera peste chei ca mai jos:

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

  Am exclus cazul 0 deoarece map rămâne neatins. Alte operații nu au nevoie de ordinea cheilor și, așa cum sa sugerat deja, ar putea fi mai bine să încercați să izolați fiecare operație într-o metodă privată.

  Comentarii

  • Mulțumim @dariosicily pentru răspuns. Nu este ‘ sortarea de fiecare dată în timp ce operația addToKey este costisitoare, de asemenea?. Sau pot folosi a SortedMap pentru a menține ordinea de inserare descrescătoare. De exemplu, SortedMap<Integer, Integer>values = new TreeMap<Integer, Integer>(Collections.reverseOrder());
  • @Praveen Sunteți binevenit. Da, este sortarea de fiecare dată, dar cu ArrayList după sortare procedați într-un mod liniar.Am fost condamnat că poți folosi numai HashMap; dacă puteți utiliza TreeMap în loc de HashMap puteți utiliza un iterator și un iterator invers și iterați peste TreeMap într-un mod direct.

  Răspuns

  Versiune modificată a Johnbot fără o clasă suplimentară. Cred că clasa suplimentară este excesivă și distrage atenția de la algoritm, deoarece trebuie să caut prin multe coduri (o mulțime de boilerplate) pentru a vedea ce se întâmplă. Nu este acea clasă suplimentară care face bucla de procesare mult mai simplă. Este algoritmul.

  Modificări suplimentare:

  • keyOffset nu îmi este clar în ce direcție este decalat, așa că l-am redenumit în addedToKey (la fel pentru valoare).
  • Am comandat operațiunea nume ca în specificația problemei, atât pentru a rămâne aproape de specificație, cât și pentru că acea ordine are mai mult sens pentru mine.
  • A introdus args pentru a salva repetarea codului.
  • S-a folosit long / Long pentru toate, nu doar pentru sumă. La urma urmei, adăugarea la chei / valori ar putea face ca acestea să depășească dacă folosim doar 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; } 

  Comentarii

  • De ce se adaugă în mod uniform addedToKey cheia valorii ‘ nu funcționează, totuși scăzând-o pentru acțiunile insert și get funcționează?

  Răspuns

  Dar despre stocarea unei valori offset pentru chei și valori și construirea metodelor de împachetare în jurul hashmap-urile obțin / pun metode pentru a contabiliza acest offset.