思路分析

本题要求设计一种算法机制来抑制重复日志，满足以下两个条件：

1. 相同日志的抑制：如果在 10 毫秒内出现相同的日志，则只保留第一个。
2. 相似日志的抑制：如果在 100 毫秒内出现 10 条相似的日志（去除数字后字符相同），则只保留前 9 条。

可以使用两种方法：

1. 暴力双重循环：

   • 遍历每个日志时，从前面已读取的有效日志中检查：
     • 10 毫秒内的相同日志数量。
     • 100 毫秒内的相似日志数量。
   • 若满足抑制条件，则将日志标记为抑制日志。
   • 时间复杂度为 O(n^2)，在最大数据量下可能存在性能问题。

2. 滑动窗口 + 哈希表：

   • 采用两个滑动窗口分别记录 10 毫秒和 100 毫秒内的日志信息。
   • 使用两个哈希表分别记录 10 毫秒内相同日志的次数，以及 100 毫秒内相似日志的次数。
   • 每次读入日志时，更新滑动窗口并维护哈希表。
   • 根据哈希表的记录判断日志是否需要抑制。
   • 时间复杂度为 O(n)，更适合处理大规模数据。

算法流程

步骤1：读取输入的日志数据。

• 遍历每一条日志，解析出时间戳和日志内容。
• 使用辅助函数 remove_digits 去除日志中的数字，以判断相似日志。

步骤2：维护滑动窗口和哈希表。

• 使用两个滑动窗口：
  • 一个窗口记录 10 毫秒内的日志数量，以判断相同日志数量。
  • 一个窗口记录 100 毫秒内的日志数量，以判断相似日志数量。
• 每次读取日志时，根据时间差更新滑动窗口，移除不在窗口范围内的日志，并更新哈希表。

步骤3：判断抑制条件。

• 若当前日志在 10 毫秒内有相同日志，或 100 毫秒内有 9 条相似日志，则标记为抑制日志。
• 否则，更新哈希表，将日志加入有效日志集合。

时间复杂度

该方法时间复杂度为 O(n)，其中 n 是日志条数，因为每个日志的判断和窗口更新操作都是常数级别。适合处理大规模数据。

代码实现

Python代码（暴力双重循环）

from collections import defaultdict

# 去除字符串中的数字，判断相似性
def remove_digits(s):
    return ''.join([c for c in s if not c.isdigit()])

n = int(input())
logs = []
suppress_logs = []

# 读取每条日志
for _ in range(n):
    s = input()
    time, content = s.split(':')
    time = int(time)
    content_no_digits = remove_digits(content)
    
    same_count = 0
    similar_count = 0
    
    # 检查是否存在10ms内相同日志，100ms内相似日志
    for log_time, log_content, log_content_no_digits in logs:
        if time - log_time < 10 and log_content == content:
            same_count += 1
        if time - log_time < 100 and log_content_no_digits == content_no_digits:
            similar_count += 1

    # 若满足抑制条件，添加至抑制日志列表
    if same_count == 0 and similar_count < 9:
        logs.append((time, content, content_no_digits))
    else:
        suppress_logs.append(s)

# 输出抑制日志
if suppress_logs:
    print("\n".join(suppress_logs))
else:
    print("None")

Java & C++ 代码

限于篇幅问题，这里只给出提交记录链接

C++ - 双重暴力解法

Java - 双重暴力解法

Python代码（滑动窗口 + 哈希表优化）

from collections import defaultdict

# 从字符串中去除数字，用于判断相似性
def remove_digits(s):
    return ''.join([c for c in s if not c.isdigit()])

n = int(input())
logs = []
suppress_logs = []

# 哈希表记录10ms和100ms内日志出现次数
mp_10 = defaultdict(int)
mp_100 = defaultdict(int)

# 滑动窗口的起点
start_10 = 0
start_100 = 0

# 读取每条日志
for _ in range(n):
    raw = input()
    time, content = raw.split(':')
    time = int(time)
    content_no_digits = remove_digits(content)
    
    # 移除10ms和100ms窗口之外的日志
    while start_10 < len(logs) and time - logs[start_10][0] >= 10:
        mp_10[logs[start_10][1]] -= 1
        start_10 += 1
    while start_100 < len(logs) and time - logs[start_100][0] >= 100:
        mp_100[logs[start_100][2]] -= 1
        start_100 += 1

    # 判断是否抑制
    if mp_10[content] >= 1 or mp_100[content_no_digits] >= 9:
        suppress_logs.append(raw)
        continue

    # 更新哈希表及窗口日志
    mp_10[content] += 1
    mp_100[content_no_digits] += 1
    logs.append((time, content, content_no_digits))

# 输出抑制日志
print("\n".join(suppress_logs))

代码注释说明

1. remove_digits 函数：该函数用于去除字符串中的数字，以便判断相似日志。只保留字母和符号的顺序。
2. 暴力双重循环：遍历每一条日志时，向前检查是否满足抑制条件。
3. 滑动窗口+哈希表：mp_10 和 mp_100 分别记录 10ms 和 100ms 窗口内的相同和相似日志次数。每次更新窗口时移除超出时间范围的日志记录。
4. 输出结果：最终输出被判定为抑制的日志。

题目描述

小明的朋友是一位从事运维工作的专业人士。有一天，他突然有急事需要请假，但是他非常担心公司的系统运行日志出现海量日志的问题。这种问题是指系统打印了大量相同或相似内容的日志，导致有效信息难以被捕捉，甚至会影响系统的运行效率。为了避免这种情况发生，小明的朋友请求小明帮助管理系统的运行日志，并确保只记录有用的信息，避免无效日志的产生。对于运维而言，系统的运行日志是非常重要的，因为它包含了系统运行时的各种细节和提示信息，能够帮助运维人员诊断和解决各种问题。

小明针对海量日志的问题，提出了一种智能算法机制。避免在系统运行时产生大量日志。在这个问题中，我们将"海量日志"定义如下：在$10$毫秒内（小于$10$毫秒），如果打印了$2$条相同的日志，只保留第一条；在 $100$ 毫秒内（小于 $100$毫秒），如果打印了$10$条相似的日志，只保留前9条。按时间读取日志，若被读取的日志被判定为抑制日志，则其将不会记录到日志文件中,即删去这一项。

字符串$s,t$相似的定义:去除掉两者中所有数字后(相对顺序不发生改变)逐字符相等。则$s,t$相似

为了简化题意，使得他变成一道可以做的算法题，小明给出了以下条件，确保你能写好你的代码~

1. 给定的输入保证后一条日志的时间戳不小于前一条。时间戳的取值范围是$[1,10000]$
2. 日志内容长度在$1000$以内
3. 所有数字均为正整数。

输入描述

本用例中的日志条数（最多不超过$1000$条）和时间戳：日志打印内容

输出描述

按时间戳输出被抑制的日志。

样例1

输入

5
100:1cbbb
100:2c3a2
102:2c3a2
102:2232c
103:2232c

输出

102:2c3a2
103:2232c