what is wrong with my codes?


  • 0
    C

    Confused. Any comments welcomed.

    
    public class PhoneDirectory {
        PriorityQueue<Integer> pq = null;
        int min = 0;
        int max = 0;
    
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        public PhoneDirectory(int maxNumbers) {
            pq = new PriorityQueue();
            min = 0;
            max = maxNumbers - 1;
        }
        
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        public int get() {
            if(min<=max) { int temp = min;  min++; return temp; }
            
            if( pq.size() > 0 ) {
                int num = pq.poll();
                pq.remove( num );
                return num;
            }
            return -1;
        }
        
        /** Check if a number is available or not. */
        public boolean check(int number) {
            return (number>= min && number<= max ) || pq.contains( number );
        }
        
        /** Recycle or release a number. */
        public void release(int number) {
            if(min<=number && max>=number) return;
            pq.offer( number );
        }
    }
    
    /**
     * Your PhoneDirectory object will be instantiated and called as such:
     * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
     * int param_1 = obj.get();
     * boolean param_2 = obj.check(number);
     * obj.release(number);
     */
    

  • 0

    @Chengcheng.Pei

    Don't know why you use PriorityQueue. It costs O(logN) to operate insert and remove and O(N) to call contains.

    Here are the bugs:

        if( pq.size() > 0 ) {
                int num = pq.poll();
                pq.remove( num );
                return num;        
        }
    

    poll() will remove the number from the queue so there is not need to call remove() again.

      public void release(int number) {
            if(min<=number && max>=number) return;
            pq.offer( number );
        }
    

    If release(1) got called twice, what will happen?
    The queue will contain two 1s.
    Therefore, you code have to call check() first before offering the number to the queue.
    Or, you might want to use TreeSet instead.


  • 0
    C

    @yubad2000 Thanks. I didnot notice the test case of releasing twice.

    Why I used priorityqueue? because I misunderstood the problem and try to get minimum available number each time.
    At beginning, I used some set. That is so why I removed again.


Log in to reply
 

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