一道C++的题，百度在线扫题等

来源：蜘蛛抓取(WebSpider) 时间：2020-10-05 02:30 标签： 百度在线扫题

百度今年一道笔试题——ip攻击

这昰今年百度的一道笔试题给你1亿个ip地址和每个ip访问的时间(00:00:00=<时间<=23:59:59，并且已经按照时间排好序了)然后给定一段时间X，定义在X内如果某IP的访問次数超过Y次则判定该IP为攻击IP。要求输出所有攻击IP只有一组测试用例。第一行输入IP记录数(即10万)时间X(10=<X<=120秒)，次数Y(2=<Y<=100)输出按访问的时间顺序输出，IP重复不再输出

输入示例：(为了方便，只给出8个意思意思)

这样的话 算法 应该比 O（n)差不了多少。

1: 定义一个已经重复的IP多叉树寻找IP更快

2. 定义两个数组(A, B), 大小为X, 分别存在两个时间段X内的攻击IP.

按时间存储到相应数组, 如果相邻次(i-1, i)时间相同且IP也相同, 重复次数+1 

3. 求出两个数组之内時间内重复IP,

4. 求出两组之间有重复的IP, 通过bgtime，及数组对应比较

2.只要判断A.下标数组 往后X 数组内是否有重复就可以了

5. 输出A、B重复的IP输出的需要根據IP多叉树查找已经输出过IP，避免重复输出, 同时把输出的IP加入IP多叉树 

同时把B数组没有重复的IP移入A数组, 再继续读取填入A, B数组

7. 这样可以减少存储涳间如果是1亿级的IP，用哈稀估计内存不能接受

t2为00：00：01-00：00：05依次类推时间段可以分为86400-x个时间段，可以另外建立一个hash表记录在某个时间段的摸个ip的访问次数，结构如下：

主键为ip地址{ip地址，时间段标识时间标识， 访问次数} 说明： 时间段标识表示访问时间在那一个时间段中， 时间标识表示访问的时间点

驿站新手, 积分 51, 距离下一级还需 99 积汾

小生不才,刚学习,用的笨办法.
把代码贴出,多给指教.

我要回帖

更多关于 百度在线扫题 的文章

 

随机推荐