379. Design Phone Directory #

题目 #

设计一个电话目录管理系统，令其支持以下功能：

get：分配给用户一个未被使用的电话号码，获取失败时返回 -1
check：检查指定的电话号码是否被使用
release：释放掉一个电话号码，使其能够重新被分配

思路 #

代码 #

class PhoneDirectory {
    private class ListNode {
        int val;
        ListNode prev;
        ListNode next;

        ListNode(int val, ListNode prev, ListNode next) { this.val = val; this.prev = prev; this.next = next; }
    }

    private ListNode sentinel;
    private Map<Integer, ListNode> map; /** 记录电话号码 number 是否被分配 */

    public PhoneDirectory(int maxNumbers) {
        this.sentinel = new ListNode(-1, null, null);
        this.sentinel.prev = this.sentinel.next = this.sentinel;
        for (int i=0; i<maxNumbers; i++) {
            this.sentinel.prev = new ListNode(i, this.sentinel.prev, this.sentinel);
            this.sentinel.prev.prev.next = this.sentinel.prev;
        }

        this.map = new HashMap<>();
    }
    
    public int get() {
        if (this.sentinel.next == this.sentinel) return -1;

        int result = this.sentinel.next.val;
        this.map.put(this.sentinel.next.val, this.sentinel.next);

        this.sentinel.next = this.sentinel.next.next;
        this.sentinel.next.prev = this.sentinel;

        return result;
    }
    
    public boolean check(int number) {
        return this.map.containsKey(number) == false;
    }
    
    public void release(int number) {
        if (this.map.containsKey(number) == false) return;

        ListNode ptr = this.map.get(number);

        ptr.prev = this.sentinel;
        ptr.next = this.sentinel.next;

        this.sentinel.next = ptr;
        ptr.next.prev = ptr;

        this.map.remove(number);
    }
}