A linkedlist-based solution in JAVA


  • 1
    F

    This code is based on a linked list and a boolean array. But I never ran it, because the problem is locked for me. So, can anyone help me out here?

    public class PhoneDirectory {
    	
    	LinkedList<Integer> availableNums;
    	boolean[] isUsed;
    	int mMaxNumbers;
    	
    	/** Initialize your data structure here
    	    @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    	public PhoneDirectory(int maxNumbers) {
    		availableNums = new LinkedList<>();
    		mMaxNumbers = maxNumbers;
    		isUsed = new boolean[ maxNumbers ];
    		
    		for(int num = maxNumbers-1; num >= 0; num--) {
    			availableNums.addFirst(num);
    		}
    	}
    	
    	/** Provide a number which is not assigned to anyone.
    	    @return - Return an available number. Return -1 if none is available. */
    	public int get() {
    		if(availableNums.size() == 0) {
    			return -1;
    		} else {
    			int num = availableNums.remove(0);
    			isUsed[ num ] = true;
    			
    			return num;
    		}
    	}
    	
    	/** Check if a number is available or not. */
    	public boolean check(int number) {
    		if(number>=0 && number<mMaxNumbers) {
    			return !isUsed[ number ];
    		} else {
    			return false;
    		}
    	}
    	
    	/** Recycle or release a number. */
    	public void release(int number) {
    		if(number>=0 && number<mMaxNumbers && isUsed[ number ]) {
    			isUsed[ number ] = false;
    			availableNums.addFirst(number);
    		}
    	}
    }
    

  • 0

    @Fanchao
    Good solution AC 391 ms.
    However, cost O(n) at the construction.
    Can do better, O(1), at construction.
    Here is my code.


  • 0
    F

    Thank you so much!


  • 0
    F

    @yubad2000 Thank you so much!


Log in to reply
 

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