【离线查询 滑动窗口】2747. 统计没有收到请求的服务器数目|2405
本文涉及知识点离线查询
C++算法：滑动窗口总结
LeetCode2747. 统计没有收到请求的服务器数目
给你一个整数 n ，表示服务器的总数目，再给你一个下标从 0 开始的 二维 整数数组 logs ，此中 logs = 表示 id 为 server_id 的服务器在 time 时收到了一个请求。
同时给你一个整数 x 和一个下标从 0 开始的整数数组 queries 。
请你返回一个长度即是 queries.length 的数组 arr ，此中 arr 表示在时间区间 - x, queries] 内没有收到请求的服务器数目。
留意时间区间是个闭区间。
示例 1：
输入：n = 3, logs = [,,], x = 5, queries =
输出：
解释：
对于 queries：id 为 1 和 2 的服务器在区间 内收到了请求，以是只有服务器 3 没有收到请求。
对于 queries：id 为 2 的服务器在区间 内收到了请求，以是 id 为 1 和 3 的服务器在这个时间段内没有收到请求。
示例 2：
输入：n = 3, logs = [,,,], x = 2, queries =
输出：
解释：
对于 queries：区间 内所有服务器都收到了请求。
对于 queries：只有 id 为 3 的服务器在区间 内没有收到请求。
提示：
1 <= n <= 105
1 <= logs.length <= 105
1 <= queries.length <= 105
logs.length == 2
1 <= logs <= n
1 <= logs <= 106
1 <= x <= 105
x < queries <= 106
滑动窗口+离线查询
一，logs按time升序排序。
二，queries按升序排序。
三：通过que罗列queries。
time小于即是que进入滑动窗口。
time小于que-x离开滑动窗口。
滑动窗口：
小根堆记录{time,serverid}
哈希映射记录有消息的服务器数目。
n - 有消息的服务器数目 就是答案。
留意：不能对queries排序，对其下标排序。
代码
核心代码
template<class KEY>
class CKeyCount
{
public:
void Add(const KEY& key, int iCount)
{
Cnt += iCount;
if (0 == Cnt)
{
Cnt.erase(key);
}
}
std::unordered_map<KEY, int> Cnt;
};
class Solution {
public:
vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
sort(logs.begin(), logs.end(), [](const vector<int>& v1, const vector<int>& v2) {return v1 < v2; });
vector<int> indexs(queries.size());
iota(indexs.begin(), indexs.end(), 0);
sort(indexs.begin(), indexs.end(), [&](int i1, int i2) {return queries < queries; });
priority_queue<pair<int, int>, vector< pair<int, int>>, std::greater<>> heap;
CKeyCount<int> cnt;
vector<int> ret(indexs.size());
int i = 0;
for (int j : indexs) {
auto que = queries;
while ((i < logs.size()) && (logs <= que)) {
cnt.Add(logs, 1);
heap.emplace(logs, logs);
i++;
}
while (heap.size() && (heap.top().first < que - x)) {
cnt.Add(heap.top().second, -1);
heap.pop();
}
ret = n - cnt.Cnt.size();
}
return ret;
}
};
单元测试
template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
Assert::AreEqual(t1, t2);
}
void AssertEx( double t1,double t2)
{
auto str = std::to_wstring(t1) + std::wstring(1,32) + std::to_wstring(t2);
Assert::IsTrue(abs(t1 - t2) < 1e-5,str.c_str() );
}
template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
Assert::AreEqual(v1.size(), v2.size());
for (int i = 0; i < v1.size(); i++)
{
Assert::AreEqual(v1, v2);
}
}
template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
sort(vv1.begin(), vv1.end());
sort(vv2.begin(), vv2.end());
Assert::AreEqual(vv1.size(), vv2.size());
for (int i = 0; i < vv1.size(); i++)
{
AssertEx(vv1, vv2);
}
}
namespace UnitTest
{
int n;
vector<vector<int>> logs;
int x;
vector<int> queries;
TEST_CLASS(UnitTest)
{
public:
TEST_METHOD(TestMethod00)
{
n = 3, logs = { {1,3},{2,6},{1,5} }, x = 5, queries = { 10,11 };
auto res = Solution().countServers(n, logs, x, queries);
AssertEx(vector<int>{1, 2}, res);
}
TEST_METHOD(TestMethod01)
{
n = 3, logs = { {2,4},{2,1},{1,2},{3,1} }, x = 2, queries = { 3,4 };
auto res = Solution().countServers(n, logs, x, queries);
AssertEx(vector<int>{0,1}, res);
}
};
}
https://img-blog.csdnimg.cn/8d37dcd13ddb4df9af8f95fefd86828d.gif#pic_center#pic_center
扩展阅读
视频课程
先学简朴的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相干推荐
我想对大家说的话《喜缺全书算法册》以原理、精确性证明、总结为主。按种别查阅鄙人的算法文章，请点击《算法与数据汇总》。有效学习：明确的目标 实时的反馈 拉伸区（难度合适） 专注闻缺陷则喜(喜缺)是一个优美的愿望，早发现问题，早修改问题，给老板节省钱。子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。如果步伐是一条龙，那算法就是他的是睛 测试环境
操作系统：win7 开辟环境： VS2019 C++17
或者 操作系统：win10 开辟环境： VS2022 C++17
如无特殊阐明，本算法用**C++**实现。
https://i-blog.csdnimg.cn/blog_migrate/4b48f80cdf99b7ea9bda88ceb91d788f.gif#pic_center
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]