华为OD机试 - 垃圾信息拦截（Python/JS/C/C++ 2024 C卷 100分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

大众对垃圾短信深恶痛绝，希望能对垃圾短信发送者进行识别，为此，很多软件增加了垃圾短信识别机制。经分析，发现正常用户的短信通常具备交互性，而垃圾短信往往都是大量单向的短信，按照如下规则进行垃圾短信识别：

本题中，发送者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是否为垃圾短信发送者（是输出 true，否则输出 false），并且按序列输出L、M的值（由于N值不唯一，不需要输出）；
输出均为宇符串。

四、测试用例

测试用例1

1、输入

8
1 2
1 3
1 4
1 5
1 6
6 1
5 2
6 3
1

2、输出

false 4 1

3、说明

输出该ID是否为垃圾短信发送者（是输出 true，否则输出 false），并且按序列输出L、M的值；
没有发过短信给A的人数L，A接收的短信数 M。

没有发过短信给A的人数L为4，A接收的短信数 M为1。

测试用例2

1、输入

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

2、输出

false 4 3

3、说明

输出该ID是否为垃圾短信发送者（是输出 true，否则输出 false），并且按序列输出L、M的值；
没有发过短信给A的人数L，A接收的短信数 M。

没有发过短信给A的人数L为4，A接收的短信数 M为3。

五、解题思路

此题还是很简单的，根据题意解析即可。

定义没有发过短信给A的人数L、A接收的短信数 M、A 发送给 X 的短信数X、A 接收到X的短信数N；
遍历A发送的短信关系aToList；
获取接收A短信的用户的短信发送信息；
如果未给A发送，则没有发过短信给A的人数L++；
否则A接收的短信数 M++；
获取A 发送给 X 的短信数X、A 接收到X的短信数N；
如果存在 X，A 发送给 X 的短信数 - A 接收到X的短信数N > 5，则视为垃圾短信发送者，输出true，不再计算N值；
根据①、②、③判断条件，判断是否为垃圾短信发送者，满足一个即为垃圾短信发送者：
1. A 发送短信的接收者中，没有发过短信给A的人数 L > 5；
2. A 发送的短信数 - A接收的短信数 M > 10；
3. 如果存在 X，A 发送给 X 的短信数 - A 接收到X的短信数N > 5；
输出该ID是否为垃圾短信发送者（是输出 true，否则输出 false），并且按序列输出L、M的值。

六、Python算法源码

# 导入所需的模块
from collections import defaultdictdef main():import sys# 读取所有输入行input = sys.stdin.read().splitlines()# 第一行是条目数n = int(input[0])# 使用字典存储发送者到接收者的列表send_map = defaultdict(list)# 读取前n行的发送和接收IDfor i in range(1, n + 1):sender, receiver = map(int, input[i].split())send_map[sender].append(receiver)# 最后一行是指定的ID AA = int(input[n + 1])# 获取A发送的短信列表，如果A没有发送短信则返回空列表a_to_list = send_map.get(A, [])# 计算 L：A 发送的接收者中，没有发过短信给 A 的人数unique_recipients = set(a_to_list)  # 去重后的接收者集合L = 0  # 初始化Lfor recipient in unique_recipients:recipient_sent_list = send_map.get(recipient, [])if A not in recipient_sent_list:L += 1  # 如果接收者没有发送短信给A，L加1# 计算 M：A 接收到的短信总数M = 0  # 初始化Mfor receivers in send_map.values():M += receivers.count(A)  # 统计所有发送者发送给A的短信数# 计算条件3：是否存在某个 X 使得 A 发送给 X 的短信数 - X 发送给 A 的短信数 > 5flag = False  # 初始化flagfor recipient in unique_recipients:sent_to_x = a_to_list.count(recipient)  # A发送给X的短信数x_sent_list = send_map.get(recipient, [])received_from_x = x_sent_list.count(A)  # X发送给A的短信数if sent_to_x - received_from_x > 5:flag = Truebreak  # 如果满足条件，设置flag为True并退出循环# 计算 A 发送的短信总数a_send = len(a_to_list)# 判断是否为垃圾短信发送者is_spam = (L > 5) or ((a_send - M) > 10) or flag# 输出结果，按照题目要求的格式print(f"{str(is_spam).lower()} {L} {M}")# 调用主函数
if __name__ == "__main__":main()

七、JavaScript算法源码

// 引入读取标准输入的模块
const readline = require('readline');// 创建接口实例
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});// 存储所有输入行
let input = [];// 监听每一行输入
rl.on('line', (line) => {input.push(line);
});// 输入结束后执行的函数
rl.on('close', () => {// 第一行是条目数const n = parseInt(input[0]);// 使用Map存储发送者到接收者的数组const sendMap = new Map();for (let i = 1; i <= n; i++) {const [sender, receiver] = input[i].split(' ').map(Number);if (!sendMap.has(sender)) {sendMap.set(sender, []);}sendMap.get(sender).push(receiver);}// 最后一行是指定的ID Aconst A = parseInt(input[n + 1]);// 获取A发送的短信列表，如果A没有发送短信则返回空数组const aToList = sendMap.get(A) || [];// 计算 L：A 发送的接收者中，没有发过短信给 A 的人数const uniqueRecipients = new Set(aToList); // 去重后的接收者集合let L = 0; // 初始化LuniqueRecipients.forEach(recipient => {const recipientSentList = sendMap.get(recipient) || [];if (!recipientSentList.includes(A)) {L += 1; // 如果接收者没有发送短信给A，L加1}});// 计算 M：A 接收到的短信总数let M = 0; // 初始化MsendMap.forEach(receivers => {M += receivers.filter(receiver => receiver === A).length; // 统计所有发送者发送给A的短信数});// 计算条件3：是否存在某个 X 使得 A 发送给 X 的短信数 - X 发送给 A 的短信数 > 5let flag = false; // 初始化flaguniqueRecipients.forEach(recipient => {const sentToX = aToList.filter(r => r === recipient).length; // A发送给X的短信数const xSentList = sendMap.get(recipient) || [];const receivedFromX = xSentList.filter(r => r === A).length; // X发送给A的短信数if (sentToX - receivedFromX > 5) {flag = true;}});// 计算 A 发送的短信总数const aSend = aToList.length;// 判断是否为垃圾短信发送者const isSpam = (L > 5) || ((aSend - M) > 10) || flag;// 输出结果，按照题目要求的格式console.log(`${isSpam} ${L} ${M}`);
});

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义最大ID值
#define MAX_ID 101int main() {int n;// 读取条目数scanf("%d", &n);// 定义发送者到接收者的数组，每个发送者有一个接收者列表int sendMap[MAX_ID][MAX_ID];int sendCount[MAX_ID];// 初始化发送计数for(int i=0;i<MAX_ID;i++) {sendCount[i] = 0;for(int j=0; j<MAX_ID; j++) {sendMap[i][j] = 0;}}// 读取n条发送记录for(int i=0; i<n; i++) {int sender, receiver;scanf("%d %d", &sender, &receiver);sendMap[sender][sendCount[sender]++] = receiver;}int A;// 读取指定的ID Ascanf("%d", &A);// 获取A发送的短信列表int aToList[MAX_ID];int aToSize = sendCount[A];for(int i=0; i<aToSize; i++) {aToList[i] = sendMap[A][i];}// 计算 L：A 发送的接收者中，没有发过短信给 A 的人数int uniqueRecipients[MAX_ID];int uniqueSize = 0;// 去重for(int i=0; i<aToSize; i++) {int exists = 0;for(int j=0; j<uniqueSize; j++) {if(uniqueRecipients[j] == aToList[i]) {exists = 1;break;}}if(!exists) {uniqueRecipients[uniqueSize++] = aToList[i];}}int L = 0;for(int i=0; i<uniqueSize; i++) {int recipient = uniqueRecipients[i];int sentListSize = sendCount[recipient];int hasSentToA = 0;for(int j=0; j<sentListSize; j++) {if(sendMap[recipient][j] == A) {hasSentToA = 1;break;}}if(!hasSentToA) {L++;}}// 计算 M：A 接收到的短信总数int M = 0;for(int i=0; i<MAX_ID; i++) {for(int j=0; j<sendCount[i]; j++) {if(sendMap[i][j] == A) {M++;}}}// 计算条件3：是否存在某个 X 使得 A 发送给 X 的短信数 - X 发送给 A 的短信数 > 5int flag = 0;for(int i=0; i<uniqueSize; i++) {int recipient = uniqueRecipients[i];// 计算 A 发送给X的短信数int sentToX = 0;for(int j=0; j<aToSize; j++) {if(aToList[j] == recipient) {sentToX++;}}// 计算 X 发送给A的短信数int receivedFromX = 0;for(int j=0; j<sendCount[recipient]; j++) {if(sendMap[recipient][j] == A) {receivedFromX++;}}if((sentToX - receivedFromX) > 5) {flag = 1;break;}}// 计算 A 发送的短信总数int aSend = aToSize;// 判断是否为垃圾短信发送者int isSpam = (L > 5) || ((aSend - M) > 10) || flag;// 输出结果，按照题目要求的格式printf("%s %d %d\n", isSpam ? "true" : "false", L, M);return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);int n;// 读取条目数cin >> n;// 定义发送者到接收者的映射vector<vector<int>> sendMap(101, vector<int>());// 读取n条发送记录for(int i=0; i<n; i++){int sender, receiver;cin >> sender >> receiver;sendMap[sender].push_back(receiver);}int A;// 读取指定的ID Acin >> A;// 获取A发送的短信列表vector<int> aToList = sendMap[A];// 计算 L：A 发送的接收者中，没有发过短信给 A 的人数unordered_set<int> uniqueRecipients(aToList.begin(), aToList.end()); // 去重后的接收者集合int L = 0; // 初始化Lfor(auto &recipient : uniqueRecipients){// 检查接收者是否发送过短信给Abool hasSentToA = false;for(auto &msg : sendMap[recipient]){if(msg == A){hasSentToA = true;break;}}if(!hasSentToA){L++;}}// 计算 M：A 接收到的短信总数int M = 0; // 初始化Mfor(int i=0; i<101; i++){for(auto &receiver : sendMap[i]){if(receiver == A){M++;}}}// 计算条件3：是否存在某个 X 使得 A 发送给 X 的短信数 - X 发送给 A 的短信数 > 5bool flag = false; // 初始化flagfor(auto &recipient : uniqueRecipients){// 计算 A 发送给X的短信数int sentToX = 0;for(auto &msg : aToList){if(msg == recipient){sentToX++;}}// 计算 X 发送给A的短信数int receivedFromX = 0;for(auto &msg : sendMap[recipient]){if(msg == A){receivedFromX++;}}if((sentToX - receivedFromX) > 5){flag = true;break;}}// 计算 A 发送的短信总数int aSend = aToList.size();// 判断是否为垃圾短信发送者bool isSpam = (L > 5) || ((aSend - M) > 10) || flag;// 输出结果，按照题目要求的格式cout << (isSpam ? "true" : "false") << " " << L << " " << M;return 0;
}