首页 > 试题广场 > ipv4地址白名单
[编程题]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

输出

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

输出

ok
ok
ok
true
ok
ok
false
ok
true
ok
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        HashSet<String> set = new HashSet<>();
        while (!scanner.hasNext("end")) {
            String command = scanner.next();
            char c = command.charAt(0);
            String ip = command.substring(2);
            switch (c) {
                case 'i':
                    set.add(ip);
                    System.out.println("ok");
                    break;
                case 'd':
                    set.remove(ip);
                    System.out.println("ok");
                    break;
                case 's':
                    System.out.println(set.contains(ip));
                    break;
            }
        }
    }
}
发表于 2019-07-15 10:11:30 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    map<string,bool> M;
    while(cin>>s){
        if(s=="end")
            break;
        string ip = s.substr(2);
        char op = s[0];
        if(op=='i'){
            M[ip] = true;
            cout<<"ok"<<endl;
        }else if(op=='d'){
            M[ip] = false;
            cout<<"ok"<<endl;
        }else if(op=='s'){
            if(M.find(ip)==M.end() || M[ip]==false)
                cout<<"false"<<endl;
            else if(M[ip])
                cout<<"true"<<endl;
        }        
    }
    return 0;
}

发表于 2019-07-14 22:54:19 回复(0)
""""
借用字典特性
添加、删除、查找,时间复杂度都为O(1)
打印O(n)
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    dic = {}
    for line in sys.stdin:
        s = line.strip()
        if s == 'end': break
        if s[0] == 'i':
            dic[s[2:]] = True
            print("ok")
        elif s[0] == 'd':
            if s[2:] in dic:
                del dic[s[2:]]
            print("ok")
        elif s[0] == 's':
            if s[2:] in dic:
                print("true")
            else:
                print("false")

发表于 2019-07-14 09:42:22 回复(0)
您的代码已保存 答案错误:您提交的程序没有通过所有的测试用例 case通过率为46.67% 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<string>res;
    vector<int>f;
    string s;
    while(cin>>s)
    {
        if(s[0]=='i')
        {
            res.push_back(s.substr(2,s.size()-2));
            f.push_back(0);
            cout<<"ok"<<endl;
        }
        else if(s[0]=='s')
        {
            int flag=0;
            for(long long i=0;i<res.size();i++)
            {
                if(res[i]==s.substr(2,s.size()-2)&&f[i]==0)
                {
                    cout<<"true"<<endl;
                    flag=1;
                    break;
                }
            }
            if(!flag)
                cout<<"false"<<endl;
        }
        else if(s[0]=='d')
        {
            for(long long i=0;i<res.size();i++)
            {
                if(res[i]==s.substr(2,s.size()-2)&&f[i]==0)
                {
                    f[i]=1;
                    break;
                }
            }
            cout<<"ok"<<endl;
        }
        else
            break;
    }
    return 0;
}
不知道为啥会这样,劳烦大神们批评指导一波,感激不尽!!
在大佬的指导下,通过了
#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<string>res;
    vector<int>f;
    string s;
    map<string,int>mp;
    while(cin>>s)
    {
        if(s[0]=='i')
        {
            string str=s.substr(2,s.size()-2);
            res.push_back(str);
            mp[str]=1;
            cout<<"ok"<<endl;
        }
        else if(s[0]=='s')
        {
            string str=s.substr(2,s.size()-2);
            if(mp[str]==1)
                cout<<"true"<<endl;
            else
                cout<<"false"<<endl;        
        }
        else if(s[0]=='d')
        {
            string str=s.substr(2,s.size()-2);
            if(mp[str]==1)
                mp[str]=0;
            cout<<"ok"<<endl;
        }
        else
            break;
    }
    return 0;
}



编辑于 2019-07-05 08:47:58 回复(2)
为什么就超时了,哪里死循环了吗
res=[]
while 1:
    i=input()
    if i=='end':
        break
    if i[0]=='i':
        if i[1:] not in res:
            res.append(i[1:])
        print('ok')
    if i[0]=='d':
        if i[1:] in res:
            res.remove(i[1:])
        print('ok')
    if i[0]=='s':
        if i[1:] in res:
            print('true')
        else:
            print('false')

发表于 2019-08-20 14:49:38 回复(0)
通过测试用例53,3%,不知道为啥,功能实现感觉都没问题
#include <stdio.h>
#include <string.h>
#define size_num 100000
#define str_length 20
int max(int a,int b){
    return a>b?a:b;    
}
int main() {
	int i = 0;
	int j = 0;
	int a = 0;
	int str_count = 0;
	int str_dcount = 0;
	int i_count = 0;
	int s_count = 0;
	int d_count = 0;
	int i_temp;
	char str_in[str_length];
	char str_temp[str_length];
	char print_str[size_num] = { 0 };
    int length_str[size_num] = {0};
	char store_str[size_num][str_length] = { 0 };
	int length = 0;

	for (i = 0; i < size_num; i++) {
		gets(str_in);
		length = strlen(str_in);
        length_str[i] = length -2;
		i_temp = i;

		for (j = 2; j < length; j++) {
			str_temp[j - 2] = str_in[j];
		}
/*		for (j = 0; j < length-2; j++) {
			printf("%c", str_temp[j]);
		}
		printf("\n");*/

		if (str_in[0] == 'i') {
			print_str[i] = '3';
			for (i_count = 0; i_count < length-2; i_count++) {
				store_str[i][i_count] = str_temp[i_count];
			}
//			printf("%c\n", print_str[i]);
/*			for (j = 0; j < length - 2; j++) {
				printf("%c", store_str[i][j]);
			}
			printf("\n");*/
		}
		else if (str_in[0] == 'd') {
			print_str[i] = '3';
			for (d_count = 0; d_count < i; d_count++) {
				str_dcount = 0;
				for (j = 0; j <max( length - 2,length_str[d_count]); j++) {
					if (str_temp[j] == store_str[d_count][j]) {
						str_dcount += 1;
					}
				}
				if (str_dcount == length - 2) {
					for (j = 0; j < length - 2; j++) {
						store_str[d_count][j] = '0';
					}
				}
				
			}
		/*	for (j = 0; j < length - 2; j++) {
				store_str[i][j] = '0';
			}*/
		/*	for (j = 0; j < length - 2; j++) {
				printf("%c", store_str[i][j]);
			}
			printf("\n");
			printf("%c\n", print_str[i]);*/
		}
		else if (str_in[0] == 's') {
			for (s_count = 0; s_count < i; s_count++) {
				str_count = 0;
				for (j = 0; j < max(length - 2,length_str[s_count]); j++) {
					if (str_temp[j] == store_str[s_count][j]) {
						str_count += 1;
					}
					else
						break;
				}
				if (str_count == length - 2) {
					print_str[i] = '1';
					break;
				}
				else
					print_str[i] = '2';

			}
	//		printf("%d\n", length - 2);
	//		printf("%d\n", str_count);
	//		printf("%c\n", print_str[i]);
//			str_count = 0;

		}
		else  if(str_in[0]=='e')
			break;
		
	}
	/*for (i = 0; i < 10; i++) {
		for (j = 0; j < 15; j++) {
			printf("%c", store_str[i][j]);
		}
		printf("\n");
	}*/
//	printf("%s\n", print_str[0]);
	//printf("%s\n", store_str[0][0]);
	for (i = 0; i <i_temp; i++) {
		if (print_str[i] == '3')
			printf("ok\n");
		else if (print_str[i] == '1') {
			printf("true\n");
		}
		else if (print_str[i] == '2') {
			printf("false\n");
		}
	}

}


发表于 2019-08-17 10:53:26 回复(1)
此题最大的坑就在于重复添加授权,计数还是1,不会累加的。用哈希表的同学注意了。

发表于 2019-07-28 09:41:26 回复(0)
import sys
ip = set()

for ss in sys.stdin:
    if ss.strip() == "end":
        break
    typ, addr = ss.split(":")
    if typ == "i":
        if addr not in ip:
            ip.add(addr)
        print("ok")
    elif typ == "s":
        if addr not in ip:
            print("false")
        else:
            print("true")
    else:
        if addr in ip:
            ip.remove(addr)
        print("ok")

发表于 2019-07-26 13:12:16 回复(0)
#include <iostream>
#include <set>
#include <string>
using namespace std;
int main()
{ 
    string ip;
    set<string>ipnum;//用一个set存储ip地址,并实现插入,查找,删除
    while (cin >> ip) {
        if (ip == "end") break;
        if (ip[0] == 'i') {
            ipnum.insert(ip.substr(2));
            cout << "ok" << endl;
        }
        else if (ip[0] == 's') {
            if (ipnum.find(ip.substr(2)) != ipnum.end()) {
                cout << "true" << endl;
            }
            else {
                cout << "false"<<endl;
            }
        }
        else {
            ipnum.erase(ip.substr(2));
            cout << "ok"<<endl;
        }
    }
    return 0;
}

发表于 2019-07-24 21:51:44 回复(0)