Design Phone Directory-蒲公英云

Design Phone Directory

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

Design Phone Directory

题目链接：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);
        }
    }
}