华为OD机考算法题：垃圾信息拦截

题目部分


题目	垃圾信息拦截
难度	难
题目说明	大众对垃圾短信深恶痛绝，希望能对垃圾短信发送者进行识别，为此，很多软件增加了垃圾短信识别机制。经分析，发现正常用户的短信通常具备交互性，而垃圾短信往往都是大量单向的短信，按照如下规则进行垃圾短信识别：本题中，发送者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
输入	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
输出	true 13 13
说明	true 表示 1 是垃圾短信发送者。两个 13 代表发送者 1 对应的 L 和 M 值都是 13。true 13 13 之间用一个空格隔开。注意：true 是字符串输出。

示例2
输入	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
输出	false 0 -1
说明	无

解读与分析

题目解读：

通过题目要求的三条规则对用户进行判断。如果三条规则满足一条，则此用户为垃圾短信发送者。

分析与思路：

逐行读取短信发送信息，每行作为一个 string，存储到数组 inputs 中。
读取最后一行，读取要检查的 id，设为 idA。

申明如下变量：
1. receivers，一个集合，记录 idA 这个短信发送者发送短信的所有接收者 id。
2. senders，一个集合，记录所有给 idA 发送短信的用户 id。
3. aSendCnt，整型数字，初始值为 0。记录 idA 发送的短信条数。
4. aReceiveCnt，整型数字，初始值为 0。记录 idA 接收的短信条数。
5. msgSendCntMap，一个 map，记录 idA 发送给其他用户，和其他用户发送给 idA 的短信条数。其中 key 的格式为 idA + " " +“其他用户id” （代表 idA 给其他用户发短信），或 “其他用户id” + " " + idA（代表其他用户给 idA 发短信），值为整型数字，表示短信条数。

实现方法如下：
1. 遍历 inputs，对于 inputs中的每条字符串，设为 inputEle，以空格（" "）分隔，把它分成一个数组 inputEleSplits，其中 inputEleSplits[0] 为空格前的 id，即短信发送者的 id；inputEleSplits[1] 为短信接收者的 id。对 inputEle 和 inputEleSplits 进行如下判断：
① 如果 inputEleSplits[0] 和 inputsEleSplits[1] 都不等于 idA，那么忽略这条信息（即不做任何处理）。
② 如果 inputEleSplits[0] 等于 idA，那么把 inputEleSplits[1] 加到 receivers 中去，并把 aSendCnt 加 1。与此同时，获取 msgSendCntMap.get( inputEle ) 的值，如果值为空，则赋值为 1；若不为空，则把其值加 1。
③ 如果 inputEleSplits[1] 等于 idA，那么把 inputEleSplits[0] 加到 senders 中去，并把 aReceiveCnt 加 1。与此同时，获取 msgSendCntMap.get( inputEle ) 的值，如果值为空，则赋值为 1；若不为空，则把其值加 1。

2. 遍历完 inputs 后，receivers、senders、aSendCnt、aReceiveCnt、msgSendCntMap均已初始化完毕。下一步，进行入操作：
① 申请变量 recSendCnt，初始值为 0。用以记录既给 idA 发过信息，也收到过 idA 的信息的用户数。遍历 senders 的每个元素，如果元素在 receivers 中，则 recSendCnt 加 1。遍历完后，集合receviers 的元素个数与 recSendCnt 的差，即为 L 的值。
② 用 aSendCnt 减去 aReceiveCnt，即为 M 的值。
③ 先假设第三条规则不存在这样的用户，申明变量布尔变量 exsitsX ，并赋值为 false。遍历 receivers，设每个元素为 tmpReceiver，分别求 msgSendCntMap.get( idA + " " + tmpReceiver ) 和 msgSendCntMap.get( tmpReceiver + " " + idA ) 的值，如果为空，则赋值为 0。求前者减去后者的差值，如果差值大于 5，则 existsX 赋值为 true，退出遍历；否则继续遍历下一个 tmpReceiver。
④ 如果 L > 5 或 M > 5 或 existsX == true，则此用户为垃圾短信发送者。
最后，输出对应的值。

此题时间复杂度 O(n)，空间复杂度 O(n)。

代码实现

Java代码

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * 垃圾信息拦截
 * @since 2023.09.20
 * @version 0.1
 * @author Frank
 *
 */
public class MsgSpam {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String input = sc.nextLine();
			int count = Integer.parseInt( input );
			
			String[] inputs = new String[count];
			for( int i = 0; i < count; i ++ )
			{
				input = sc.nextLine();
				inputs[i] = input;
			}
			
			String idA = sc.nextLine();
			processMsgSpam( idA, inputs );
		}
	}

	private static void processMsgSpam( String idA, String inputs[] )
	{
		Set<String> receivers = new HashSet<String>();
		Set<String> senders = new HashSet<String>();
		int aSendCnt = 0;
		int aReceiveCnt = 0;
		Map<String, Integer> msgSendCntMap = new HashMap<String, Integer>();
		
		for( int i = 0; i < inputs.length; i ++ )
		{
			String inputEle = inputs[i];
			String[] inputEleSplits = inputEle.split( " " );
			
			if( ( !inputEleSplits[0].equals( idA ) ) &&  ( !inputEleSplits[1].equals( idA ) )  )
			{
				continue;
			}
			
			if( inputEleSplits[0].equals( idA ) )
			{
				receivers.add( inputEleSplits[1] );
				aSendCnt += 1;
			}else // inputEleSplits[1].equals( idA ) 
			{
				senders.add( inputEleSplits[0] );
				aReceiveCnt += 1;
			}
			Integer tmpCnt = msgSendCntMap.get( inputEle );
			if( tmpCnt == null )
			{
				tmpCnt = 0;
			}
			tmpCnt += 1;
			msgSendCntMap.put( inputEle, tmpCnt );				
		}
		
		int recSendCnt = 0;
		for( Iterator<String> iter = senders.iterator(); iter.hasNext(); )
		{
			String tmpSender = iter.next();
			if( receivers.contains( tmpSender ) )
			{
				recSendCnt ++;
			}
		}
		int L = receivers.size() - recSendCnt;
		
		int M = aSendCnt - aReceiveCnt;
		
		boolean existsX = false;
		for( Iterator<String> iter = receivers.iterator(); iter.hasNext(); )
		{
			String tmpReceiver = iter.next();
			Integer tmpSendCnt = msgSendCntMap.get( idA + " " + tmpReceiver );
			if( tmpSendCnt == null )
			{
				// will never come here
				continue;
			}
		
			Integer tmpReceiveCnt = msgSendCntMap.get( tmpReceiver + " " + idA );
			if( tmpReceiveCnt == null )
			{
				tmpReceiveCnt = 0;
			}
			if( tmpSendCnt - tmpReceiveCnt > 5 )
			{
				existsX = true;
				break;
			}
		}
		
		boolean isSpamSender = ( L > 5 ) || ( M > 5) || existsX;
		System.out.println( isSpamSender + " " + L + " " + M );
	}
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {
    while (line = await readline()) {
        var count = parseInt(line);

        var inputs = new Array();
        for (var i = 0; i < count; i++) {
            inputs[i] = await readline();
        }

        var idA = await readline();
        processMsgSpam(idA, inputs);
    }
}();

function processMsgSpam(idA, inputs) {
    var receivers = new Set();
    var senders = new Set();
    var aSendCnt = 0;
    var aReceiveCnt = 0;
    var msgSendCntMap = new Map();

    for (var i = 0; i < inputs.length; i++) {
        var inputEle = inputs[i];
        var inputEleSplits = inputEle.split(" ");

        if ((inputEleSplits[0] != idA) && (inputEleSplits[1] != idA)) {
            continue;
        }

        if (inputEleSplits[0] == idA) {
            receivers.add(inputEleSplits[1]);
            aSendCnt += 1;
        } else // inputEleSplits[1].equals( idA ) 
        {
            senders.add(inputEleSplits[0]);
            aReceiveCnt += 1;
        }
        var tmpCnt = msgSendCntMap.get(inputEle);
        if (tmpCnt == null) {
            tmpCnt = 0;
        }
        tmpCnt += 1;
        msgSendCntMap.set(inputEle, tmpCnt);
    }

    var recSendCnt = 0;
    for (const item of senders) {
        if (receivers.has(item)) {
            recSendCnt++;
        }
    }
    var L = receivers.size - recSendCnt;

    var M = aSendCnt - aReceiveCnt;

    var existsX = false;
    for (const item of receivers) {
        var tmpSendCnt = msgSendCntMap.get(idA + " " + item);
        if (tmpSendCnt == null) {
            // will never come here
            continue;
        }

        var tmpReceiveCnt = msgSendCntMap.get(item + " " + idA);
        if (tmpReceiveCnt == null) {
            tmpReceiveCnt = 0;
        }
        if (tmpSendCnt - tmpReceiveCnt > 5) {
            existsX = true;
            break;
        }
    }

    var isSpamSender = (L > 5) || (M > 5) || existsX;
    console.log(isSpamSender + " " + L + " " + M);
}

(完)