【华为OD-E卷 - 垃圾信息拦截 100分（python、java、c++、js、c）】
题目
大众对垃圾短信深恶痛绝，希望能对垃圾短信发送者进行识别，为此，很多软件增加了垃圾短信的识别机制。 经分析，发现正常用户的短信通常具备交互性，而垃圾短信往往都是大量单向的短信，按照如下规则进行垃圾短信识别：
本题中，发送者A符合以下条件之一的，则认为A是垃圾短信发送者：
A发送短信的接收者中，没有发过短信给A的人数L > 5； A发送的短信数 – A接收的短信数M > 10； 如果存在X，A发送给X的短信数 – A接收到X的短信数N > 5；
输入描述
- 第一行是条目数，接下来几行是具体的条目，每个条目，是一对ID，第一个数字是发送者ID，后面的数字是接收者ID，中间空格隔开，所有的ID都为无符号整型，ID最大值为100；
同一个条目中，两个ID不会相同（即不会自己给自己发消息）
最后一行为指定的ID
输出描述
- 输出该ID是否为垃圾短信发送者，并且按序列输出 L M 的值（由于 N 值不唯一，不需要输出）； 输出均为字符串。
备注
用例
用例一：
输入：
15
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
14 1
1 15
1
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
输出：
true 13 13
- 1
用例二：
输入：
15
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
14 1
1 15
2
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
输出：
false 0 -1
- 1
python解法
- 解题思路：
- 问题描述
每条数据表示一次发送和接收关系，格式为 (s, r)，其中：
s 是发送方的 ID。
r 是接收方的 ID。
给定一个目标 ID tid，需要分析它的发送和接收行为，判断是否为垃圾发送者，并输出以下三项：
是否为垃圾发送者（true 或 false）。
tid 发送的消息中没有被响应的接收者数量。
tid 的发送和接收消息数量差。
垃圾发送者判定规则
定义垃圾发送者的条件：
tid 有超过 5 个发送目标未响应。
tid 的总发送消息数量比接收消息数量多出 10 条以上。
对于每个接收者，如果 tid 发送给该接收者的消息数量比从该接收者接收到的消息多出 5 条，则判定为垃圾发送者。
算法设计
遍历数据列表，统计 tid 的以下信息：
snd：所有发送消息的接收者集合。
rcv：所有发送消息的发送者集合。
snd_cnt：每个接收者接收到的消息数量。
rcv_cnt：每个发送者发送给 tid 的消息数量。
计算以下结果：
no_resp：未响应的接收者数量（snd - rcv 的集合大小）。
diff：发送消息数量减去接收消息数量的差值。
spam：根据上述垃圾发送者规则判断结果
def get_result(tid, arr):
# 定义集合和字典用于统计发送和接收的信息
snd = set() # 存储 `tid` 所有发送消息的接收者
rcv = set() # 存储 `tid` 所有接收消息的发送者
snd_cnt = {} # 存储每个接收者接收到的消息数量
rcv_cnt = {} # 存储每个发送者发送给 `tid` 的消息数量
# 遍历所有记录，统计发送和接收信息
for s, r in arr:
if s == tid: # 如果当前记录的发送方是 `tid`
snd.add(r) # 将接收方加入发送集合
snd_cnt[r] = snd_cnt.get(r, 0) + 1 # 统计发送给每个接收方的消息数量
if r == tid: # 如果当前记录的接收方是 `tid`
rcv.add(s) # 将发送方加入接收集合
rcv_cnt[s] = rcv_cnt.get(s, 0) + 1 # 统计每个发送方发送给 `tid` 的消息数量
# 计算未响应的接收者数量（`snd - rcv`）
no_resp = len(snd - rcv)
# 计算发送和接收的消息数量差值
diff = sum(snd_cnt.values()) - sum(rcv_cnt.values())
# 初始垃圾发送者标志为 False
spam = no_resp > 5 or diff > 10 # 根据规则 1 和规则 2 判断垃圾发送者
# 检查规则 3：是否有某个接收者与 `tid` 的消息差大于 5
for p in snd:
if snd_cnt.get(p, 0) - rcv_cnt.get(p, 0) > 5:
spam = True # 如果满足条件，判定为垃圾发送者
break
# 返回结果，格式为 `spam no_resp diff`
return f"{str(spam).lower()} {no_resp} {diff}"
# 输入处理部分
n = int(input()) # 读取记录数量
arr = [input().split() for _ in range(n)] # 读取所有记录
tid = input() # 读取目标 ID
# 调用函数输出结果
print(get_result(tid, arr))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
java解法
- 解题思路
- 问题描述
每条消息以 (sender, receiver) 的形式表示，分别为发送方和接收方的 ID。
给定一个目标用户 ID tid，需要判定该用户是否为垃圾发送者。
垃圾发送者的判定规则：
tid 发送的接收方中，有超过 5 个未回复的接收方。
tid 总发送消息数量减去总接收消息数量超过 10。
对任意接收方，如果 tid 向其发送的消息数量比从其接收的消息数量多 5 条以上，则为垃圾发送者。
算法设计
使用 集合 和 映射 数据结构统计消息的发送和接收关系：
sentTo：tid 发送消息的所有接收方。
receivedFrom：tid 接收消息的所有发送方。
sendCount：tid 对每个接收方发送的消息数量。
receiveCount：每个发送方对 tid 发送的消息数量。
根据统计数据，计算以下结果：
未回复的接收方数量 l。
总发送消息数量与接收消息数量的差值 m。
是否满足垃圾发送者判定规则。
实现细节
使用 SpamDetector 类封装判定逻辑，包括消息处理、垃圾发送者判定，以及结果计算方法。
在主函数中读取输入，调用 SpamDetector 执行判定。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取消息记录数
int n = scanner.nextInt();
// 存储消息记录的列表
List<int[]> messages = new ArrayList<>();
// 读取消息记录 (sender, receiver)
for (int i = 0; i < n; i++) {
int[] entry = new int[2];
entry[0] = scanner.nextInt(); // 发送方
entry[1] = scanner.nextInt(); // 接收方
messages.add(entry);
}
// 读取目标用户 ID
int targetId = scanner.nextInt();
// 调用方法检查垃圾发送者并输出结果
System.out.println(checkSpammer(targetId, messages));
}
/**
* 检查指定用户是否为垃圾发送者
*
* @param tid 目标用户 ID
* @param messages 消息记录列表
* @return 判定结果字符串，格式为 "true/false l m"
*/
public static String checkSpammer(int tid, List<int[]> messages) {
// 创建垃圾发送者检测器对象
SpamDetector detector = new SpamDetector(tid);
// 处理每条消息记录
for (int[] msg : messages) {
detector.processMessage(msg[0], msg[1]);
}
// 返回判定结果
return detector.isSpammer() + " " + detector.getL() + " " + detector.getM();
}
}
/**
* 垃圾发送者检测器类
*/
class SpamDetector {
private int tid; // 目标用户 ID
private Set<Integer> sentTo = new HashSet<>(); // `tid` 发送的接收方集合
private Set<Integer> receivedFrom = new HashSet<>(); // `tid` 接收的发送方集合
private Map<Integer, Integer> sendCount = new HashMap<>(); // `tid` 向每个接收方发送的消息数量
private Map<Integer, Integer> receiveCount = new HashMap<>(); // 每个发送方向 `tid` 发送的消息数量
// 构造函数初始化目标用户 ID
public SpamDetector(int tid) {
this.tid = tid;
}
/**
* 处理单条消息记录
*
* @param sender 发送方 ID
* @param receiver 接收方 ID
*/
public void processMessage(int sender, int receiver) {
if (sender == tid) { // 如果发送方是目标用户
sentTo.add(receiver); // 添加接收方到发送集合
sendCount.put(receiver, sendCount.getOrDefault(receiver, 0) + 1); // 更新发送数量
} else if (receiver == tid) { // 如果接收方是目标用户
receivedFrom.add(sender); // 添加发送方到接收集合
receiveCount.put(sender, receiveCount.getOrDefault(sender, 0) + 1); // 更新接收数量
}
}
/**
* 判定是否为垃圾发送者
*
* @return 是否为垃圾发送者
*/
public boolean isSpammer() {
// 计算未回复的接收方数量 l
int l = sentTo.size() - (int) sentTo.stream().filter(receivedFrom::contains).count();
// 计算发送与接收消息数量差值 m
int m = sendCount.values().stream().mapToInt(Integer::intValue).sum() -
receiveCount.values().stream().mapToInt(Integer::intValue).sum();
// 判断是否满足垃圾发送者规则 1 和规则 2
if (l > 5 || m > 10) {
return true;
}
// 判断是否满足垃圾发送者规则 3
for (int id : sentTo) {
if (sendCount.get(id) - receiveCount.getOrDefault(id, 0) > 5) {
return true;
}
}
return false; // 如果不满足任何规则，则不是垃圾发送者
}
/**
* 获取未回复的接收方数量 l
*
* @return 未回复的接收方数量
*/
public int getL() {
return sentTo.size() - (int) sentTo.stream().filter(receivedFrom::contains).count();
}
/**
* 获取发送与接收消息数量差值 m
*
* @return 发送与接收消息数量差值
*/
public int getM() {
return sendCount.values().stream().mapToInt(Integer::intValue).sum() -
receiveCount.values().stream().mapToInt(Integer::intValue).sum();
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
C++解法
- 解题思路
- 问题描述
给定一个消息记录的列表，记录的形式为 (sender, receiver)，表示某个发送者向某个接收者发送了一条消息。
给定一个目标用户 ID targetId，需要分析该用户是否为垃圾发送者，并输出以下三个结果：
是否为垃圾发送者（true 或 false）。
L：目标用户发送的接收者中未回复的接收者数量。
M：目标用户的总发送消息数量减去总接收消息数量的差值。
垃圾发送者判定规则
满足以下任意一条规则，即判定为垃圾发送者：
L > 5，即未回复的接收者数量超过 5。
M > 10，即发送和接收的消息数量差值超过 10。
对任意接收者，如果发送消息数量比接收到的消息数量多 5 条以上，则判定为垃圾发送者。
算法设计
遍历消息记录，统计目标用户的发送和接收情况：
使用 unordered_set 分别记录目标用户发送消息的接收者和接收消息的发送者。
使用 unordered_map 记录每个接收者收到的消息数量和每个发送者发送给目标用户的消息数量。
累计目标用户的总发送消息数量和接收消息数量。
计算 L 和 M：
L 为发送集合中未被接收集合覆盖的部分。
M 为总发送消息数量减去总接收消息数量。
判断是否满足垃圾发送者条件
#include - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
C解法
更新中
- 1
JS解法
给定若干条消息日志，每条日志记录了消息的发送者和接收者 (sender, receiver)。
需要分析一个指定的用户 targetId 的消息行为，判断其是否为垃圾短信发送者。
判断规则：
目标用户的独立接收者数量 L > 5。
目标用户发送的总消息数量减去接收到的总消息数量 M > 10。
目标用户对某个接收者发送的消息数量比从该接收者接收到的消息数量多出 5 条。
输入输出格式
输入：
第一行是消息日志的条目数 n。
接下来 n 行，每行包含一条消息日志，格式为 sender receiver。
最后一行是目标用户的 ID targetId。
输出：
格式为 “isSpammer L M”，其中：
isSpammer 是 true 或 false，表示目标用户是否为垃圾短信发送者；
L 是独立接收者数量；
M 是总发送消息数量与接收消息数量的差值。
算法设计
使用两个哈希表统计消息记录：
outgoingMessages：记录每个用户的发送消息详情，包括总发送量和独立接收者集合。
incomingMessages：记录每个用户接收消息的总数。
统计目标用户的 L 和 M 值：
L 为目标用户的独立接收者数量。
M 为目标用户的发送消息数量减去接收消息数量。
检查垃圾发送者的规则，逐条判断是否满足
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let inputs = [];
let totalRecords;
rl.on("line", (line) => {
inputs.push(line);
// 读取第一行消息记录总数
if (inputs.length === 1) {
totalRecords = parseInt(inputs[0], 10);
}
// 当输入完整时处理数据
if (inputs.length === totalRecords + 2) {
inputs.shift(); // 移除第一行记录（消息总数）
const targetId = inputs.pop(); // 获取最后一行作为目标用户 ID
const messageLogs = inputs.map((line) => line.split(" ").map(Number)); // 将日志解析为数组
// 调用函数分析目标用户的消息行为
console.log(analyzeMessages(parseInt(targetId, 10), messageLogs));
inputs = []; // 重置输入数据
}
});
/**
* 判断目标ID是否为垃圾短信发送者
* @param {number} targetId 目标的ID
* @param {Array>} messageLogs 消息日志，格式为 [[sender, receiver], ...]
* @returns {string} 返回是否为垃圾短信发送者以及L和M值
*/
function analyzeMessages(targetId, messageLogs) {
// 定义哈希表用于存储发送和接收消息的数据
const outgoingMessages = {}; // 记录用户的发送数据
const incomingMessages = {}; // 记录用户的接收数据
// 遍历消息日志，统计发送和接收数据
messageLogs.forEach(([sender, receiver]) => {
// 初始化发送数据
if (!outgoingMessages[sender]) {
outgoingMessages[sender] = { totalSent: 0, uniqueReceivers: new Set() };
}
// 初始化接收数据
if (!incomingMessages[receiver]) {
incomingMessages[receiver] = 0;
}
// 更新发送数据
outgoingMessages[sender].totalSent++;
outgoingMessages[sender].uniqueReceivers.add(receiver);
// 更新接收数据
incomingMessages[receiver]++;
});
// 获取目标用户的统计信息
const totalSent = outgoingMessages[targetId]?.totalSent || 0; // 目标用户的总发送消息数量
const totalReceived = incomingMessages[targetId] || 0; // 目标用户的总接收消息数量
const uniqueReceivers = outgoingMessages[targetId]?.uniqueReceivers.size || 0; // 目标用户的独立接收者数量
// 计算 L 和 M
const L = uniqueReceivers; // 独立接收者数量
const M = totalSent - totalReceived; // 发送与接收的差值
// 判断垃圾发送者规则
let isSpammer = L > 5 || M > 10; // 规则 1 和规则 2
if (!isSpammer) {
// 规则 3：检查是否有接收者与目标用户的发送接收差值超过 5
for (let receiver of outgoingMessages[targetId]?.uniqueReceivers || []) {
const sentToReceiver = outgoingMessages[targetId].totalSent;
const receivedFromReceiver = incomingMessages[receiver] || 0;
if (sentToReceiver - receivedFromReceiver > 5) {
isSpammer = true;
break;
}
}
}
// 返回结果，格式为 "isSpammer L M"
return `${isSpammer} ${L} ${M}`;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：