【离线查询 滑动窗口】2747. 统计没有收到请求的服务器数目
创始人
2024-09-25 09:22:24
0

本文涉及知识点

离线查询 C++算法:滑动窗口总结

LeetCode2747. 统计没有收到请求的服务器数目

给你一个整数 n ,表示服务器的总数目,再给你一个下标从 0 开始的 二维 整数数组 logs ,其中 logs[i] = [server_id, time] 表示 id 为 server_id 的服务器在 time 时收到了一个请求。
同时给你一个整数 x 和一个下标从 0 开始的整数数组 queries 。
请你返回一个长度等于 queries.length 的数组 arr ,其中 arr[i] 表示在时间区间 [queries[i] - x, queries[i]] 内没有收到请求的服务器数目。
注意时间区间是个闭区间。
示例 1:
输入:n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]
输出:[1,2]
解释:
对于 queries[0]:id 为 1 和 2 的服务器在区间 [5, 10] 内收到了请求,所以只有服务器 3 没有收到请求。
对于 queries[1]:id 为 2 的服务器在区间 [6,11] 内收到了请求,所以 id 为 1 和 3 的服务器在这个时间段内没有收到请求。
示例 2:
输入:n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]
输出:[0,1]
解释:
对于 queries[0]:区间 [1, 3] 内所有服务器都收到了请求。
对于 queries[1]:只有 id 为 3 的服务器在区间 [2,4] 内没有收到请求。
提示:
1 <= n <= 105
1 <= logs.length <= 105
1 <= queries.length <= 105
logs[i].length == 2
1 <= logs[i][0] <= n
1 <= logs[i][1] <= 106
1 <= x <= 105
x < queries[i] <= 106

滑动窗口+离线查询

一,logs按time升序排序。
二,queries按升序排序。
三:通过que枚举queries。
time小于等于que进入滑动窗口。
time小于que-x离开滑动窗口。
滑动窗口:
小根堆记录{time,serverid}
哈希映射记录有消息的服务器数量。
n - 有消息的服务器数量 就是答案。
注意:不能对queries排序,对其下标排序。

代码

核心代码

 template class CKeyCount { public: 	void Add(const KEY& key, int iCount) 	{ 		Cnt[key] += iCount; 		if (0 == Cnt[key]) 		{ 			Cnt.erase(key); 		} 	} 	std::unordered_map Cnt; };  class Solution { public: 	vector countServers(int n, vector>& logs, int x, vector& queries) { 		sort(logs.begin(), logs.end(), [](const vector& v1, const vector& v2) {return v1[1] < v2[1]; }); 		vector indexs(queries.size()); 		iota(indexs.begin(), indexs.end(), 0); 		sort(indexs.begin(), indexs.end(), [&](int i1, int i2) {return queries[i1] < queries[i2]; }); 		priority_queue, vector< pair>, std::greater<>> heap; 		CKeyCount cnt; 		vector ret(indexs.size()); 		int i = 0; 		for (int j : indexs) { 			auto que = queries[j]; 			while ((i < logs.size()) && (logs[i][1] <= que)) { 				cnt.Add(logs[i][0], 1);				 				heap.emplace(logs[i][1], logs[i][0]); 				i++; 			} 			while (heap.size() && (heap.top().first < que - x)) { 				cnt.Add(heap.top().second, -1); 				heap.pop(); 			} 			ret[j] = n - cnt.Cnt.size(); 		} 		return ret; 	} }; 

单元测试

template 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 void AssertEx(const vector& v1, const vector& v2) { 	Assert::AreEqual(v1.size(), v2.size()); 	for (int i = 0; i < v1.size(); i++) 	{ 		Assert::AreEqual(v1[i], v2[i]); 	} }  template void AssertV2(vector> vv1, vector> 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[i], vv2[i]); 	} }  namespace UnitTest { 	int n; 	vector> logs; 	int x; 	vector 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{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{0,1}, res); 		} 	}; } 

扩展阅读

视频课程

先学简单的课程,请移步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++**实现。

相关内容

热门资讯

七分钟实锤!(wpk外挂是真的... 七分钟实锤!(wpk外挂是真的还是假的!软件透明挂)外挂辅助器代打(2022已更新)(哔哩哔哩)是一...
两分钟了解!Wepoke游戏(... 两分钟了解!Wepoke游戏(wepoKe)外挂透明挂助手,太过分了原来一直总是有挂(2021已更新...
6分钟实锤!(wepoke软件... 6分钟实锤!(wepoke软件透明挂检测!透视辅助)外挂辅助器工具(2024已更新)(哔哩哔哩);小...
三分钟了解!Wepoke安装(... 三分钟了解!Wepoke安装(wePOKE)外挂辅助器插件,太嚣张了原来是真的有挂(2021已更新)...
七分钟实锤!(aa扑克不能用模... 七分钟实锤!(aa扑克不能用模拟器!辅助透视)外挂透明挂安装(2025已更新)(哔哩哔哩)是一款可以...
5分钟了解!Wepoke助手(... 5分钟了解!Wepoke助手(wePOke)外挂透明挂透视,太嚣张了原来是真的有挂(2023已更新)...
十分钟实锤!(线上德州有后台操... 您好,这款游戏可以开挂的,确实是有挂的,需要了解加微【485275054】很多玩家在这款游戏中打牌都...
域名不用了备案怎么办(如何处理... 域名备案过期的网站怎么处理?域名备案是指将域名和网站的信息注册在国家有关政府机关进行备案,以维护国家...
搬瓦工可以干什么(搬瓦工的功能... 搬瓦工可以干什么?搬瓦工是一款功能强大的虚拟专用服务器(VPS)服务,可以用来进行多种任务的操作。下...
域名信息过户怎么办(如何进行域... 概述域名信息过户是指把域名的所有权从一个人或机构转移到另一个人或机构的过程。该过程需要注意一些步骤和...