算法刷题目其他题目
Source
Edit
History

undefined

用户在线波峰计算

题目：

输入： 用户日志(time, user_id, login | logout)
输出：同时在线人数的峰值，精确到秒

峰值会出现于在线人数最多的时候，那么某个时间点在线的人数就是：所有在这个时间点之前登入的 -（减去）在这个时间点之前所有登出的

实现：

  • 定义三个变量，其中一个记录当前在线人数（currentVal），一个最大值（maxVal），最后一个记录其对应的秒数的数组（seconds）
  • 将日志分成登陆、登出两种状态，并且根据时间进行正向排序
  • 遍历上一步得到的日志，
    • 如果是登陆则 currentVal + 1 并且和 maxVal 对比
      • 如果比 maxVal 大，则将 maxVal 设置为 currentVal，seconds 设置为当前秒数；
      • 如果 MaxVal == currentVal ，则 seconds 增加当前秒数
    • 如果是登出则 currentVal - 1 （更完美点应该判断当前是不是 maxVal，如果是则将上一次峰值的秒数 到 当前秒数的区间写入到 seconds）
  • 遍历完之后得到的 maxVal 就是峰值，seconds 数组就是对应秒数列表

航班预订统计

leetcode 1109 题目

这里有 n 个航班，它们分别从 1 到 n 进行编号。有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

解题思路

差分数组对应的概念是前缀和数组，对于数组[1,2,2,4]，其差分数组为 [1,1,0,2]，差分数组的第 i 个数即为原数组的第 i-1 个元素和第 i 个元素的差值，也就是说我们对差分数组求前缀和即可得到原数组。

差分数组有一个性质就是，当我们希望对原数组的某一区间 [left, right] 增加一个值 inc_val 时，差分数组对应的改变是：arr[left] 增加 inc_val 值，然后 arr[right+1] 减少 inc_val 值。 因为对 left 位置的增加，会蔓延到 left 位置之后的所有数值；而对 right+1 位置的减操作，刚好可以终止 right+1 位置及以后的所有位置的数值。也就可以恰当对 [left, right] 之间位置的元素进行了增加。这样对于区间的修改就变为了对两个位置的修改。并且这个修改是可以叠加的，即当我们多次对原数组的不同区间施加不同的增量，我们只要按规则修改差分数组即可。

最后注意下标，如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        std::vector<int> res(n, 0);
        for (auto& booking : bookings) {
            res[booking[0]-1] += booking[2];
            if (booking[1] < n) {
                res[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < res.size(); ++i) {
            res[i] += res[i-1];
        }
        return res;
    }
};

用户波峰计算

再来看用户波峰计算。输入的日志每行都是 uid、登入时间、登出时间

需要计算同时在线的峰值，精确到秒。而其中登入时间和登出时间是精确到秒的

解题思路

那也就是求登入时间和登出时间这个区间的 uid 个数。假设有 N 行数据。登出时间一定比登入时间晚。因此我们的差分数组想要计算 [登入时间，登出时间] 的 uid 个数。只需要在差分数组的 登入时间 的这个位置加 1，然后在差分数组的 登出时间+1 位置减 1 即可。那么理论上一天有 86400 秒。可以申请 长度为 86400 大小的数组。然后再最终还原差分数组时，求出最大值来，并且记录秒数区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 假定 logs 中每一行是 uin、登入时间、登出时间
void getUserCrest(std::vector<std::vector<int>>& logs) {
	int curDayTimeStamp = 1655220701; // 假定这是当天 0:00:00 时刻的时间戳
	std::vector<int> seconds(86400, 0);
	for (auto& log : logs) {
		seconds[log[1] - curDayTimeStamp] += 1;
        // 防止溢出，也就是如果登出时间为 curDayTimeStamp+86399 就无需操作
        if (log[2] - curDayTimeStamp + 1 < 86400) { 
			seconds[log[2] - curDayTimeStamp + 1] -= 1;
        }
	}
	// 波峰定义
	int maxVal = 0;
	// 发生的时间点
	std::vector<int> indexes;
	for (int i = 1; i < seconds.size(); ++i) {
		seconds[i] += seconds[i-1];
		if (seconds[i] > maxVal) {
			maxVal = seconds[i];
			indexes.removeAll();
			indexes.push_back(i);
		} else if (seconds[i] == maxVal) {
			indexes.push_back(i);
		}
	}
	
	// maxVal 即为波峰
	// indexes 即为出现波峰的时间点
}