刷q币网站建设,长治网站建设推广,wordpress云标签,网站建设应注重实用性作者推荐
利用广度优先或模拟解决米诺骨牌
本文涉及的基础知识点
二分查找算法合集
题目
一个酒店里有 n 个房间#xff0c;这些房间用二维整数数组 rooms 表示#xff0c;其中 rooms[i] [roomIdi, sizei] 表示有一个房间号为 roomIdi 的房间且它的面积为 sizei 。每一…作者推荐
利用广度优先或模拟解决米诺骨牌
本文涉及的基础知识点
二分查找算法合集
题目
一个酒店里有 n 个房间这些房间用二维整数数组 rooms 表示其中 rooms[i] [roomIdi, sizei] 表示有一个房间号为 roomIdi 的房间且它的面积为 sizei 。每一个房间号 roomIdi 保证是 独一无二 的。 同时给你 k 个查询用二维数组 queries 表示其中 queries[j] [preferredj, minSizej] 。第 j 个查询的答案是满足如下条件的房间 id 房间的面积 至少 为 minSizej 且 abs(id - preferredj) 的值 最小 其中 abs(x) 是 x 的绝对值。 如果差的绝对值有 相等 的选择 最小 的 id 。如果 没有满足条件的房间 答案为 -1 。 请你返回长度为 k 的数组 answer 其中 answer[j] 为第 j 个查询的结果。 示例 1 输入rooms [[2,2],[1,2],[3,2]], queries [[3,1],[3,3],[5,2]] 输出[3,-1,3] 解释查询的答案如下 查询 [3,1] 房间 3 的面积为 2 大于等于 1 且号码是最接近 3 的为 abs(3 - 3) 0 所以答案为 3 。 查询 [3,3] 没有房间的面积至少为 3 所以答案为 -1 。 查询 [5,2] 房间 3 的面积为 2 大于等于 2 且号码是最接近 5 的为 abs(3 - 5) 2 所以答案为 3 。 示例 2 输入rooms [[1,4],[2,3],[3,5],[4,1],[5,2]], queries [[2,3],[2,4],[2,5]] 输出[2,1,3] 解释查询的答案如下 查询 [2,3] 房间 2 的面积为 3 大于等于 3 且号码是最接近的为 abs(2 - 2) 0 所以答案为 2 。 查询 [2,4] 房间 1 和 3 的面积都至少为 4 答案为 1 因为它房间编号更小。 查询 [2,5] 房间 3 是唯一面积大于等于 5 的所以答案为 3 。 参数范围 n rooms.length 1 n 105 k queries.length 1 k 104 1 roomIdi, preferredj 107 1 sizei, minSizej 107
分析
时间复杂
O(nlogn)。
步骤
一预处理。房间按面积排序从大到小。对查询的索引排序面积大的在前。 二枚举每个查询将房间面积大于等于当前查询面积的房间号加到setRoomNO中。在setRoomNO中找第一个大于等于preferredj和小于preferredj的房间号。比较看那个更接近preferredj。
代码
核心代码
class Solution {
public:vectorint closestRoom(vectorvectorint rooms, vectorvectorint queries) {vectorint indexs(queries.size());iota(indexs.begin(), indexs.end(), 0);sort(indexs.begin(), indexs.end(), [queries](const int i1, const int i2) {return queries[i1][1] queries[i2][1]; });sort(rooms.begin(), rooms.end(), [](const auto v1, const auto v2) {return v1[1] v2[1]; });int indexRoom 0;setint setRoomNO;vectorint vRet(queries.size(),-1);for (const auto i : indexs){while ((indexRoom rooms.size()) (rooms[indexRoom][1] queries[i][1])){setRoomNO.emplace(rooms[indexRoom][0]);indexRoom;}auto it setRoomNO.lower_bound(queries[i][0]);if ((setRoomNO.end() it)(setRoomNO.begin() it)){continue;}else if (setRoomNO.end() it){vRet[i] *std::prev(it);}else if (setRoomNO.begin() it){vRet[i] *it;}else{vRet[i] (*it - queries[i][0] queries[i][0] - *std::prev(it)) ? *std::prev(it) : *it; }}return vRet;}
};测试用例
template void Assert(const T t1, const T t2) { assert(t1 t2); }
template void Assert(const vector v1, const vector v2) { if (v1.size() ! v2.size()) { assert(false); return; } for (int i 0; i v1.size(); i) { Assert(v1[i], v2[i]); } }
int main() { vectorvector rooms, queries; vector res; { rooms { {2,2},{1,2},{3,2} }; queries { {3,1},{3,3},{5,2} }; Solution slu; res slu.closestRoom(rooms, queries); Assert(res, vector{3, -1, 3}); } { rooms { {1,4},{2,3},{3,5},{4,1},{5,2} }; queries { {2,3},{2,4},{2,5} }; Solution slu; res slu.closestRoom(rooms, queries); Assert(res, vector{2,1, 3}); } { rooms { {2,2},{1,2},{3,2} }; queries { {3,1},{3,3},{5,2} }; Solution slu; res slu.closestRoom(rooms, queries); Assert(res, vector{3, -1, 3}); }
//CConsole::Out(res);}
小的优化代码简洁增加可理解性方便排除
旧代码17行
auto it setRoomNO.lower_bound(queries[i][0]);if ((setRoomNO.end() it)(setRoomNO.begin() it)){continue;}else if (setRoomNO.end() it){vRet[i] *std::prev(it);}else if (setRoomNO.begin() it){vRet[i] *it;}else{vRet[i] (*it - queries[i][0] queries[i][0] - *std::prev(it)) ? *std::prev(it) : *it; }新代码12行
std::mapint, int mAbsToRoomNO;auto it setRoomNO.lower_bound(queries[i][0]);if (setRoomNO.end() ! it){mAbsToRoomNO[*it - queries[i][0]] *it;}if (setRoomNO.begin() ! it){const auto itPre std::prev(it);mAbsToRoomNO[queries[i][0]- *itPre] *itPre;}vRet[i] (mAbsToRoomNO.size()) ? mAbsToRoomNO.begin()-second : -1;2023年3月旧代码
class Solution { public: vector closestRoom(vectorvector rooms, vectorvector queries) { vector indexs; for (int i 0; i queries.size(); i) { indexs.push_back(i); } auto SortFun [](const vector v1, const vector v2) { return v1[1] v2[1]; }; std::sort(rooms.begin(), rooms.end(), SortFun); std::sort(indexs.begin(), indexs.end(), [queries](const int i1, const int i2) { return queries[i1][1] queries[i2][1]; }); std::set setRoomNO; int j rooms.size() - 1; vector vRet(queries.size()); for (int i1 queries.size() - 1; i1 0; i1–) { const int i indexs[i1]; const auto vq queries[i]; while ((j 0 ) (rooms[j][1] vq[1])) { setRoomNO.emplace(rooms[j][0]); j–; } auto it setRoomNO.lower_bound(vq[0]); std::set setSelRoomNO; if (setRoomNO.end() ! it) { setSelRoomNO.insert(it); } if (setRoomNO.begin() ! it) { setSelRoomNO.insert((–it)); } if (0 setSelRoomNO.size()) { vRet[i] -1; } else if (1 setSelRoomNO.size()) { vRet[i] *setSelRoomNO.begin(); } else if (2 setSelRoomNO.size()) { bool bPre abs(vq[0] - *setSelRoomNO.begin()) abs(vq[0] - *setSelRoomNO.rbegin()); vRet[i] bPre ? *setSelRoomNO.begin() : *setSelRoomNO.rbegin() ; } } return vRet; } };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境
VS2022 C17
