Az alábbi probléma merült fel egy kódolási teszt során, és 28/30 teszt-passzot kaptam, és 2 sikertelen volt időtúllépésig.

probléma
Létrehozott egy programozási nyelvet, és most úgy döntött, hogy hozzáadja a hashmap támogatást. Megállapították, hogy a közös programozási nyelvekben lehetetlen számot adni az összes hashmap kulcshoz / értékhez. Tehát úgy döntött, hogy a következő műveletekkel saját hashmap t hajt végre az új nyelven.

  • insert x y – beszúrás és objektum a x kulccsal és az értékkel y
  • get x – adja vissza az objektum értékét a x

    • kulccsal.

  • addToKey x – add x a térkép összes kulcsához
  • addToValue y – adja hozzá a y elemet a térkép összes értékéhez / li>

Az Ön feladata ennek megvalósítása hashmap, a megadott lekérdezések alkalmazása és a megtalálása A get műveletek összes eredményének összege

Például

  • A queryType=["insert","insert","addToValue","addToKey","get"] és query=[[1,2],[2,3],[2],[1],[3]], a kimenetnek .

Magyarázat

  1. insert 1 2 – a hashmap értéke {1:2}
  2. insert 2 3 – a hashmap lesz: {1:2,2:3}
  3. addToValue 2 – a hashmap lesz: {1:4,2:5}
  4. addToKey 1 – a hashmap értéke {2:4,3:5}
  5. get 3 – az érték 5

Bemenet / Kimenet

  • [végrehajtási időkorlát] 3 másodperc (Java)
  • [input] array.string queryType
    Tömb lekérdezés típusai. garantált, hogy minden queryType[i] a fent említett műveletek bármelyike
    1 < = queryType.length < = 10 ^ 5
  • [input] array.array.integer lekérdezés
    Lekérdezések tömbje, ahol az egyes lekérdezéseket két szám említi a beszúráshoz és egy számot a többi számára. A kulcsértékek a [-10 ^ 9,10 ^ 9] tartományba esnek daf54a121c “>

Az alábbiakban bemutatom a következő megoldást: Java 

long hashMap(String[] queryType, int[][] query) { long sum = 0; Integer currKey = 0; Integer currValue = 0; Map<Integer, Integer> values = new HashMap<>(); for (int i = 0; i < queryType.length; i++) { String currQuery = queryType[i]; switch (currQuery) { case "insert": 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); 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": 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); currValue = 0; currKey = 0; } sum += values.get(query[i][0]); } } return sum; }

Van-e más adatstruktúra, amelyet használhatok a hashmap helyett, vagy javíthatok-e? hogy a kódom lineárisabb legyen?

Megjegyzések

  • Üdvözöljük a Code Review webhelyen. Nem értem, hogy ‘ miért értem, miért hoz létre új Map minden alkalommal, amikor elkészíti a get lekérdezések, ha meg tudod magyarázni, miért értékelem.
  • @dariosicily, az, mert nem ‘ nem akarja felülírni a meglévő értéket egy kulcs vagy térkép frissítése közben. Példa: A (z) {2: 3,3: 1} esetén: Ha hozzá akarja adni az 1-es kulcsot és az 1-es értéket. Az első iterációban a következő lesz: 3: 4}. Itt elveszítem a tényleges 3: 1 arányt, amely a következő kulcsérték pár. Röviden, a kulcsértékpárok felülírása / ütközésének elkerülése érdekében.
  • Köszönöm, most megkaptam.

Válasz

Azt javaslom, hogy hozzon létre saját OffsetIntegerMap -et, amely feltérképezheti az egész számokat, és kezelheti a kulcsok és értékek eltolását.

Ön ne feltétlenül a nulláról kell végrehajtania a HashMap t, meg kell határoznia a saját korlátozott felületét, és a meglévő Map<Integer, Integer> összetétel útján kell megvalósítania.

Ha az eltolásokat a kulcsoktól és értékektől külön kezeljük, akkor az eltolási műveletek bonyolultsága O (1) helyett O (n) helyett végez újraszámításokat, és a Map<> a put and get műveletek az eredeti O (1) értéknél maradnak.

Példa egy ” 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; } }

Az offszet logikájának beágyazásával a feldolgozási ciklus is sokkal egyszerűbbé válik anélkül, hogy bármi nagyot visszafejtenénk 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; }

megjegyzések

  • köszönöm. Jobb megvalósításnak tűnik. Ellenőrizni fogom ezt a logikát.
  • Ezt a választ találom a legjobbnak. Az összes eset tesztelésétől elkülönített osztály használata.keyWithoutOffset és valueWithoutOffset (azt hiszem, hogy az eredeti kódban hibát láttam w.r..t.). A világos nevek (eltolás). Csak a módszer nevei térképközpontúak, a követelményekben szereplőek helyett
  • Használhatja a kérdés példáját. Csak cserélje le a [] szöveget a {} kifejezésre. A queryType String[] és query a int[][].
  • Á, ezt elnéztem. És én ‘ túl elrontottam azzal, hogy a kihívó oldalakat kódoltam, csak egy ” Run ” gomb :-). Ezt a megoldást most a saját válaszomra módosítottam.
  • Az eltolás nem lesz azonos a hashmap minden kulcsán! – kezdje kulcskészlettel (1,2,3) – adjon 10-et az összes kulcshoz, most a kulcskészlet (10,11,12) – helyezzen be új kulcsot (5), most a kulcskészlet (10,11,12,5) – add 10 az összes kulcshoz, most a kulcskészlet (20,21,22,15). Tehát az első 3 kulcs gyakorlatilag 20-at ellensúlyozott, de az utolsó kulcs csak 10-et (azaz a kulcs (5) behelyezése előtt végrehajtott kulcs-kiegészítéseket a rendszer figyelmen kívül hagyja).

Válasz

Van néhány javaslatom az Ön számára.

Bontsa ki a logika egy részét a módszerekhez.

A kód, ha a lekérdezés insert és get, akkor két nagy kódblokk van, amelyek hasonlóak; kivonhatja egy metódusba, és újból felhasználhatja a metódust mindkét szakaszban.

Javaslom egy metódust, amely logikai értéket ad vissza a if feltétel alapján, tehát képes a currValue és currKey változók nullára állítására. 

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

Az aktuális lekérdezés currQuery ellenőrzéséhez mindegyiket kibonthatja egy metódusban. 

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

Mindig használja a primitíveket, ha lehetséges

Amikor tudd, hogy a számmal lehetetlen null értéket kapni, próbáld meg használni a primitíveket; ezek kevesebb memóriát igényelnek és gyorsabbak, mint a burkoló osztály.

Mielőtt 

 Integer currKey = 0; Integer currValue = 0;  

 int currKey = 0; int currValue = 0;

Próbálja meg kevesebb kódot beírni a switch blokkokba

Véleményem szerint a kód kevésbé lesz olvasható, ha egy kapcsolóblokkban több mint 3 kódsor található; Javaslom, hogy alakítsa át is-else-if -re. Ez az átalakítás rövidebbé és olvashatóbbá teszi a kódot. 

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

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

Felújított kód 

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

Válasz

A legtöbb drága művelet az a addToKey x, amely x-et ad hozzá az összes kulcshoz a térképen, mert lényegében új belépési kulcsot, + értéket kell létrehoznia a hashmap és törölje a régi belépési kulcsot, értéket. A régi bejegyzés gyorsítótárazásának elkerülése érdekében a térképen történő iterálás során két esetet különböztethet meg:

x > 0, majd ha egy keyset csökkenő sorrendben nincs szükség a régi bejegyzések gyorsítótárba helyezésére.

x < 0, ugyanaz a megközelítés, de a keyset növekvő sorrendbe van állítva

Mivel a hashmap fájlt használja, nincs garantált kulcsrendelés, ezért adatokra van szüksége felépítés a megrendelt kulcsok tárolására, mielőtt az alábbiak szerint ismételnénk a kulcsokat: 

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

Kizártam az esetet 0 mert map érintetlen marad. Más műveletekhez nincs szükség a kulcsok sorrendjére, és amint már javasoltuk, jobb lehet megpróbálni minden műveletet elkülöníteni egy privát módszerrel.

Megjegyzések

  • Köszönöm @dariosicily a választ. Nem ‘ nem válogat minden alkalommal, miközben a addToKey művelet költséges is? a SortedMap, hogy a beszúrási sorrend csökkenő legyen. Tetszik, SortedMap<Integer, Integer>values = new TreeMap<Integer, Integer>(Collections.reverseOrder());
  • @Praveen Üdvözöljük. Igen, igen rendezés minden alkalommal, de a rendezés után a ArrayList paranccsal lineáris módon folytatja.Elítéltek, hogy csak HashMap használhat; ha a TreeMap szót használhatja a HashMap helyett, használhat egy iterátort és egy fordított iterátort, és iterálhat a >

egyenes módon.

Válasz

A Johnbot válasza extra osztály nélkül . Úgy gondolom, hogy az extra osztály túlzott és inkább elvonja a figyelmet az algoritmusról, mivel sok kódon kell keresnem (sok a kazán), hogy lássuk, mi folyik itt. Nem ez az extra osztály teszi sokkal egyszerűbbé a feldolgozási ciklust. Ez az algoritmus.

További változtatások:

  • keyOffset nem világos számomra, hogy melyik irányba tolódjon el, ezért ezt átneveztem addedToKey -re (az értékre is).
  • A műveletet elrendelte nevek, mint a probléma specifikációban, mind azért, hogy közel maradjak a specifikációhoz, mind azért, mert számomra ez a sorrend értelmesebb.
  • Bevezettük a args kódismétlést.
  • A long / Long elemeket mindenre felhasználta, nemcsak az összegre. Végül is, ha hozzáadjuk a kulcsokhoz / értékekhez, akkor ezek túlcsordulhatnak, ha csak a következőt használjuk: 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; }

Megjegyzések

  • Miért egyenletesen adja hozzá a addedToKey Az érték ‘ s kulcs nem működik, de kivonja a insert és get műveletekhez működik?

Válasz

Mi a helyzet csak a kulcsok és értékek eltolásának eltárolásával és a burkoló metódusok felépítésével a A hashmaps get / put módszerek ennek az ellentételezésnek a figyelembe vételéhez.

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük