当前位置：首页 > news >正文

华为OD机试 - 垃圾短信识别（Python/JS/C/C++ 2024 E卷 100分）

news 2025/5/8 23:47:55

在这里插入图片描述

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

专栏导读

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

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

一、题目描述

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

本题中，发送者A符合以下条件之⼀的，则认为A是垃圾短信发送者：

A发送给B的直接短信中，没有发送给B的总数＞5；
A发送的短信数＞A接收的短信数 M＞10；
如果M存在，A发送给C的短信数－A接收到C的短信数 N＞5；

二、输入描述

第⼀⾏是条⽬总数，接下来是⼏⾏具体的条⽬，每个条⽬是⼀对ID，第⼀个数字是发送者ID，后⾯的数字是接收者ID，中间空格隔开，所有的ID都为⽆符号整数，ID最⼤值为100；

同⼀条⽬中，两个ID不会相同（即不会把⼀个⼈发消息⾃⼰）。

最后⼀⾏为指定的ID。

三、输出描述

输出该ID是否为垃圾短信发送者，并且按垃圾序列输出L与M的值（由于N值不唯⼀，不需要输出）；输出均为空格分隔。

四、测试用例

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
1

2、输出

true 13 13

3、说明

true 表示1是垃圾短信发送者，两个数字，代表发送者1对应的L和M值。
true 13 13 中间以一个空格分割。注意 true 是字符串输出。

五、解题思路

使用Scanner读取输入，包括短信记录的数量、具体记录、以及要检查的指定ID。
统计发送和接收信息：
- 使用LinkedList存储发送和接收的ID。
- 使用HashMap统计每个ID发送和接收的短信数量。
计算L值和M值：
- L值：发送者发送给不同接收者的短信数量（不重复计算接收者）。
- M值：发送者发送的短信数量减去接收的短信数量。
判断垃圾短信发送者：
- 检查以下条件：
  - L值大于5。
  - M值大于10。
  - 对于每个发送给的接收者，检查发送数量与接收数量的差值是否大于5。
输出结果：打印结果，格式为true/false L M。

六、Python算法源码

# 导入所需的模块
from collections import defaultdictdef get_result(tid, arr):# 用于存储发送和接收的IDsend = []receive = []# 统计发送和接收的数量send_count = defaultdict(int)  # 发送统计receive_count = defaultdict(int)  # 接收统计# 处理每条短信记录for sid, rid in arr:# 如果发送者是指定的IDif sid == tid:send.append(rid)  # 添加接收者ID到发送列表send_count[rid] += 1  # 统计发送给接收者的次数# 如果接收者是指定的IDif rid == tid:receive.append(sid)  # 添加发送者ID到接收列表receive_count[sid] += 1  # 统计接收到的次数# 使用集合去重send_set = set(send)receive_set = set(receive)# 计算连接的数量（即同时发送和接收的ID）connect = send_set.intersection(receive_set)# 计算L和M值l = len(send_set) - len(connect)  # L值m = len(send) - len(receive)  # M值# 判断是否为垃圾短信发送者is_spammers = l > 5 or m > 10# 如果不是垃圾发送者，检查其他条件if not is_spammers:for rid in send_set:# 检查发送给每个接收者的差值是否大于5if send_count[rid] - receive_count[rid] > 5:is_spammers = Truebreak# 返回结果return f"{is_spammers} {l} {m}"# 主程序入口
if __name__ == "__main__":# 读取条目总数n = int(input())arr = []# 读取每条短信记录for _ in range(n):arr.append(tuple(map(int, input().split())))# 读取指定的IDid = int(input())# 调用计算结果的方法并输出print(get_result(id, arr))

七、JavaScript算法源码

function getResult(tid, arr) {// 用于存储发送和接收的IDconst send = [];const receive = [];// 统计发送和接收的数量const sendCount = new Map();  // 发送统计const receiveCount = new Map();  // 接收统计// 处理每条短信记录for (let [sid, rid] of arr) {// 如果发送者是指定的IDif (sid === tid) {send.push(rid);  // 添加接收者ID到发送列表sendCount.set(rid, (sendCount.get(rid) || 0) + 1);  // 统计发送给接收者的次数}// 如果接收者是指定的IDif (rid === tid) {receive.push(sid);  // 添加发送者ID到接收列表receiveCount.set(sid, (receiveCount.get(sid) || 0) + 1);  // 统计接收到的次数}}// 使用Set去重const sendSet = new Set(send);const receiveSet = new Set(receive);// 计算连接的数量（即同时发送和接收的ID）const connect = [...sendSet].filter(id => receiveSet.has(id));// 计算L和M值const l = sendSet.size - connect.length;  // L值const m = send.length - receive.length;  // M值// 判断是否为垃圾短信发送者let isSpammers = l > 5 || m > 10;// 如果不是垃圾发送者，检查其他条件if (!isSpammers) {for (let rid of sendSet) {// 检查发送给每个接收者的差值是否大于5if ((sendCount.get(rid) || 0) - (receiveCount.get(rid) || 0) > 5) {isSpammers = true;break;}}}// 返回结果return `${isSpammers} ${l} ${m}`;
}// 主程序入口
const input = require('fs').readFileSync('/dev/stdin', 'utf-8').trim().split('\n');
const n = parseInt(input[0]);
const arr = input.slice(1, n + 1).map(line => line.split(' ').map(Number));
const id = parseInt(input[n + 1]);// 调用计算结果的方法并输出
console.log(getResult(id, arr));

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_USERS 100// 统计发送和接收的数量
int sendCount[MAX_USERS + 1];
int receiveCount[MAX_USERS + 1];int getResult(int tid, int arr[][2], int n) {// 用于存储发送和接收的唯一IDint sendSet[MAX_USERS + 1] = {0}; // 发送的接收者IDint receiveSet[MAX_USERS + 1] = {0}; // 接收的发送者IDint sendSize = 0, receiveSize = 0;// 处理每条短信记录for (int i = 0; i < n; i++) {int sid = arr[i][0]; // 发送者IDint rid = arr[i][1]; // 接收者ID// 如果发送者是指定的IDif (sid == tid) {sendSet[rid] = 1; // 标记该接收者IDsendCount[rid]++; // 统计发送给接收者的次数sendSize++; // 增加发送数量}// 如果接收者是指定的IDif (rid == tid) {receiveSet[sid] = 1; // 标记该发送者IDreceiveCount[sid]++; // 统计接收到的次数receiveSize++; // 增加接收数量}}// 计算连接的数量（即同时发送和接收的ID）int connect = 0;for (int i = 1; i <= MAX_USERS; i++) {if (sendSet[i] && receiveSet[i]) {connect++; // 计算同时发送和接收的数量}}// 计算L和M值int l = sendSize - connect; // L值int m = 0;for (int i = 1; i <= MAX_USERS; i++) {m += sendCount[i]; // 发送的总数}m -= receiveSize; // M值// 判断是否为垃圾短信发送者int isSpammers = (l > 5 || m > 10);// 如果不是垃圾发送者，检查其他条件if (!isSpammers) {for (int i = 1; i <= MAX_USERS; i++) {if (sendSet[i] && (sendCount[i] - receiveCount[i] > 5)) {isSpammers = 1; // 标记为垃圾短信发送者break;}}}// 输出结果printf("%s %d %d\n", isSpammers ? "true" : "false", l, m);return 0;
}// 主程序入口
int main() {int n;scanf("%d", &n);int arr[n][2];// 读取每条短信记录for (int i = 0; i < n; i++) {scanf("%d %d", &arr[i][0], &arr[i][1]);}// 读取指定的IDint id;scanf("%d", &id);// 调用计算结果的方法getResult(id, arr, n);return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>using namespace std;// 计算结果的函数
string getResult(int tid, const vector<pair<int, int>>& arr) {unordered_set<int> sendSet;  // 用于存储发送的接收者IDunordered_set<int> receiveSet;  // 用于存储接收的发送者IDunordered_map<int, int> sendCount;  // 统计发送给每个接收者的次数unordered_map<int, int> receiveCount;  // 统计接收到的次数// 处理每条短信记录for (const auto& ele : arr) {int sid = ele.first;  // 发送者IDint rid = ele.second;  // 接收者ID// 如果发送者是指定的IDif (sid == tid) {sendSet.insert(rid);  // 添加接收者ID到发送集合sendCount[rid]++;  // 统计发送给接收者的次数}// 如果接收者是指定的IDif (rid == tid) {receiveSet.insert(sid);  // 添加发送者ID到接收集合receiveCount[sid]++;  // 统计接收到的次数}}// 计算连接的数量（即同时发送和接收的ID）int connect = 0;for (int id : sendSet) {if (receiveSet.count(id)) {connect++;  // 统计同时发送和接收的ID}}// 计算L和M值int l = sendSet.size() - connect;  // L值int m = sendCount.size() - receiveSet.size();  // M值// 判断是否为垃圾短信发送者bool isSpammers = (l > 5 || m > 10);// 如果不是垃圾发送者，检查其他条件if (!isSpammers) {for (int id : sendSet) {if (sendCount[id] - receiveCount[id] > 5) {isSpammers = true;  // 标记为垃圾短信发送者break;}}}// 返回结果return to_string(isSpammers) + " " + to_string(l) + " " + to_string(m);
}// 主程序入口
int main() {int n;cin >> n;  // 读取条目总数vector<pair<int, int>> arr(n);// 读取每条短信记录for (int i = 0; i < n; i++) {cin >> arr[i].first >> arr[i].second;  // 读取发送者和接收者ID}// 读取指定的IDint id;cin >> id;// 调用计算结果的方法并输出cout << getResult(id, arr) << endl;return 0;
}