力扣--3433. 统计用户被提及情况-育师

前言：

这是力扣第3433的一道中等算法题，废话不多说，看题目和代码！

题目：

给你一个整数numberOfUsers表示用户总数，另有一个大小为n x 3的数组events。

每个events[i]都属于下述两种类型之一：

消息事件（Message Event）：["MESSAGE", "timestampi", "mentions_stringi"]
- 事件表示在timestampi时，一组用户被消息提及。
- mentions_stringi字符串包含下述标识符之一：
  - id<number>：其中<number>是一个区间[0,numberOfUsers - 1]内的整数。可以用单个空格分隔多个 id ，并且 id 可能重复。此外，这种形式可以提及离线用户。
  - ALL：提及所有用户。
  - HERE：提及所有在线用户。
离线事件（Offline Event）：["OFFLINE", "timestampi", "idi"]
- 事件表示用户idi在timestampi时变为离线状态 60 个单位时间。用户会在timestampi + 60时自动再次上线。

返回数组mentions，其中mentions[i]表示 id 为i的用户在所有MESSAGE事件中被提及的次数。

最初所有用户都处于在线状态，并且如果某个用户离线或者重新上线，其对应的状态变更将会在所有相同时间发生的消息事件之前进行处理和同步。

注意在单条消息中，同一个用户可能会被提及多次。每次提及都需要被分别统计。

示例 1：

输入：numberOfUsers = 2, events = [["MESSAGE","10","id1 id0"],["OFFLINE","11","0"],["MESSAGE","71","HERE"]]

输出：[2,2]

解释：

最初，所有用户都在线。

时间戳 10 ，id1和id0被提及，mentions = [1,1]

时间戳 11 ，id0离线。

时间戳 71 ，id0再次上线并且"HERE"被提及，mentions = [2,2]

示例 2：

输入：numberOfUsers = 2, events = [["MESSAGE","10","id1 id0"],["OFFLINE","11","0"],["MESSAGE","12","ALL"]]

输出：[2,2]

解释：

最初，所有用户都在线。

时间戳 10 ，id1和id0被提及，mentions = [1,1]

时间戳 11 ，id0离线。

时间戳 12 ，"ALL"被提及。这种方式将会包括所有离线用户，所以id0和id1都被提及，mentions = [2,2]

示例 3：

输入：numberOfUsers = 2, events = [["OFFLINE","10","0"],["MESSAGE","12","HERE"]]

输出：[0,1]

解释：

最初，所有用户都在线。

时间戳 10 ，id0离线。

时间戳 12 ，"HERE"被提及。由于id0仍处于离线状态，其将不会被提及，mentions = [0,1]

提示：

1 <= numberOfUsers <= 100
1 <= events.length <= 100
events[i].length == 3
events[i][0]的值为MESSAGE或OFFLINE。
1 <= int(events[i][1]) <= 105
在任意"MESSAGE"事件中，以id<number>形式提及的用户数目介于1和100之间。
0 <= <number> <= numberOfUsers - 1
题目保证OFFLINE引用的用户 id 在事件发生时处于在线状态。

题目分析：

这个题目就是一个计算用户被@的次数，简单理解

ALL：@所有人

HERE：@在线人员

所有就可以理解成：

对于 ALL ，用一个变量统计所有用户被提及的次数，看到ALL就所有人加1。

对于 HERE 消息：

1、先认为所有用户都被提及了，把如同ALL，加1。
2、此刻离线的用户不能被计入，需要把这些用户的提及次数减1。
比如一个用户在 5 时刻离线，在 65 时刻在线，那么发生在 [5,64] 中的 HERE 消息个数，就是需要减去的提及次数。

借鉴前缀和的思想，用 [0,64] 中的 HERE 消息个数，减去 [0,4] 中的 HERE 消息个数，即为 [5,64] 中的 HERE 消息个数。

把离线事件、上线事件、HERE 消息混在一起，按照发生时间排序。相同时间的，HERE 消息排在后面。然后遍历这些事件，同时统计 HERE 消息个数 here。离线时加上 here，在线时减去 here。这样一加一减，最终减去的就是离线时的 HERE 消息个数。

代码：

class Solution {
public int[] countMentions(int numberOfUsers, List<List<String>> events) {
int[] ans = new int[numberOfUsers];
List<int[]> es = new ArrayList<>(); // (timestamp, type, id)
int all = 0;
for (List<String> e : events) {
int curT = Integer.parseInt(e.get(1)); // 当前时间
String mention = e.get(2);
if (e.get(0).charAt(0) == 'O') { // 离线
int i = Integer.parseInt(mention);
es.add(new int[]{curT, 1, i});
es.add(new int[]{curT + 60, -1, i});
} else if (mention.charAt(0) == 'A') { // @所有人
all++;
} else if (mention.charAt(0) == 'H') { // @所有在线用户
all++;
es.add(new int[]{curT, 2, -1});
} else { // @id
for (String s : mention.split(" ")) {
int i = Integer.parseInt(s.substring(2));
ans[i]++;
}
}
}
es.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
int here = 0;
for (int[] e : es) {
int type = e[1];
if (type == 2) {
here++;
} else {
// 注意 HERE 排在后面，还没有计入发生在此刻的 HERE 消息
ans[e[2]] += type * here; // type=1 是加，-1 是减
}
}
for (int i = 0; i < numberOfUsers; i++) {
ans[i] += all;
}
return ans;
}
}

代码分析：

1、初始化

一个ans数组用于统计每个用户被提交（艾特@）的次数

一个es列表用于存events中每个事件

一个all变量统计存放被@次数（提交次数）

int[] ans = new int[numberOfUsers];
List<int[]> es = new ArrayList<>(); // (timestamp, type, id)
int all = 0;

2、逻辑实现

events = [["MESSAGE","10","id1 id0"],["OFFLINE","11","0"],["MESSAGE","71","HERE"]]

events是一个列表含列表，在列表里面是字符串

先获取每个事件的时间戳和id

id这里看题要求，有三个可能

mentions_stringi字符串包含下述标识符之一：

id<number>：其中<number>是一个区间[0,numberOfUsers - 1]内的整数。可以用单个空格分隔多个id ，并且 id 可能重复。此外，这种形式可以提及离线用户。
ALL：提及所有用户。
HERE：提及所有在线用户。

然后all是所有人加1，here也是先所有人加1，后面删减不符合的

同时离线和离线在上线都需要加入到数组es，为后续计算here

最后还需要注意一下案例一那种情况!

for (List<String> e : events) {
int curT = Integer.parseInt(e.get(1)); // 当前时间
String mention = e.get(2);
if (e.get(0).charAt(0) == 'O') { // 离线
int i = Integer.parseInt(mention);
es.add(new int[]{curT, 1, i});//离线。type = 1
es.add(new int[]{curT + 60, -1, i});//重新上线 type = -1
} else if (mention.charAt(0) == 'A') { // @所有人
all++;
} else if (mention.charAt(0) == 'H') { // @所有在线用户
all++;
es.add(new int[]{curT, 2, -1});//here type = 2
} else { // @id
for (String s : mention.split(" ")) {
int i = Integer.parseInt(s.substring(2));
ans[i]++;
}
}
}

3、排序

对es数组进行排序，每个列表的第一个是时间戳，按时间戳升序排序，如果时间相等，先是type = -1 即重新上线的，在type = 1 即离线，最后再是type = 2 即here，也是升序

es.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

4、计算here

这里就是扣除here，因为统计here个数，离线是1是先记着，一旦上线变成-1，就扣除之前统计的here

int here = 0;
for (int[] e : es) {
int type = e[1];
if (type == 2) {
here++;
} else {
// 注意 HERE 排在后面，还没有计入发生在此刻的 HERE 消息
ans[e[2]] += type * here; // type=1 是加，-1 是减
}
}