模拟 2016-7-13

[dayang]

LeetCode 146 LRU Cache

poj 1676 What time is it?

[SnackMen]

/*
*LeetCode 146 LRU Cache   AC
*
*/
import java.util.LinkedHashMap;  
import java.util.Map;
public class LRUCache {
    private Map<Integer,Integer> map;
    private int capacity;
    public LRUCache(int capacity) {
        this.capacity=capacity;
        map = new LinkedHashMap<Integer,Integer>(capacity){
            //如果达到最大容量，删除末尾不活跃的值
            @Override protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest){
                return size() > capacity;
            }};
        }
    public int get(int key){
       if(map.containsKey(key)){//重新更改顺序，保证在最前面
            int value = map.get(key);  
            map.remove(key);  
            map.put(key, value);  
            return value;  
        }  

        return -1;
    }
    public void set(int key, int value) {
        if(map.containsKey(key))
            map.remove(key);
        map.put(key,value);
    }
}

[dayang]

[AC] LeetCode 146 LRU Cache

/**
 * @constructor
 */
var LRUCache = function(capacity) {
    this.node = function(y,next,pre){
        this.value = y;
        this.next = next;
        this.pre = pre;
    }
    this.capacity = capacity;
    this.used = 0;
    this.memery = {};
    this.head = 0;
    this.tail = 0;
};

/**
 * @param {number} key
 * @returns {number}
 */
LRUCache.prototype.get = function(key) {
    if(!this.memery[key])
        return -1;
    else{
        if(key == this.head){
            return this.memery[key].value;
        }
        if(key == this.tail){
            this.tail = this.memery[this.tail].pre;
        }
        var temp = this.memery[key];
        this.memery[temp.pre].next = temp.next;
        this.memery[temp.next].pre = temp.pre;
        this.memery[key].next = this.head;
        this.memery[key].pre = this.memery[this.head].pre;
        this.memery[this.memery[this.head].pre].next = key;
        this.memery[this.head].pre = key;
        this.head = key;
        return temp.value;
    }
};

/**
 * @param {number} key
 * @param {number} value
 * @returns {void}
 */
LRUCache.prototype.set = function(key, value) {
    if(!this.memery[key]){
        if(this.used ===0){
            this.head = this.tail = key;
            this.memery[key] = new this.node(value,key,key);
            this.used++;
        }else if(this.used < this.capacity){ 
            this.memery[key] = new this.node(value,this.head,this.memery[this.head].pre);
            this.memery[this.memery[this.head].pre].next = key;
            this.memery[this.head].pre = key;
            this.head = key;
            this.used++;
        }else{
            this.memery[key] = new this.node(value,this.head,this.memery[this.head].pre);
            this.memery[this.memery[this.head].pre].next = key;
            this.memery[this.head].pre = key;
            this.head = key;
            var t = this.tail;
            var pre = this.memery[t].pre;
            this.memery[pre].next = this.memery[t].next;
            this.memery[this.memery[t].next].pre = pre;
            this.tail = pre;
            delete this.memery[t];
        }
    }else{
        if(key == this.head){
            this.memery[key].value = value;
            return;
        }
        if(key == this.tail){
            this.tail = this.memery[this.tail].pre;
        }
        var temp = this.memery[key];
        this.memery[key].value = value;
        this.memery[temp.pre].next = temp.next;
        this.memery[temp.next].pre = temp.pre;
        this.memery[key].next = this.head;
        this.memery[key].pre = this.memery[this.head].pre;
        this.memery[this.memery[this.head].pre].next = key;
        this.memery[this.head].pre = key;
        this.head = key;
    }
};

[zhaokuohaha]

LeetCode 146 - C# - 66666啊

public class node
{
    public int value { get; set; }
    public int prevkey { get; set; }
    public int nextkey { get; set; }

    public node()
    {
        value = 0;
        prevkey = -1;
        nextkey = -1;
    }

    public node(int val, int pre, int nex)
    {
        value = val;
        prevkey = pre;
        nextkey = nex;
    }
}
public class LRUCache
{
    Dictionary<int, node> obj = new Dictionary<int, node>();
    int cap;
    node head;  
    public LRUCache(int capacity)
    {
        obj.Add(-1, new node());
        head = obj[-1];
        cap = capacity;
    }

    public int Get(int key)
    {

        if (!obj.ContainsKey(key)) 
            return -1;
        node  res = obj[key];

        obj[res.prevkey].nextkey = res.nextkey;
        obj[res.nextkey].prevkey = res.prevkey;

        res.prevkey = -1;
        res.nextkey = head.nextkey;

        obj[res.nextkey].prevkey = key;
        head.nextkey = key;

        return res.value;
    }
    public void Set(int key, int value)
    {
        if (obj.ContainsKey(key))
        {
            obj[key].value = value;
            Get(key);
        }
        else
        {
            node res = new node(value, -1, head.nextkey);
            obj.Add(key, res);
            obj[res.nextkey].prevkey = key;
            head.nextkey = key;
            if (obj.Count >= cap+2)
            {
                head.prevkey = obj[head.prevkey].prevkey;
                obj.Remove(obj[head.prevkey].nextkey);
                obj[head.prevkey].nextkey = -1;
            }
        }
    }
}