Sugerowałbym utworzenie własnego OffsetIntegerMap, które może mapować między liczbami całkowitymi i obsługiwać przesunięcie kluczy i wartości.

Ty Nie musisz koniecznie implementować HashMap od zera, definiować własnego ograniczonego interfejsu i implementować go z istniejącym Map<Integer, Integer> poprzez kompozycję.

Dzięki obsłudze przesunięć oddzielnie od kluczy i wartości złożoność operacji przesunięcia kończy się wynikiem O (1) zamiast O (n) podczas wykonywania ponownych obliczeń i Map<> operacje put i get pozostają w oryginalnym O (1).

Przykład 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; } } 

Dzięki hermetyzacji logiki przesunięcia pętla przetwarzania również staje się znacznie prostsza bez refaktoryzacji wielu elementów 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; } 

Komentarze

• Dziękuję. Wygląda na lepszą implementację. Sprawdzę tę logikę.
• Ta odpowiedź jest u góry. Używanie klasy niezależnej od testowania wszystkich przypadków.keyWithoutOffset i valueWithoutOffset (wydaje mi się, że widziałem błąd w oryginalnym kodzie z tym). Jasne nazwy (przesunięcie). Tylko nazwy metod są skoncentrowane na mapie, a nie w wymaganiach.
• Możesz użyć przykładu z pytania. Po prostu zamień [] na {}. queryType to String[], a query to int[][].
• Ach, przeoczyłem to. I ' jestem zbyt rozpieszczony kodowaniem witryn z wyzwaniami, które dają mi ” Uruchom ” przycisk :-). Zmodyfikowałem teraz to rozwiązanie w mojej własnej odpowiedzi.
• Przesunięcie nie będzie takie samo dla każdego klucza w hashmap! – zacznij od zestawu kluczy (1,2,3) – dodaj 10 do wszystkich kluczy, teraz zestaw kluczy to (10,11,12) – wstaw nowy klucz (5), teraz zestaw kluczy to (10,11,12,5) – dodaj 10 do wszystkich kluczy, teraz zestaw kluczy to (20,21,22,15). Tak więc pierwsze 3 klucze miały faktycznie dodane przesunięcie 20, ale ostatni klucz miał przesunięcie tylko 10 (tj. Dodawanie klucza wykonane przed wstawieniem tego klucza (5) będzie ignorowane).

Mam dla Ciebie kilka sugestii.

Wyodrębnij część logiki do metod.

W swoim code, gdy zapytanie to insert i get, masz dwa duże bloki kodu, które są podobne; możesz wyodrębnić do metody i ponownie użyć metody w obu sekcjach.

Proponuję metodę, która zwraca wartość logiczną na podstawie warunku if, więc będziesz w stanie ustawić zmienne currValue i currKey na 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; }  

Ponadto, aby sprawdzić bieżące zapytanie currQuery, możesz wyodrębnić każdy z nich w metodzie.

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

Zawsze używaj prymitywów, jeśli to możliwe

Kiedy wiedz, że nie można uzyskać wartości null za pomocą liczby, spróbuj użyć prymitywów; zajmują mniej pamięci i są szybsze niż klasa opakowania.

Przed

 Integer currKey = 0; Integer currValue = 0;  

Po

 int currKey = 0; int currValue = 0;  

Spróbuj umieścić mniej kodu w switch blokach

Moim zdaniem kod staje się mniej czytelny, gdy w bloku przełącznika jest więcej niż 3 wiersze kodu; Proponuję przekonwertować go na is-else-if. Ta konwersja sprawi, że kod będzie krótszy i bardziej czytelny.

Przed

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

Po

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

Refaktoryzowany kod

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

Najczęściej kosztowną operacją jest addToKey x, który dodaje x do wszystkich kluczy w mapie, ponieważ zasadniczo musisz utworzyć nowy klucz wejściowy, wartość + x w swoim hashmap i usuń stary klucz wpisu, wartość. Aby uniknąć potrzeby buforowania starego wpisu podczas iteracji po mapie, możesz wyróżnić dwa przypadki:

x > 0, a następnie jeśli wykonujesz iterację po keyset uporządkowane malejąco, nie ma potrzeby buforowania starych wpisów

x < 0, to samo podejście, ale keyset jest uporządkowany rosnąco

Ponieważ używasz hashmap, nie ma gwarantowanej kolejności kluczy, więc potrzebujesz danych struktura do przechowywania kluczy do zamówienia, przed iteracją po kluczach, jak poniżej:

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

Wykluczyłem przypadek 0 ponieważ map pozostaje nietknięte. Inne operacje nie wymagają kolejności kluczy i jak już zasugerowano, lepiej byłoby spróbować izolować każdą operację w metodzie prywatnej.

Komentarze

• Dzięki @dariosicily za odpowiedź. Czy nie ' t sortowanie za każdym razem podczas wykonywania addToKey operacji jest również kosztowne ?. Czy mogę użyć a SortedMap, aby kolejność reklamowa była malejąca. Na przykład SortedMap<Integer, Integer>values = new TreeMap<Integer, Integer>(Collections.reverseOrder());
• @Praveen Nie ma za co. Tak, sortowanie za każdym razem, ale z ArrayList po sortowaniu postępujesz w sposób liniowy.Zostałem skazany, że możesz użyć tylko HashMap; jeśli możesz użyć TreeMap zamiast HashMap, możesz użyć iteratora i iteratora odwrotnego i wykonać iterację po TreeMap w prosty sposób.

Zmodyfikowana wersja Johnbota” bez dodatkowej klasy. Myślę, że ta dodatkowa klasa jest przesadą i raczej odwraca uwagę od algorytmu, ponieważ muszę przeszukiwać dużo kodu (dużo z tego schematu), aby zobaczyć, co się dzieje. To nie dodatkowa klasa sprawia, że pętla przetwarzania jest znacznie prostsza. To algorytm.

Dalsze zmiany:

• keyOffset nie jest dla mnie jasne, w którym kierunku jest przesunięte, więc zmieniłem jego nazwę na addedToKey (podobnie dla wartości).
• Zamówiłem operację nazwy jak w specyfikacji problemu, zarówno po to, aby pozostać blisko specyfikacji, jak i dlatego, że ta kolejność ma dla mnie większy sens.
• Wprowadzono args, aby zaoszczędzić trochę powtórzeń kodu.
• Używane long / Long do wszystkiego, nie tylko do sumy. W końcu dodanie do kluczy / wartości może spowodować ich przepełnienie, jeśli użyjemy po prostu 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; } 

Komentarze

• Dlaczego w jednolity sposób dodaje się addedToKey do wartość ' nie działa, ale odjęcie go dla działań insert i get nie działa działa?

A co z przechowywaniem wartości przesunięcia dla kluczy i wartości oraz budowaniem metod opakowujących wokół metody hashmaps get / put do uwzględnienia tego przesunięcia.