[2018カカブラインド]キャッシュ(JAVA)

14700 ワード
アルゴリズム#アルゴリズム# コーディングテスト ProblemSolving テキストリンク
質問する
に答える
2年生の時にやったパソコンの宿題を思い出す.LRUキャッシュの実装...
  • processCity():cityNameをパラメータとして、cacheにHitまたはMissが含まれているかどうかをチェックして処理します.
  • 比較時にエラーが発生しないように大文字cityNameが受信されます
  • processHit():cacheは、既存のCityのcurrentTimeオブジェクトではなく、新しいCityオブジェクトに更新されます.
  • processMiss()a.cacheSizeが0の場合、cacheはリフレッシュされず、所要時間のみが返されます.
    b.cacheが満たされている場合は、LRU()からlestRecentlyVisitedCityが削除されます.
    c.Cityオブジェクトをcacheに追加します.
    • コード#コード#
    import java.util.*;

class Solution {
    
    private static final int HIT = 1;
    private static final int MISS = 5;

    private int cacheSize;
    private Set<City> cache = new HashSet<>();
    private int currentTime;

    public int solution(int size, String[] cities) {
        cacheSize = size;
        processCities(cities);
        return currentTime;
    }

    private void processCities(String[] cities) {
        for (String city : cities)
            currentTime += processCity(city.toUpperCase());
    }

    private int processCity(String cityName) {
        if (cache.contains(new City(cityName)))
            return processHit(cityName);
        else
            return processMiss(cityName);
    }
    
    private int processHit(String cityName) {
        cache.remove(new City(cityName));
        cache.add(new City(cityName, currentTime));
        return HIT;
    }

    private int processMiss(String cityName) {
        if (cacheSize != 0) {   
            if (cache.size() >= cacheSize) LRU();
            cache.add(new City(cityName, currentTime));
        }
        return MISS;
    }

    private void LRU() {
        City leastRecentlyVisitedCity = cache.stream().min(Comparator.comparingInt(o -> o.lastVisitedTime)).orElse(null);
        cache.remove(leastRecentlyVisitedCity);
    }
}

class City {
    String cityName;
    int lastVisitedTime;

    public City(String cityName, int lastVisitedTime) {
        this.cityName = cityName;
        this.lastVisitedTime = lastVisitedTime;
    }

    public City(String cityName) {
        this(cityName, 0);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof City)) return false;
        City city = (City) o;
        return Objects.equals(cityName, city.cityName);
    }

    @Override
    public int hashCode() {
        return Objects.hash(cityName);
    }
}
    【Python】heapq
    演算子と関数(1)