首页 > 试题广场 >

ipv4地址白名单

[编程题]ipv4地址白名单
  • 热度指数:2867 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
我们的小齐同学是一名很辛苦的实习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
您的代码已保存 答案错误:您提交的程序没有通过所有的测试用例 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)
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)
用set模拟数据库的操作即可
line = input().strip()
db = set()
while line != "end":
    op, ip = line.split(":")
    if op == "i":
        db.add(ip)
        print("ok")
    elif op == "d":
        db.discard(ip)
        print("ok")
    else:
        if ip in db:
            print("true")
        else:
            print("false")
    line = input().strip()


发表于 2021-02-27 15:58:19 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	set<string> S;
	while((cin>>s) && (s!="end"))
	{
		if(s[0]=='i')
		{
			s=s.substr(2);
			S.insert(s);
			printf("ok\n");
		}
		else if(s[0]=='s')
		{
			s=s.substr(2);
			if(S.find(s)!=S.end())
			{
				printf("true\n");
			}
			else printf("false\n");
		}
		else	//d
		{
			s=s.substr(2);
			S.erase(s);
			printf("ok\n");
		}
	}
	return 0;
}

发表于 2020-09-04 15:59:38 回复(0)
我发现用algorithm的find算法比容器自带的find要慢一点,我用algorithm的find通过了66.7%,其他超时。用set自带的find就过了。
#include <iostream>
#include <string>
#include <set>
using namespace std;

int main(){
    string str;
    set<string> st;
    while(cin >> str){
        if(str == "end"){
            return 0;
        }
        //做判断
        char c = str[0];
        string temp = str.substr(2);
        if(c == 'i'){
            cout << "ok" << endl;
            st.insert(temp);
        } else if(c == 'd'){
            cout << "ok" << endl;
            set<string>::iterator it = st.find(temp);
            if(it != st.end()){
                st.erase(it);
            }
        } else{
            if(st.find(temp) != st.end()){
                cout << "true" << endl;
            } else{
                cout << "false" << endl;
            }
        }
    }
    return 0;
}


编辑于 2020-06-26 21:04:49 回复(0)
为什么就超时了,哪里死循环了吗
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)
""""
借用字典特性
添加、删除、查找,时间复杂度都为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)
#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)
package main

import (
    "fmt"
    "os"
    "bufio"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var s string
    cnt:=map[string]bool{}
    for{
        fmt.Fscan(in,&s)
        if s=="end"{
            break
        }
        t,ip:=s[0],s[2:]
        if t=='i'{
            cnt[ip]=true
            fmt.Println("ok")
        }else if t=='d'{
            delete(cnt,ip)
            fmt.Println("ok")
        }else{
            _,ok:=cnt[ip]
            fmt.Println(ok)
        }
    }
}

发表于 2023-03-22 19:51:29 回复(0)

思路:使用unorder_map来实现高效的查找。

#include<cstring>
#include<iostream>
#include<unordered_map>
using namespace std;
class Solution {
public:
    void insert(string str) {
        datasets[str] = 1;
        cout << "ok" << endl;
    }
    void search(string str ) {
        if (datasets[str] == 1) {
            cout << "true" << endl;
        }
        else
        {
            cout << "false" << endl;
        }
    }
    void deletesol(string str) {
        datasets[str] = 0;
        cout << "ok" << endl;
    }
    void dealWith(string temp) {
        startWith = temp.find(':');
        selectWay = temp[startWith-1];
        res = temp.substr(startWith + 1);
        if (selectWay == 'i') {
            insert(res);
        }
        else if (selectWay == 'd') {
            deletesol(res);
        }
        else
        {
            search(res);
        }
    }
private:
    char selectWay;
    int startWith;
    string res;
    unordered_map<string,int> datasets;
};
int main() {
    string in;
    Solution sol;
    while (cin >> in) {
        if (in == "end") {
            break;
        }
        sol.dealWith(in);

    }

}
发表于 2020-05-20 22:12:44 回复(0)
用Map效率好像比Set高。
import java.util.HashMap;
import java.util.Scanner;

/**
 * @Date: 2020-05-04 22:54
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        HashMap<String,Boolean> al = new HashMap<>();
        while (true){
            String s = sc.next();
            if ("end".equals(s))
                break;
            char op = s.charAt(0);
            String ip = s.substring(2, s.length());
            if (op == 'i'){
                al.put(ip,true);
                System.out.println("ok");
            }else if (op == 'd'){
                al.put(ip,false);
                System.out.println("ok");
            }else
            {
                if (al.get(ip)==null || al.get(ip)==false)
                    System.out.println(false);
                else 
                    System.out.println(true);
            }
        }
    }
}


发表于 2020-05-04 23:29:03 回复(0)
注意要是set,不能用list
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {

        Set<String> values = new HashSet<>();
        String ip;
        String op;
        String str;
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            str = cin.next();
            if (str.equals("end")) {
                return;
            }

            op = str.substring(0, 1);
            ip = str.substring(2);
            if (op.equals("i")) {
                values.add(ip);
                System.out.println("ok");
            }
            if (op.equals("s")) {
                if (values.contains(ip)) {
                    System.out.println("true");
                } else {
                    System.out.println("false");
                }
            }
            if (op.equals("d")) {
                    values.remove(ip);
                    System.out.println("ok");
            }
        }

    }
}


发表于 2019-10-05 02:01:17 回复(0)
#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));
            }
            printf("ok\n");
        }
    }
    return 0;
}

发表于 2019-10-04 17:10:04 回复(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)