刷题笔记合集🔗

问题描述

随着移动通信的普及，垃圾短信也越来越多，给人们的生活带来了很多烦恼。为了识别垃圾短信发送者，我们需要分析短信发送和接收的模式。

在这个问题中，我们将使用以下规则来识别垃圾短信发送者：

1. 如果一个用户A发送短信给超过5个没有回复过A的用户，则A可能是垃圾短信发送者。
2. 如果一个用户A发送的短信总数比收到的短信总数多10条以上，则A可能是垃圾短信发送者。
3. 如果存在用户X，用户A发送给X的短信比X发送给A的短信多5条以上，则A可能是垃圾短信发送者。

如果满足以上任一条件，则认为该用户是垃圾短信发送者。

输入格式

第一行包含一个整数 ，表示短信记录的数量。

接下来的 行，每行包含两个整数 和 ，分别表示发送者ID和接收者ID。

最后一行包含一个整数 ，表示要检查的用户ID。

输出格式

输出一行，包含三个值，用空格分隔：

• 第一个值是 "true" 或 "false"，表示用户 是否是垃圾短信发送者。
• 第二个值是一个整数 ，表示用户 发送短信给的没有回复过 的用户数量。
• 第三个值是一个整数 ，表示用户 发送的短信总数减去收到的短信总数。

样例输入1

12
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 1
3 10
4 10
5 10
6 10
1

样例输出1

true 6 7

样例输入2

15
2 1
2 1
2 1
2 1
2 1
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1

样例输出2

false 0 5

样例输入3

10
1 2
1 2
1 2
1 2
1 2
1 2
1 2
2 1
3 4
5 6
1

样例输出3

true 0 6

数据范围

题解

这道题目要求我们识别垃圾短信发送者，需要根据三个条件来判断：

1. 发送短信给超过5个没有回复过的用户
2. 发送的短信总数比收到的短信总数多10条以上
3. 存在用户X，发送给X的短信比X发送给自己的短信多5条以上

解题思路：

1. 统计用户发送和接收的短信记录
2. 计算没有回复过的用户数量l
3. 计算发送短信总数与接收短信总数的差值m
4. 检查是否存在满足条件3的用户X
5. 根据三个条件判断是否是垃圾短信发送者

时间复杂度分析：

• 统计短信记录需要 的时间
• 计算l和m需要 的时间，其中k是与用户tid有交互的用户数量
• 检查条件3需要 的时间
• 因此，总的时间复杂度是

空间复杂度分析：

• 存储短信记录需要 的空间
• 因此，总的空间复杂度是

对于给定的数据范围，这个算法是高效的，可以在合理的时间内得到结果。

参考代码

# 输入获取
n = int(input())
msg_list = [input().split() for i in range(n)]
user_id = input()

# 算法入口
def check_spam(uid, msgs):
    # 记录发送和接收的消息
    out_msgs = []
    in_msgs = []
    
    # 记录发送和接收的次数
    out_cnt = {}
    in_cnt = {}
    
    # 处理所有消息记录
    for s_id, r_id in msgs:
        # 处理发送的消息
        if s_id == uid:
            out_msgs.append(r_id)
            if r_id in out_cnt:
                out_cnt[r_id] += 1
            else:
                out_cnt[r_id] = 1
        
        # 处理接收的消息
        if r_id == uid:
            in_msgs.append(s_id)
            if s_id in in_cnt:
                in_cnt[s_id] += 1
            else:
                in_cnt[s_id] = 1
    
    # 计算发送和接收的用户集合
    out_set = set(out_msgs)
    in_set = set(in_msgs)
    
    # 计算有交互的用户
    chat_list = [x for x in out_set if x in in_set]
    
    # 计算关键指标
    no_reply = len(out_set) - len(chat_list)
    msg_diff = len(out_msgs) - len(in_msgs)
    
    # 判断是否为垃圾短信发送者
    is_spam = no_reply > 5 or msg_diff > 10
    
    # 如果前两个条件不满足，检查第三个条件
    if not is_spam:
        for uid2 in out_set:
            sent = out_cnt[uid2]
            recv = in_cnt.get(uid2, 0)
            if sent - recv > 5:
                is_spam = True
                break
    
    # 返回结果
    return f"{str(is_spam).lower()} {no_reply} {msg_diff}"

# 算法调用
print(check_spam(user_id, msg_list))

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;

/**