379. 电话目录管理系统
设计一个电话目录管理系统，让它支持以下功能：
get: 分配给用户一个未被使用的电话号码，获取失败请返回 -1check: 检查指定的电话号码是否被使用release: 释放掉一个电话号码，使其能够重新被分配
示例：
// 初始化电话目录，包括 3 个电话号码：0，1 和 2。 PhoneDirectory directory = new PhoneDirectory(3); // 可以返回任意未分配的号码，这里我们假设它返回 0。 directory.get(); // 假设，函数返回 1。 directory.get(); // 号码 2 未分配，所以返回为 true。 directory.check(2); // 返回 2，分配后，只剩一个号码未被分配。 directory.get(); // 此时，号码 2 已经被分配，所以返回 false。 directory.check(2); // 释放号码 2，将该号码变回未分配状态。 directory.release(2); // 号码 2 现在是未分配状态，所以返回 true。 directory.check(2);
提示：
1 <= maxNumbers <= 10^40 <= number < maxNumbers[0 - 20000] 之内原站题解
golang 解法, 执行用时: 24 ms, 内存消耗: 7.2 MB, 提交时间: 2023-10-17 16:52:38
type PhoneDirectory struct {
//使用状态
uses map[int]struct{}
}
func Constructor(maxNumbers int) PhoneDirectory {
//初始化使用状态,存在即可用,时间复杂度:O(n)
uses := make(map[int]struct{}, maxNumbers)
for i := 0; i < maxNumbers; i++ {
uses[i] = struct{}{}
}
return PhoneDirectory{
uses: uses,
}
}
//获取,时间复杂度:O(1)
func (this *PhoneDirectory) Get() int {
for i := range this.uses {
//将i删除,并返回
delete(this.uses, i)
return i
}
return -1
}
//检查,时间复杂度:O(1)
func (this *PhoneDirectory) Check(number int) bool {
_, ok := this.uses[number]
return ok
}
//释放,时间复杂度:O(1)
func (this *PhoneDirectory) Release(number int) {
this.uses[number] = struct{}{}
}
/**
* Your PhoneDirectory object will be instantiated and called as such:
* obj := Constructor(maxNumbers);
* param_1 := obj.Get();
* param_2 := obj.Check(number);
* obj.Release(number);
*/
golang 解法, 执行用时: 36 ms, 内存消耗: 7 MB, 提交时间: 2023-10-17 16:51:38
type PhoneDirectory struct {
//使用状态
uses []bool
maxNumbers int
}
//初始化,使用状态默认为false:未使用
func Constructor(maxNumbers int) PhoneDirectory {
return PhoneDirectory{
uses: make([]bool, maxNumbers),
maxNumbers: maxNumbers,
}
}
//遍历,找到第一个未使用的号码.时间复杂度 :O(n)
func (this *PhoneDirectory) Get() int {
for i := 0; i < this.maxNumbers; i++ {
if !this.uses[i] {
this.uses[i] = true
return i
}
}
return -1
}
//判断是否被使用,时间复杂度:O(1)
func (this *PhoneDirectory) Check(number int) bool {
return !this.uses[number]
}
//释放,时间复杂度:O(1)
func (this *PhoneDirectory) Release(number int) {
this.uses[number] = false
}
/**
* Your PhoneDirectory object will be instantiated and called as such:
* obj := Constructor(maxNumbers);
* param_1 := obj.Get();
* param_2 := obj.Check(number);
* obj.Release(number);
*/
java 解法, 执行用时: 9 ms, 内存消耗: 46 MB, 提交时间: 2023-10-17 16:50:42
class PhoneDirectory {
boolean[] sys;
int size = 0;
/**
* Initialize your data structure here
*
* @param maxNumbers - The maximum numbers that can be stored in the phone
* directory.
*/
public PhoneDirectory(int maxNumbers) {
size = maxNumbers;
sys = new boolean[size];
Arrays.fill(sys, true);
}
/**
* Provide a number which is not assigned to anyone.
*
* @return - Return an available number. Return -1 if none is available.
*/
public int get() {
for (int i = 0; i < size; i++) {
if (sys[i]) {
sys[i] = false;
return i;
}
}
return -1;
}
/** Check if a number is available or not. */
public boolean check(int number) {
return sys[number];
}
/** Recycle or release a number. */
public void release(int number) {
sys[number] = true;
}
}
/**
* 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);
*/
python3 解法, 执行用时: 180 ms, 内存消耗: 20.1 MB, 提交时间: 2023-10-17 16:49:33
class PhoneDirectory:
def __init__(self, maxNumbers: int):
"""
Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory.
"""
self.q = [False for i in range(maxNumbers)]
def get(self) -> int:
"""
Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available.
"""
if all(self.q): return -1
for i, t in enumerate(self.q):
if not t:
self.q[i] = True
return i
def check(self, number: int) -> bool:
"""
Check if a number is available or not.
"""
return not self.q[number]
def release(self, number: int) -> None:
"""
Recycle or release a number.
"""
self.q[number] = False
# 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)
python3 解法, 执行用时: 244 ms, 内存消耗: 20.3 MB, 提交时间: 2023-10-17 16:43:52
class PhoneDirectory:
def __init__(self, maxNumbers: int):
"""
Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory.
"""
self.dic = {} # 字典解决问题, true 已分配，false 未分配
for i in range(maxNumbers):
self.dic[i] = False
def get(self) -> int:
"""
Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available.
"""
for k, v in self.dic.items():
if not v:
self.dic[k] = True
return k
return -1
def check(self, number: int) -> bool:
"""
Check if a number is available or not.
"""
return not self.dic[number]
def release(self, number: int) -> None:
"""
Recycle or release a number.
"""
self.dic[number] = False
# 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)
cpp 解法, 执行用时: 64 ms, 内存消耗: 22 MB, 提交时间: 2023-10-17 16:34:02
// 使用数组保存号码, O(n)
class PhoneDirectory {
public:
/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
PhoneDirectory(int maxNumbers) {
nums = vector<int>(maxNumbers, -1);
}
/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
int get() {
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == -1) {
nums[i] = i;
return i;
}
}
return -1;
}
/** Check if a number is available or not. */
bool check(int number) {
return nums[number] == -1;
}
/** Recycle or release a number. */
void release(int number) {
nums[number] = -1;
}
private:
vector<int> nums;
};
// 方法二：用queue+hash表，O(1) 时间
class PhoneDirectory2 {
public:
PhoneDirectory2(int maxNumbers) {
for (int i = 0; i < maxNumbers; i++) {
q.push(i);
}
used.clear();
}
/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
int get() {
if (q.empty()) {
return -1;
}
auto num = q.front();
used.insert(num);
q.pop();
return num;
}
/** Check if a number is available or not. */
bool check(int number) {
return !used.count(number);
}
/** Recycle or release a number. */
void release(int number) {
if (used.count(number)) {
used.erase(number);
q.push(number);
}
}
private:
unordered_set<int> used;
queue<int> q;
};
// 方法三：只用哈希表，不用queue，随着哈希表增大冲突越来越多，越来越慢
class PhoneDirectory3 {
public:
/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
PhoneDirectory3(int maxNumbers) {
capacity = maxNumbers;
}
/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
int get() {
int seed;
if (used.size() == capacity) {
return -1;
}
do {
seed = rand() % capacity;
} while (used.count(seed));
used.insert(seed);
return seed;
}
/** Check if a number is available or not. */
bool check(int number) {
return !used.count(number);
}
/** Recycle or release a number. */
void release(int number) {
used.erase(number);
}
private:
unordered_set<int> used;
int capacity;
};
/**
* 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);
*/
python3 解法, 执行用时: 152 ms, 内存消耗: 20.2 MB, 提交时间: 2023-10-17 16:30:50
class PhoneDirectory:
def __init__(self, maxNumbers: int):
self.pool = [i for i in range(maxNumbers)]
self.used = []
def get(self) -> int:
if len(self.pool) == 0:
return -1
num = self.pool.pop()
self.used.append(num)
return num
def check(self, number: int) -> bool:
if number in self.used:
return False
return True
def release(self, number: int) -> None:
if number in self.used:
self.pool.append(number)
self.used.remove(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)