​LeetCode刷题实战379:电话目录管理系统

程序IT圈

共 3264字,需浏览 7分钟

 ·

2021-09-13 15:59

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 电话目录管理系统,我们先来看题面:
https://leetcode-cn.com/problems/design-phone-directory/

Design a Phone Directory which supports the following operations:

get: Provide a number which is not assigned to anyone.

check: Check if a number is available or not.

release: Recycle or release a number.



设计一个电话目录管理系统,让它支持以下功能:
get: 分配给用户一个未被使用的电话号码,获取失败请返回 -1
check: 检查指定的电话号码是否被使用
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);


解题

https://www.cnblogs.com/grandyang/p/5735205.html


又是一道设计题,让我们设计一个电话目录管理系统,可以分配电话号码,查询某一个号码是否已经被使用,释放一个号码。既然要分配号码,肯定需要一个数组 nums 来存所有可以分配的号码,注意要初始化成不同的数字。然后再用一个长度相等的数组 used 来标记某个位置上的号码是否已经被使用过了,用一个变量 idx 表明当前分配到的位置。

再 get 函数中,首先判断若 idx 小于0了,说明没有号码可以分配了,返回 -1。否则就取出 nums[idx],并且标记该号码已经使用了,注意 idx 还要自减1,返回之前取出的号码。

对于 check 函数,直接在 used 函数中看对应值是否为0。最后实现 release 函数,若该号码没被使用过,直接 return;否则将 idx 自增1,再将该号码赋值给 nums[idx],然后在 used 中标记为0即可,参见代码如下:


class PhoneDirectory {
public:
    PhoneDirectory(int maxNumbers) {
        nums.resize(maxNumbers);
        used.resize(maxNumbers);
        idx = maxNumbers - 1;
        iota(nums.begin(), nums.end(), 0);
    }
    int get() {
        if (idx < 0) return -1;
        int num = nums[idx--];
        used[num] = 1;
        return num;
    }
    bool check(int number) {
        return used[number] == 0;
    }
    void release(int number) {
        if (used[number] == 0) return;
        nums[++idx] = number;
        used[number] = 0;
    }

private:
    int idx;
    vector<int> nums, used;
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-360题汇总,希望对你有点帮助!

LeetCode刷题实战361:轰炸敌人

LeetCode刷题实战362:敲击计数器

LeetCode刷题实战363:矩形区域不超过 K 的最大数值和
LeetCode刷题实战364:加权嵌套序列和 II
LeetCode刷题实战365:水壶问题
LeetCode刷题实战366:寻找二叉树的叶子节点
LeetCode刷题实战367:有效的完全平方数
LeetCode刷题实战368:最大整除子集数
LeetCode刷题实战369:给单链表加一
LeetCode刷题实战370:区间加法
LeetCode刷题实战371:两整数之和
LeetCode刷题实战372:超级次方
LeetCode刷题实战373:查找和最小的K对数字
LeetCode刷题实战374:猜数字大小
LeetCode刷题实战375:猜数字大小 II
LeetCode刷题实战376:摆动序列
LeetCode刷题实战377:组合总和 Ⅳ
LeetCode刷题实战378:有序矩阵中第 K 小的元素

浏览 28
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报