Design Phone Directory

怼烎@ 2022-02-23 13:44 222阅读 0赞

## Design Phone Directory ##

题目链接：[https://leetcode.com/problems...][https_leetcode.com_problems...]

直接用一个set，结果tle了= =

public class PhoneDirectory {
    
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        Set<Integer> set = new HashSet();
        int maxNum;
        public PhoneDirectory(int maxNumbers) {
            for(int i = 0; i < maxNumbers; i++) set.add(i);
            maxNum = maxNumbers;
        }
        
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        public int get() {
            // no available numbers left
            if(set.size() == 0) return -1;
            // return 1 number
            else {
                int number = set.iterator().next();
                set.remove(number);
                return number;
            }
        }
        
        /** Check if a number is available or not. */
        public boolean check(int number) {
            return set.contains(number);
        }
        
        /** Recycle or release a number. */
        public void release(int number) {
            if(number >= 0 && number < maxNum) set.add(number);
        }
    }

看了discussion加了个queue，不过感觉没什么必要加q，反正保存的都一样，只是set.iterator().next()的时间大于O(1)，用q可以保证O(1)。看了题目条件是get可以随便返回一个值，但是test case不让这么做。很无语啊

public class PhoneDirectory {
    
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        Set<Integer> set = new HashSet();
        int maxNum;
        Queue<Integer> available = new LinkedList();
        public PhoneDirectory(int maxNumbers) {
            for(int i = 0; i < maxNumbers; i++) available.add(i);
            maxNum = maxNumbers;
        }
        
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        public int get() {
            // no available numbers left
            if(available.size() == 0) return -1;
            // return 1 number
            else {
                int number = available.poll();
                set.add(number);
                return number;
            }
        }
        
        /** Check if a number is available or not. */
        public boolean check(int number) {
            return !set.contains(number);
        }
        
        /** Recycle or release a number. */
        public void release(int number) {
            if(number >= 0 && number < maxNum) {
                if(set.remove(number)) available.add(number);
            }
        }
    }

如果这道题要求get要求的是random的，那就和380. Insert Delete GetRandom O(1)一样了。  
[https://segmentfault.com/a/11...][https_segmentfault.com_a_11...]

[https_leetcode.com_problems...]: https://leetcode.com/problems/design-phone-directory/?tab=Description
[https_segmentfault.com_a_11...]: https://segmentfault.com/a/1190000008119229