[Leetcode] Design

satjd

2019/01/08

Categories: Algorithm 基础知识 Tags: leetcode

460. LFU Cache

class LFUCache {
    // key: 源数据的key   value:这个key对应的kv的出现频率
    // 这个map用于快速确定某个kv的出现频率,从而通过下面的freqToDatas找到所在数据
    private HashMap<Integer,Integer> dataFreq;

    // key: 源数据的key   value: 保存这个kv数据的所在链表
    // 这个map用于找到数据的所在位置并进行删除操作
    private HashMap<Integer,LinkedHashMap<Integer,Integer>> data;

    // key:频率   value:这个频率下的所有数据组成的LinkedHashMap
    // 这个map用于找到某个频率下的所有数据
    // 使用treemap是为了更快地找到频率最小的数据
    private TreeMap<Integer,LinkedHashMap<Integer,Integer>> freqToDatas;

    private final int cap;

    public LFUCache(int capacity) {
        this.cap = capacity;
        dataFreq = new HashMap<>(cap);
        data = new HashMap<>(cap);
        freqToDatas = new TreeMap<>();
    }

    public int get(int key) {
        LinkedHashMap<Integer,Integer> entrys = data.get(key);
        Integer value;
        if (entrys == null || (value = entrys.get(key)) == null) {
            return -1;
        }

        Integer oldFreq = dataFreq.get(key);
        Integer nextFreq = oldFreq + 1;

        if (freqToDatas.get(nextFreq) == null) {
            freqToDatas.put(nextFreq,new LinkedHashMap<Integer,Integer>());
        }
        freqToDatas.get(nextFreq).put(key,value);
        freqToDatas.get(oldFreq).remove(key);
        dataFreq.put(key,nextFreq);
        data.put(key, freqToDatas.get(nextFreq));

        return value;
    }

    public void put(int key, int value) {
        if (cap <= 0) {
            return;
        }
        
        Integer oldKeyFreq = dataFreq.get(key);
        Integer newKeyFreq;
        if (oldKeyFreq == null) {
            newKeyFreq = 0;
            dataFreq.put(key,newKeyFreq);
        } else {
            newKeyFreq = oldKeyFreq + 1;
            dataFreq.put(key,newKeyFreq);
            freqToDatas.get(oldKeyFreq).remove(key);
        }

        // 需要在这里进行删除
        // 不能在插入新数据后再删除,因为这样可能会删掉刚插进来的数据
        if (cap < dataFreq.size()) {
            removeLRU();
        }

        LinkedHashMap dataMap = freqToDatas.get(newKeyFreq);
        if (dataMap == null) {
            dataMap = new LinkedHashMap<Integer,Integer>();
            freqToDatas.put(newKeyFreq,dataMap);
        }
        dataMap.put(key,value);
        data.put(key,dataMap);
    }

    private void removeLRU() {
        for (Map.Entry<Integer,LinkedHashMap<Integer,Integer>> e : freqToDatas.entrySet()) {
            if (!e.getValue().isEmpty()) {
                Map.Entry<Integer,Integer> entry = e.getValue().entrySet().iterator().next();
                Integer keyToRemove = entry.getKey();
                e.getValue().remove(keyToRemove);
                data.remove(keyToRemove);
                dataFreq.remove(keyToRemove);
                break;
            }
        }
    }
}

432. All O`one Data Structure

class AllOne {
    // 定义一个数据结构Slot 用于存储值为m的所有key
    private static class Slot {
        public int value;
        public HashSet<String> keys;
        public Slot() {
            
        }
        public Slot(int value, HashSet<String> keys) {
            this.value = value;
            this.keys = keys;
        }
    }
    
    private int minV = 1;
    private int maxV = 1;
    // 建立值为m的value和它的key之间的对应关系
    private HashMap<Integer,Slot> slots;

    // 建立key和它的value之间的对应关系
    private HashMap<String,Integer> data;

    /** Initialize your data structure here. */
    public AllOne() {
        slots = new HashMap<Integer,Slot>();
        data = new HashMap<String,Integer>();
        slots.put(1,new Slot(1,new HashSet<String>()));
    }
    
    // 将值为value的key加入到对应的Slot中
    private void addToSlots(String key, int value) {
        if (slots.get(value) == null) {
            Slot s = new Slot();
            s.value = value;
            s.keys = new HashSet<String>();
            
            slots.put(value,s);
            
            if (value < minV) minV = value;
            if (value > maxV) maxV = value;
        }
        Slot s = slots.get(value);
        s.keys.add(key);
        
        
    }
    
    // 将某个key从对应的value Slot中取出
    private void removeFromSlots(String key, int value) {
        if (data.get(key) == null || slots.get(value) == null) {
            return;
        }
        Slot s = slots.get(value);
        s.keys.remove(key);
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    // 在Slot之间移动key即可
    public void inc(String key) {
        if (!data.containsKey(key)) {
            data.put(key,1);
            addToSlots(key,1);
        } else {
            int value = data.get(key);
            removeFromSlots(key,value);
            addToSlots(key,value + 1);
            data.put(key, value + 1);
        }
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    // 在Slot之间移动key即可
    public void dec(String key) {
        if (!data.containsKey(key)) {
            return;
        }
        int value = data.get(key);
        removeFromSlots(key,value);
        if (value > 1) {
            addToSlots(key,value - 1);
            data.put(key, value - 1);
        } else {
            data.remove(key);
        }
    }
    
    /** Returns one of the keys with maximal value. */
    // 从右向左找到第一个不为空的Slot 并取出一个元素作为返回
    public String getMaxKey() {
        Slot s = slots.get(maxV);
        int temp = maxV;
        while (s.keys.isEmpty()) {
            s = slots.get(--temp);
            if (s == null) {
                return "";
            }
        }
        String ret = "";
        for (String str : s.keys) {
            ret = str;
            break;
        }
        
        return ret;
    }
    
    /** Returns one of the keys with Minimal value. */
    // 从左向右 同理
    public String getMinKey() {
        Slot s = slots.get(minV);
        int temp = minV;
        while (s.keys.isEmpty()) {
            s = slots.get(++temp);
            if (s == null) {
                return "";
            }
        }
        String ret = "";
        for (String str : s.keys) {
            ret = str;
            break;
        }
        
        return ret;
    }
}