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

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

article 2024/11/14 3:22:21

在这里插入图片描述

华为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、说明

  1. 输出该ID是否为垃圾短信发送者（是输出 true，否则输出 false），并且按序列输出L、M的值；
  2. 没有发过短信给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、说明

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

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

五、解题思路

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

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

六、Python算法源码

# 导入所需的模块
from collections import defaultdict

def main():
    import sys
    # 读取所有输入行
    input = sys.stdin.read().splitlines()
    # 第一行是条目数
    n = int(input[0])
    # 使用字典存储发送者到接收者的列表
    send_map = defaultdict(list)
    # 读取前n行的发送和接收ID
    for i in range(1, n + 1):
        sender, receiver = map(int, input[i].split())
        send_map[sender].append(receiver)
    # 最后一行是指定的ID A
    A = int(input[n + 1])

    # 获取A发送的短信列表，如果A没有发送短信则返回空列表
    a_to_list = send_map.get(A, [])

    # 计算 L：A 发送的接收者中，没有发过短信给 A 的人数
    unique_recipients = set(a_to_list)  # 去重后的接收者集合
    L = 0  # 初始化L
    for 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  # 初始化M
    for receivers in send_map.values():
        M += receivers.count(A)  # 统计所有发送者发送给A的短信数

    # 计算条件3：是否存在某个 X 使得 A 发送给 X 的短信数 - X 发送给 A 的短信数 > 5
    flag = False  # 初始化flag
    for 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 = True
            break  # 如果满足条件，设置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 A
    const A = parseInt(input[n + 1]);

    // 获取A发送的短信列表，如果A没有发送短信则返回空数组
    const aToList = sendMap.get(A) || [];

    // 计算 L：A 发送的接收者中，没有发过短信给 A 的人数
    const uniqueRecipients = new Set(aToList); // 去重后的接收者集合
    let L = 0; // 初始化L
    uniqueRecipients.forEach(recipient => {
        const recipientSentList = sendMap.get(recipient) || [];
        if (!recipientSentList.includes(A)) {
            L += 1; // 如果接收者没有发送短信给A，L加1
        }
    });

    // 计算 M：A 接收到的短信总数
    let M = 0; // 初始化M
    sendMap.forEach(receivers => {
        M += receivers.filter(receiver => receiver === A).length; // 统计所有发送者发送给A的短信数
    });

    // 计算条件3：是否存在某个 X 使得 A 发送给 X 的短信数 - X 发送给 A 的短信数 > 5
    let flag = false; // 初始化flag
    uniqueRecipients.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 101

int 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 A
    scanf("%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 的短信数 > 5
    int 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 A
    cin >> A;
    
    // 获取A发送的短信列表
    vector<int> aToList = sendMap[A];
    
    // 计算 L：A 发送的接收者中，没有发过短信给 A 的人数
    unordered_set<int> uniqueRecipients(aToList.begin(), aToList.end()); // 去重后的接收者集合
    int L = 0; // 初始化L
    for(auto &recipient : uniqueRecipients){
        // 检查接收者是否发送过短信给A
        bool hasSentToA = false;
        for(auto &msg : sendMap[recipient]){
            if(msg == A){
                hasSentToA = true;
                break;
            }
        }
        if(!hasSentToA){
            L++;
        }
    }
    
    // 计算 M：A 接收到的短信总数
    int M = 0; // 初始化M
    for(int i=0; i<101; i++){
        for(auto &receiver : sendMap[i]){
            if(receiver == A){
                M++;
            }
        }
    }
    
    // 计算条件3：是否存在某个 X 使得 A 发送给 X 的短信数 - X 发送给 A 的短信数 > 5
    bool flag = false; // 初始化flag
    for(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;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

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

在这里插入图片描述


http://www.kler.cn/a/390234.html

相关文章：

  • 基于迭代重加权最小二乘法的算法及例程
  • 【金融风控】特征评估与筛选详解
  • 【LeetCode】【算法】55. 跳跃游戏
  • LeetCode【0027】移除元素
  • 【前端】JavaScript高级教程：线程机制与事件机制
  • 【前端】深入浅出的React.js详解
  • Maven 项目模板
  • 探索Python图像处理的奥秘：Pillow库的全面指南
  • 请简述Vue与React的区别
  • 【Linux】进程信号全攻略（一）
  • 云上盛宴-腾讯云双11活动玩法攻略
  • 【Linux探索学习】第十一弹——初识操作系统：冯诺依曼体系结构与操作系统的概念与定位
  • 开源数据库 - mysql - mysql-server-8.4(gtid主主同步+ keepalived热切换)部署方案
  • Lua进阶用法之Lua和C的接口设计
  • uniapp实现H5和微信小程序获取当前位置（腾讯地图）
  • 确定图像的熵和各向异性 Halcon entropy_gray 解析
  • Spring资源加载模块，原来XML就这，活该被注解踩在脚下 手写Spring第六篇了
  • 【vue】封装一个可随时暂停启动无需担心副作用的定时器
  • AI - 人工智能；Open WebUI；Lobe Chat；Ollama
  • git clone相关问题和bug记录
  • 本地保存mysql凭据实现免密登录mysql
  • Ubuntu 18.04 安装Fast-planner
  • Ecmascript（ES）标准
  • 【新人系列】Python 入门（九）：数据结构 - 中
  • 深入探讨Vue项目中缺少明显入口文件的原因及解决策略
  • Spring Boot框架：计算机课程与工程认证的桥梁