strange thing !! I get the right output however the output of leetcode is wrong,does anybody help to find out why?Thanks!


  • 0
    M

    My Solution pass 12/15 case and WA in the 12th,however , when i run this test case in my local machine,the leetcode output result is not the same as my local output,and my local output is exactly the same as the expect one.I check the test case many times , and my jdk version is 1.8.0,same as the jdk version provided by leetcode , and i also run my code in online compiler .

    So does anybody may run my code in your machine , and submit it to leetcode to find out what is going wrong with my code.

    thanks a lot!

    here is my code;
    //Allone.java

    
    import java.util.HashMap;
    import java.util.HashSet;
    
    class AllOne {
    	
    	private class StrNode {
    		private String string;
    		private int value;
    
    		public StrNode pre_node;// should be private
    		public StrNode post_node;// should be private
    
    		public StrNode(String string, int value) {
    			super();
    			this.string = string;
    			this.value = value;
    		}
    	}
    
    	public StrNode head_node;
    	public StrNode tail_node;
    	public int linklist_size;
    
    	public HashMap<String, StrNode> hashMap;
    
    	/** Initialize your data structure here. */
    	public AllOne() {
    
    		head_node = null;
    		tail_node = null;
    		linklist_size = 0;
    		hashMap = new HashMap<>();
    
    	}
    
    	/**
    	 * Inserts a new key <Key> with value 1. Or increments an existing key by 1.
    	 */
    	public void inc(String key) {
    
    		if (null == key)
    			return;
    
    		if (linklist_size == 0) {
    
    			StrNode new_one = new StrNode(key, 1);
    			hashMap.put(key, new_one);
    			head_node = new_one;
    			tail_node = new_one;
    
    			new_one.post_node = null;
    			new_one.pre_node = null;
    
    			linklist_size++;
    
    		}
    
    		else if (linklist_size == 1) {
    
    			if (key == head_node.string)
    				head_node.value++;
    
    			else {
    
    				StrNode new_one = new StrNode(key, 1);
    				hashMap.put(key, new_one);
    
    				tail_node = new_one;
    
    				head_node.post_node = tail_node;
    				head_node.pre_node = null;
    				tail_node.pre_node = head_node;
    				tail_node.post_node = null;
    				
    				linklist_size++;
    
    			}
    
    		}
    
    		else {// add to the tail
    
    			// alread exist string
    			if (hashMap.containsKey(key)) {
    				
    				StrNode one = hashMap.get(key);
    				one.value++;
    				
    				//change the one and one.pre_node
    				if (one.pre_node != null && one.value > one.pre_node.value)
    					change_node(one.pre_node,one);
    				//change the one and one.post_node
    				else if (one.post_node != null && one.value < one.post_node.value)
    					change_node(one,one.post_node);
    				
    
    			} else {
    				// not exsit string
    				StrNode new_one = new StrNode(key, 1);
    				hashMap.put(key, new_one);
    
    				new_one.pre_node = tail_node;
    				tail_node.post_node = new_one;
    				tail_node = new_one;
    				tail_node.post_node = null;
    				
    
    				linklist_size++;
    			}
    
    		}
    
    	}
    
    	private void change_node(StrNode pre_one, StrNode post_one) {
    		// TODO Auto-generated method stub
    		//change the pre_node and post_node
    		
    		if (pre_one == head_node) {
    			
    			if (post_one == tail_node) {
    				
    				head_node = post_one;
    				tail_node = pre_one;
    				
    				head_node.pre_node = null;
    				head_node.post_node = tail_node;
    				
    				tail_node.pre_node = head_node;
    				tail_node.post_node = null;
    				
    			}
    			else {
    				
    				StrNode post_post = post_one.post_node;
    				
    				head_node = post_one;
    				
    				post_one.pre_node = null;
    				post_one.post_node = pre_one;
    				
    				pre_one.pre_node = post_one;
    				pre_one.post_node = post_post;
    				
    				post_post.pre_node = pre_one;
    
    			}
    			return;
    		}
    		
    		if (post_one == tail_node) {
    			//pre_node != head_node
    			
    			StrNode pre_pre = pre_one.pre_node;
    			
    			tail_node = pre_one;
    			
    			pre_one.post_node = null;
    			pre_one.pre_node = post_one;
    			
    			post_one.post_node = pre_one;
    			post_one.pre_node = pre_pre;
    			
    			pre_pre.post_node = post_one;
    			
    			return;
    		}
    		
    		StrNode pre_pre = pre_one.pre_node;
    		StrNode post_post = post_one.post_node;
    		
    		pre_pre.post_node = post_one;
    		post_post.pre_node = pre_one;
    		
    		pre_one.pre_node = post_one;
    		pre_one.post_node = post_post;
    		
    		post_one.post_node = pre_one;
    		post_one.pre_node = pre_pre;
    		
    	}
    
    	/**
    	 * Decrements an existing key by 1. If Key's value is 1, remove it from the
    	 * data structure.
    	 */
    	public void dec(String key) {
    		
    		if (null == key || hashMap.containsKey(key) == false) 
    			return;
    		
    		StrNode one = hashMap.get(key);
    		
    		if (one.value == 1)
    		{
    			delete_node(one);
    			hashMap.remove(key);
    		}
    			
    		else
    		{
    			one.value--;
    			//change the one and one.pre_node
    			if (one.pre_node != null && one.value > one.pre_node.value)
    				change_node(one.pre_node,one);
    			//change the one and one.post_node
    			else if (one.post_node != null && one.value < one.post_node.value)
    				change_node(one,one.post_node);
    		}
    	}
    
    	private void delete_node(StrNode one) {
    		// TODO Auto-generated method stub
    		if (one == null) return;
    		
    		if (linklist_size == 0)return ;
    		
    		if (linklist_size == 1) 
    		{
    			head_node = null;
    			tail_node = null;
    		}
    		else {
    		
    			if (one == head_node) {
    				
    				StrNode post_one = one.post_node;
    				post_one.pre_node = null;
    				head_node = post_one;
    				
    			}	
    			else if (one == tail_node) {
    				
    				StrNode pre_node = one.pre_node;
    				pre_node.post_node = null;
    				tail_node = pre_node;
    				
    			}
    			else {
    				one.post_node.pre_node = one.pre_node;
    				one.pre_node.post_node = one.post_node;
    			}
    		}	
    		
    		linklist_size--;
    		return;
    	}
    
    	/** Returns one of the keys with maximal value. */
    	public String getMaxKey() {
    		
    		if (head_node == null)
    			return "";
    
    		return head_node.string;
    
    	}
    
    	/** Returns one of the keys with Minimal value. */
    	public String getMinKey() {
    
    		if (tail_node == null) 
    			return "";
    		
    		return tail_node.string;
    
    	}
    
    	
    }
    
    /**
     * Your AllOne object will be instantiated and called as such: AllOne obj = new
     * AllOne(); obj.inc(key); obj.dec(key); String param_3 = obj.getMaxKey();
     * String param_4 = obj.getMinKey();
     */
    

    and my local test main function
    //test_main.java

    
    public class test_main {
    
    	public static void main(String[] args) {
    
    		/*
    		
    		12/15 test cases passed.
    		Input:
    		["AllOne","inc","inc","inc","dec","inc","inc","getMaxKey","dec","dec","dec","getMaxKey"]
    		[[],["hello"],["world"],["hello"],["world"],["hello"],["leet"],[],["hello"],["hello"],["hello"],[]]
    		Output:[null,null,null,null,null,null,null,"hello",null,null,null,"hello"]
    		
    		*/
    		
    		AllOne allOne = new AllOne();
    		allOne.inc("hello");
    		allOne.inc("world");
    		allOne.inc("hello");
    		
    		allOne.dec("world");
    		
    		allOne.inc("hello");
    		allOne.inc("leet");
    		
    		System.out.println(allOne.getMaxKey());
    		
    		allOne.dec("hello");
    		allOne.dec("hello");
    		allOne.dec("hello");
    		System.out.println(allOne.getMaxKey());
    
    	}
    }
    
    

  • 0

    @muyuliuguang said in strange thing !! I get the right output however the output of leetcode is wrong,does anybody help to find out why?Thanks!:

    if (key == head_node.string)

    In Java you should do string comparison using the .equals() method, otherwise the behavior is unexpected and could be different in other environments.

    if (key.equals(head_node.string)
    

    Try this and see if it works.


  • 0
    M

    @1337c0d3r what a tiny mistake never make before...thanks man , your test cases are great! and then i WA in last cases , after modify it ,my code is accepted.thank you very much ^_^

                                    //if (one.pre_node != null && one.value > one.pre_node.value)//ori
    				while(one.pre_node != null && one.value > one.pre_node.value)
    					change_node(one.pre_node,one);
    				//else if (one.post_node != null && one.value < one.post_node.value)//ori
    				while(one.post_node != null && one.value < one.post_node.value)
    					change_node(one,one.post_node);
    
    

Log in to reply
 

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