题目部分
题目 | 华为OD机考算法题:告警抑制 |
难度 | 易 |
题目说明 | 告警抑制,是指高优先级告警抑制低优先级告警的规则。高优先级告警产生后,低优先级告警不再产生。请根据原始告警列表和告警抑制关系,给出实际产生的告警列表。 注:不会出现循环抑制的情况。 告警不会传递,比如A->B,B->C,这种情况下A不会直接抑制C,但被抑制的告警仍然可以抑制其他低优先级告警。 如果两个告警存在抑制关系,被抑制的低优先级告警无论是在高优先级告警的前面还是后面,都会被抑制。(笔者注) |
输入描述 | 第一行为数字N,表示告警抑制关系个数,0<=N <=120。 接下来 N 行,每行是由空格分隔的两个告警ID,例如: id1 id2,表示id1抑制id2。告警ID的格式为:大写字母 + 0个或者1个数字。 最后一行为告警产生列表,列表长度[1,100]。 |
输出描述 | 真实产生的告警列表。 |
补充说明 | 告警 ID 之间以单个空格分隔。 |
------------------------------------------------------ | |
示例 | |
示例1 | |
输入 | 2 A B B C A B C D E |
输出 | A D E |
说明 | A抑制了B,B抑制了C,最后实际的告警为A D E。 |
示例2 | |
输入 | 4 F G C B A G A0 A A B C D E |
输出 | A C D E |
说明 | 无 |
解读与分析
题目解读:
此题要求从一个字符串中,删除被抑制的告警,只输出未被抑制的告警。输出后的告警顺序与源字符串保持一致。
注:在题目的告警列表中,如果两个告警存在抑制关系,无论被抑制的低优先级告警是在高优先级告警的前面还是后面,都会被抑制。题目中并未明说,但在示例 2 中是按照这个规则处理的。
此题在说明中存在歧义,需要通过示例 2 来澄清。个人认为,应该在题干中阐述清楚,而不是通过示例说明。
分析与思路:
先申明2个变量:
1. sourceAlarms,数组,输入的原始告警列表。
2. cutOffArray,二维数组,用以存放告警的抑制关系。数组的每个元素(设为 cutOffEle)是一个包含2个元素的抑制关系,cutOffEle[0] 是高优先级的告警,cutOffEle[1] 是被抑制的低优先级告警。
3. rmAlarmSet,集合,用以存储初始告警列表中需要删除的告警。
实现步骤如下:
1. 构建cutOffArray。逐行读取抑制关系,每行数据对应一个新的 cutOffEle。把每行数据拆分成两个告警ID,其中第一个告警 ID 放到 cutOffEle[0] 中,第二个告警 ID 放到 cutOffEle[1] 中,然后把 cutOffEle 作为元素放到数组 cutOffArray 中。
2. 构建 rmAlarmSet。遍历 cutOffArray,对于每个元素 cutOffEle,如果 cutOffEle[0] 在 sourceAlarms 中存在,则把 cutOffEle[1] 添加到 rmAlarmSet 中。
3. 遍历 sourceAlarms,如果告警 ID 不在 rmAlarmSet 中,则输出它;在 rmAlarmSet 中,则跳过。
说明:在第 2 步中,判断 cutOffEle[0] 在 sourceAlarms 中时,因为 sourceAlarms 是个数组,会让时间复杂度变大,可以先把 sourceAlarms 中所有的告警信息放到一个集合,如 sourceAlarmSet 中。
此算法的时间复杂度为 O(n),空间复杂度为 O(n)。
代码实现
Java代码
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
/**
* 告警抑制
* @since 2023.09.13
* @version 0.1
* @author Frank
*
*/
public class CutOffAlarms {
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[][] cutOffArray = new String[count][2];
for( int i = 0; i < count; i ++ )
{
input = sc.nextLine();
String[] curCutOff = input.split( " " );
cutOffArray[i] = curCutOff;
}
input = sc.nextLine();
String[] sourceAlarms = input.split( " " );
processCutOffAlarms( cutOffArray, sourceAlarms );
}
}
private static void processCutOffAlarms( String[][] cutOffArray, String sourceAlarms[] )
{
Set<String> sourceAlarmSet = new HashSet<String>();
for( int i = 0; i < sourceAlarms.length; i ++ )
{
sourceAlarmSet.add( sourceAlarms[i] );
}
Set<String> rmAlarmSet = new HashSet<String>();
for( int i = 0; i < cutOffArray.length; i ++ )
{
String[] curAlarmEle = cutOffArray[i];
if( sourceAlarmSet.contains( curAlarmEle[0] ) ) {
rmAlarmSet.add( curAlarmEle[1] );
}
}
StringBuffer sb = new StringBuffer();
for( int i = 0; i < sourceAlarms.length; i ++ )
{
String eachAlarm = sourceAlarms[i];
if( rmAlarmSet.contains( eachAlarm ))
{
continue;
}
sb.append( eachAlarm );
if( i != sourceAlarms.length - 1 )
{
sb.append( " " );
}
}
System.out.println( sb.toString() );
}
}
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 cutOffArray = new Array();
for (var i = 0; i < count; i++) {
line = await readline();
var curCutOff = line.split(" ");
cutOffArray[i] = curCutOff;
}
line = await readline();
var sourceAlarms = line.split(" ");
processUnhappyKids(cutOffArray, sourceAlarms);
}
}();
function processUnhappyKids(cutOffArray, sourceAlarms) {
var sourceAlarmSet = new Set();
for (var i = 0; i < sourceAlarms.length; i++) {
sourceAlarmSet.add(sourceAlarms[i]);
}
var rmAlarmSet = new Set();
for (var i = 0; i < cutOffArray.length; i++) {
var curAlarmEle = cutOffArray[i];
if (sourceAlarmSet.has(curAlarmEle[0])) {
rmAlarmSet.add(curAlarmEle[1]);
}
}
var ret = "";
for (var i = 0; i < sourceAlarms.length; i++) {
var eachAlarm = sourceAlarms[i];
if (rmAlarmSet.has(eachAlarm)) {
continue;
}
ret += eachAlarm;
if (i != sourceAlarms.length - 1) {
ret += " ";
}
}
console.log(ret);
}
(完)