运行时间最快击败了99.81%提交 JAVA


  • 0
    Y

    public class LRUCache {
    private int mLength = 1600;
    private Item[] mItems = null;
    private Cache mCacheStart;
    private Cache mCacheEnd;
    private int mCapacity;
    int size;

    public LRUCache(int capacity) {
    	mCapacity = capacity;
    	
    	mLength = capacity < 16 ? 16 : capacity;
    	mItems = new Item[mLength];
    }
    
    public int get(int key) {
    	int n = getN(key);
    	Item item = mItems[n];
    	if(item == null)return -1;
    	while(item!= null){
    		if(key == item.key){
    			break;
    		}
    		item = item.next;
    	}
    	if(item == null) return -1;
    	moveCache(item);
    	//		print(key);
    	return item.value;
    }
    
    void print(int key){
    	//		Cache cache = mCacheStart;
    	//		System.out.print(key+"   =   ");
    	//		while(cache != null){
    	//			System.out.print("    "+cache.item.key+"="+cache.item.value);
    	//			cache = cache.next;
    	//		}
    	//		System.out.println();
    }
    
    public void set(int key, int value) {
    
    	Item item = mItems[getN(key)];
    	while(item != null){
    		if(item.key == key){
    			item.value = value;
    			break;
    		}
    		item = item.next;
    	}
    	if(item == null){
    		if(size == mCapacity){
    			remove();
    		}
    		item = newItem(key , value);
    		newCache(item);
    	}else{
    		moveCache(item);
    	}
    	//		print(key);
    }
    
    
    
    private Item newItem(int key , int value){
    	int n = getN(key);
    	mItems[n] = new Item(key , value , mItems[n]);
    	size ++;
    	return mItems[n]; 
    }
    
    private void newCache(Item item){
    	Cache cache = new Cache(item);
    	if(mCacheStart == null){
    		mCacheStart = cache;
    	}else{
    		mCacheEnd.next = cache;
    		cache.font = mCacheEnd;
    	}
    	cache.next = null;
    	mCacheEnd = cache;
    	item.cache = cache;
    }
    
    private void moveCache(Item item){
    	Cache c = item.cache;
    	if(c.next == null) return;
    	if(c == mCacheStart || c.font == null){
    		mCacheStart = c.next;
    		mCacheStart.font = null;
    	}else{
    		c.font.next = c.next;
    		c.next.font = c.font;
    	}
    	c.next = null;
    	mCacheEnd.next = c;
    	c.font = mCacheEnd;
    	mCacheEnd = c;
    }
    
    
    private int getN(int key){
    	return key % (mLength-1);
    }
    
    private void remove(){
    	Cache removeCache = mCacheStart;
    	mCacheStart = mCacheStart.next;
    	if(mCacheStart != null){
    		mCacheStart.font = null;
    	}
    	int N = getN(removeCache.item.key);
    	Item itemRoot = mItems[N];
    	Item item = removeCache.item;
    	if(itemRoot == item || item.font == null){
    		mItems[N] = item.next;
    		if(mItems[N] != null){
    			mItems[N].font = null;
    		}
    	}else{
    		item.font.next = item.next;
    		if(item.next != null){
    			item.next.font = item.font;
    		}
    	}
    	size --;
    }
    
    
    class Item{
    	public int key;
    	public int value;
    	public Item next;
    	public Item font;
    	public Cache cache;
    	public Item(int key ,int value , Item next){
    		this.key = key;
    		this.value = value;
    		this.next = next;
    		if(next != null){
    			next.font = this;
    		}
    	}
    }
    class Cache{
    	public Item item;
    	public Cache font;
    	public Cache next;
    	public Cache(Item item){
    		this.item = item;
    	}
    }
    

    }


  • 0
    B

    @youjiannuo Good idea to mock HashMap


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.