ipv4地址白名单

正文索引 [隐藏]

题目描述:

我们的小齐同学是一名很辛苦的实习DBA,他每天的工作就是为一个帐号添加授权,今天给这200个ipv4添加授权,明天又要把这200个授权删掉,有一天小齐同学在删除授权的时候不小心把所有的授权都删了,被领导很批了一顿。痛定思痛,小齐同学开始反思他每天的工作,发现无非就是我每天要让那些ip访问数据库而已,他决定写一个效率很高的ip白名单,请帮小齐同学说一下实现思路,并用结构化编程语言(c/c++/python/golang/java等)写一个ip白名单吧,他需要这个白名单有添加ip的功能,删除ip的功能,查找这个ip在不在白名单中,以及打印白名单中的内容,以上四个功能中查找ip是否在白名单中效率一定要高。并帮小齐分析一下各个功能的时间复杂度,写的好小齐同学会请你吃饭哦。

输入描述:

每行一条输入,格式为 type:ip

type 包括 i d s 分别表示添加,删除,查找

以 end 结尾 输入最多不超过100000行

输出描述:

输出每行一条对应输入

如果是查找,成功请打印true,失败请打印false

如果是添加删除,请打印ok

输入描述1:

i:127.0.0.1
i:10.0.0.1
s:10.0.0.1
d:10.0.0.1
s:10.0.0.1
s:127.0.0.1
end

输出描述1:

ok
ok
true
ok
false
true

输入描述2:

i:127.0.0.3
i:127.0.0.3
d:127.0.0.4
s:127.0.0.3
i:127.0.0.5
d:127.0.0.5
s:127.0.0.4
i:127.0.0.4
s:127.0.0.3
d:127.0.0.4
end

输出描述2:

ok
ok
ok
true
ok
ok
false
ok
true
ok

解题思路:

牛客网给的标签是小米校招题。我感觉这题有bug吧,我是用set来模拟ip白名单的,当set中没有那个需要删除的ip时它居然还要你输出ok?!

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)

int main()
{
    ios::sync_with_stdio(false);
    set<string> s;   //用来存ip白名单
    string str;
    while(getline(cin,str) && str!="end")
    {
        char type = str[0];    //添加i、删除d、查找s
        string ip = str.substr(2,str.length()-2);
        //cout << ip << endl;
        if(type=='i')    
        {
            s.insert(ip);   
            printf("ok\n");
        }
        if(type=='s')   //查找
        {
            printf("%s\n",s.count(ip)!=0?"true":"false");
        }
        if(type=='d')   //删除
        {
            if(s.count(ip)!=0)   //这题有bug吧 set中没有这个ip还要你输出ok?!
            {
                s.erase(s.find(ip));   //不加if条件可鞥会产生段错误,因为它输入的ip可能不存在set中
            }
            printf("ok\n");
        }
    }
    return 0;
}