Any suggestion?


  • -2
    D

    Here is my java code passed OJ, I modify my previous code to it so some variable name seems strange, the unit class is actually a node class,I used a double linked list, to avoid iterate through the list, I create an array of node references with a very large size(100000,"unit[ ] data=new unit[100000]") to get O(1) time complexity while the space complexity is too huge, any suggestion for that?Please do not tell me hashmap,hashset,hashtable,ArrayList<Node>, because the OJ compiler do not compile them for me, that is why I used a huge reference array, by the way, anyone tell me what is wrong with the OJ compiler?Why it doesn`t compile them for me? What JDK version does it use?my os is ubuntu Saucy Salamander

    public class LRUCache{
    
    	
    	public class unit{
    		int key;
    		int value;
    		unit pre;
    		unit next; 
    		
    		
    		public unit(int a,int b){
    			key=a;
    			value=b;
    		pre=null;
    		next=null;
    		}
    	}
    	
    		private unit me=new unit(0,0);
    		private unit end;
    		private unit[] data=new unit[100000];
    		int capacity;
    		int count=0;
    		boolean fullFlag=false;
    		
    
    	 public LRUCache(int capacity) {
    		 if (capacity<1) {
    			System.out.println("Invalid capacity of the LRCCache");
    			return;
    		} 
    		 this.capacity=capacity;
    
    	    }
    	    
    	    public int get(int key) {
    	    	if (data[key]==null) {
    				return -1;
    			}else {
    				
    				if (capacity==1) {
    					return data[key].value;
    				}else {
    
    					if (data[key].next==null) {
    						return data[key].value;
    					}
    					
    					data[key].pre.next=data[key].next;
    					data[key].next.pre=data[key].pre;
    					
    					data[key].pre=end;
    					end.next=data[key];
    					data[key].next=null;
    					end=data[key];
    					return data[key].value;	
    				}
    				
    			}
    	    	
    	    }
    	    
    	    public void set(int key, int value) {
    
    	    	if (capacity==1) {
    				if (me.next==null) {
    					unit t=new unit(key, value);
    					me.next=t;
    					t.pre=me;
    					fullFlag=true;
    					end=t;
    					data[key]=t;
    					return;
    					
    				}else {
    					if (data[key]==null) {
    						if (me.next.key==key) {
    							me.next.value=value;
    						}else {
    							data[me.next.key]=null;
    							unit t=new unit(key, value);
    							
    							data[key]=t;
    							me.next=t;
    							t.pre=me;
    							end=t;
    					
    							
    						}
    					}	
    				}	
    			}
    	    	
    	    	else {//when capacity is not 1 
    				if (me.next==null) {//when capacity is not 1 and linked list is empty
    					unit t=new unit(key, value);
    					me.next=t;
    					t.pre=me;
    					count++;
    					end=t;
    					data[key]=t;
    				}else {//when capacity is not 1 and linked list is not empty
    					if (fullFlag) {
    						if (data[key]==null) {
    							data[me.next.key]=null;
    							me.next=me.next.next;
    							me.next.pre=me;
    							unit t=new unit(key, value);
    							data[key]=t;
    							end.next=t;
    							t.pre=end;
    							end=t;
    						}else {
    							data[key].value=value;
    							int k=get(key);
    						}
    					}else {//when capacity is not 1 and linked list is not empty, and it is not full, add into the new one
    						if (data[key]==null) {
    							unit t=new unit(key, value);
    							end.next=t;
    							t.pre=end;
    				            end=t;			
    							data[key]=t;
    							count++;
    							if(count==capacity)fullFlag=true;								
    						}else {//if key exists, change value and update the order of key
    							data[key].value=value;
    							int k=get(key);
    							
    						}
    					}
    				}
    			}
    			}
    }

  • 0
    S

    Please format your code correctly. You can select all your code then click {} button.


  • 0
    L

    Well, HashMap works fine for the rest of us. Are you sure you use it correctly?


  • 0
    D
    This post is deleted!

  • 0
    S

    I have edit it correctly for you. I am not the one who vote down your post, everyone has the privilege to do it.


  • 0
    D

    @loick,thank you for your reply, I tried to put them in eclipse and no compile error but when post in OJ it reports compile error, it should be the same to everyone so maybe its my browser or os problem, thank you for telling me that, I will try other ways to use OJ,Im not trying to challenge leetcode organiser,actually I like leetcode and enjoy solving problems on OJ @Shangrila


  • 0
    D

    @Shangrila, Sorry for my words and thank you for editing


  • 0
    G

    I noticed that in OJ, jdk1.7 notation of collections doesn't work.
    e.g. HashMap<Integer,Integer> map = new HashMap<>() won't work and OJ will give error.
    But HashMap<Integer,Integer> map = new HashMap<Integer, Integer>() will work.


Log in to reply
 

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