[LeetCode] 379. Design Phone Directory 设计电话目录

2021年09月15日 阅读数:4
这篇文章主要向大家介绍[LeetCode] 379. Design Phone Directory 设计电话目录,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Design a Phone Directory which supports the following operations:html

  1. get: Provide a number which is not assigned to anyone.
  2. check: Check if a number is available or not.
  3. release: Recycle or release a number.

Example:java

// Init a phone directory containing a total of 3 numbers: 0, 1, and 2.
PhoneDirectory directory = new PhoneDirectory(3);

// It can return any available phone number. Here we assume it returns 0.
directory.get();

// Assume it returns 1.
directory.get();

// The number 2 is available, so return true.
directory.check(2);

// It returns 2, the only number that is left.
directory.get();

// The number 2 is no longer available, so return false.
directory.check(2);

// Release number 2 back to the pool.
directory.release(2);

// Number 2 is available again, return true.
directory.check(2);

设计一个电话目录有3个功能,get: 给出一个没有使用的电话号码,check: 查验一个电话号码是否被使用了,release: 释放一个电话号码,使其能被重新使用。python

一、哈希表:只须要存贮一个哈希表,因此空间复杂度理论上是O(n)(实际上存储空间应该比这个大,由于涉及到散列和解决冲突)。
PhoneDirectory(int maxNumbers):时间复杂度是O(n)。
int get():时间复杂度是O(1)。
bool check(int number):时间复杂度是O(1)。
void release(int number):时间复杂度是O(1)。
二、二叉搜索树:只须要存贮一棵二叉搜索树,因此空间复杂度是O(n)。数组

PhoneDirectory(int maxNumbers):时间复杂度是O(nlogn)。
int get():时间复杂度是O(logn)。
bool check(int number):时间复杂度是O(logn)。
void release(int number):时间复杂度是O(logn)。
三、数组:存储一个表示电话号码的数组,以及一个表示某个电话号码是否可用的数组,以及一个当前可用的电话号码个数。因此空间复杂度是O(2n)。ide

PhoneDirectory(int maxNumbers):时间复杂度是O(n)。
int get():时间复杂度是O(1)。
bool check(int number):时间复杂度是O(1)。
void release(int number):时间复杂度是O(1)。
经过对比能够发现,1和3的时间复杂度都较低,可是因为3中每一个函数中同时要对两个数组进行操做,因此运行时间仍是要略慢于1。这是否是也说明C++系统中实现的散列函数仍是不错的,解决冲突并无花费太多的时间?函数

解法1: hash table, 很差post

解法2: binary tree, 很差url

解法3: 数组设计

解法4: n-ary treecode

G家:Phone number assignment

Java:

public class PhoneDirectory {
    int max;
    HashSet<Integer> set;
    LinkedList<Integer> queue;
 
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    public PhoneDirectory(int maxNumbers) {
        set = new HashSet<Integer>();
        queue = new LinkedList<Integer>();
        for(int i=0; i<maxNumbers; i++){
            queue.offer(i);
        }
        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(queue.isEmpty())
            return -1;
 
        int e = queue.poll();
        set.add(e);
        return e;
    }
 
    /** Check if a number is available or not. */
    public boolean check(int number) {
        return !set.contains(number) && number<=max;
    }
 
    /** Recycle or release a number. */
    public void release(int number) {
        if(set.contains(number)){
            set.remove(number);
            queue.offer(number);
        }
    }
}  

Python:

# init:     Time: O(n), Space: O(n)
# get:      Time: O(1), Space: O(1)
# check:    Time: O(1), Space: O(1)
# release:  Time: O(1), Space: O(1)
class PhoneDirectory(object):
    def __init__(self, maxNumbers):
        """
        Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory.
        :type maxNumbers: int
        """
        self.__curr = 0
        self.__numbers = range(maxNumbers)
        self.__used = [False] * maxNumbers

    def get(self):
        """
        Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available.
        :rtype: int
        """
        if self.__curr == len(self.__numbers):
            return -1
        number = self.__numbers[self.__curr]
        self.__curr += 1
        self.__used[number] = True
        return number


    def check(self, number):
        """
        Check if a number is available or not.
        :type number: int
        :rtype: bool
        """
        return 0 <= number < len(self.__numbers) and \
               not self.__used[number]

    def release(self, number):
        """
        Recycle or release a number.
        :type number: int
        :rtype: void
        """
        if not 0 <= number < len(self.__numbers) or \
           not self.__used[number]:
            return
        self.__used[number] = False
        self.__curr -= 1
        self.__numbers[self.__curr] = number

# Your PhoneDirectory object will be instantiated and called as such:
# obj = PhoneDirectory(maxNumbers)
# param_1 = obj.get()
# param_2 = obj.check(number)
# obj.release(number)  

C++: Hash table

class PhoneDirectory {
public:
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    PhoneDirectory(int maxNumbers) {
        for (int i = 0; i < maxNumbers; ++i) {
            hash.insert(i);
        }
    }
    
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    int get() {
        if (hash.empty()) {
            return -1;
        }
        int ret = *(hash.begin());
        hash.erase(hash.begin());
        return ret;
    }
    
    /** Check if a number is available or not. */
    bool check(int number) {
        return hash.count(number) > 0;
    }
    
    /** Recycle or release a number. */
    void release(int number) {
        hash.insert(number);
    }
private:
    unordered_set<int> hash;
};
 
/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj.get();
 * bool param_2 = obj.check(number);
 * obj.release(number);
 */

C++: binary tree

class PhoneDirectory {
public:
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    PhoneDirectory(int maxNumbers) {
        for (int i = 0; i < maxNumbers; ++i) {
            st.insert(i);
        }
    }
    
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    int get() {
        if (st.empty()) {
            return -1;
        }
        int ret = *st.begin();
        st.erase(st.begin());
        return ret;
    }
    
    /** Check if a number is available or not. */
    bool check(int number) {
        return st.find(number) != st.end();
    }
    
    /** Recycle or release a number. */
    void release(int number) {
        st.insert(number);
    }
private:
    set<int> st;
};
 
/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj.get();
 * bool param_2 = obj.check(number);
 * obj.release(number);
 */

C++: array 

class PhoneDirectory {
public:
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    PhoneDirectory(int maxNumbers) {
        n = maxNumbers;
        numbers.resize(n);
        for(int i = 0; i < n; ++i) {
            numbers[i] = i;
        }
        is_available.resize(n, true);
    }
    
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    int get() {
        if(n == 0) {
            return -1;
        }
        int num = numbers[--n];
        is_available[num] = false;
        return num;
    }
    
    /** Check if a number is available or not. */
    bool check(int number) {
        return is_available[number];
    }
    
    /** Recycle or release a number. */
    void release(int number) {
        if(is_available[number]) {  // already released
            return;
        }
        numbers[n++] = number;
        is_available[number] = true;
    }
private:
    vector<int> numbers;            // the number array
    vector<bool> is_available;      // indicate whether the number is available
    int n;                          // the current available numbers
};
 
/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj.get();
 * bool param_2 = obj.check(number);
 * obj.release(number);
 */   

C++:

class PhoneDirectory {
public:
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    PhoneDirectory(int maxNumbers) {
        max_num = maxNumbers;
        next = idx = 0;
        recycle.resize(max_num);
        flag.resize(max_num, 1);
    }
    
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    int get() {
        if (next == max_num && idx <= 0) return -1;
        if (idx > 0) {
            int t = recycle[--idx];
            flag[t] = 0;
            return t;
        }
        flag[next] = false;
        return next++;
    }
    
    /** Check if a number is available or not. */
    bool check(int number) {
        return number >= 0 && number < max_num && flag[number];
    }
    
    /** Recycle or release a number. */
    void release(int number) {
        if (number >= 0 && number < max_num && !flag[number]) {
            recycle[idx++] = number;
            flag[number] = 1;
        }
    }
private:
    int max_num, next, idx;
    vector<int> recycle, flag;
};

  

 

All LeetCode Questions List 题目汇总