网站怎样制作吸引人,可以查各种资料的app,外贸信托,中铁建设集团招聘700人目录
1851. 包含每个查询的最小区间
题目描述#xff1a;
实现代码与解析#xff1a;
排序 哈希
原理思路#xff1a; 1851. 包含每个查询的最小区间
题目描述#xff1a; 给你一个二维整数数组 intervals #xff0c;其中 intervals[i] [lefti, righti] 表示第 i…目录
1851. 包含每个查询的最小区间
题目描述
实现代码与解析
排序 哈希
原理思路 1851. 包含每个查询的最小区间
题目描述 给你一个二维整数数组 intervals 其中 intervals[i] [lefti, righti] 表示第 i 个区间开始于 lefti 、结束于 righti包含两侧取值闭区间。区间的 长度 定义为区间中包含的整数数目更正式地表达是 righti - lefti 1 。
再给你一个整数数组 queries 。第 j 个查询的答案是满足 lefti queries[j] righti 的 长度最小区间 i 的长度 。如果不存在这样的区间那么答案是 -1 。
以数组形式返回对应查询的所有答案。
示例 1
输入intervals [[1,4],[2,4],[3,6],[4,4]], queries [2,3,4,5]
输出[3,3,1,4]
解释查询处理如下
- Query 2 区间 [2,4] 是包含 2 的最小区间答案为 4 - 2 1 3 。
- Query 3 区间 [2,4] 是包含 3 的最小区间答案为 4 - 2 1 3 。
- Query 4 区间 [4,4] 是包含 4 的最小区间答案为 4 - 4 1 1 。
- Query 5 区间 [3,6] 是包含 5 的最小区间答案为 6 - 3 1 4 。示例 2
输入intervals [[2,3],[2,5],[1,8],[20,25]], queries [2,19,5,22]
输出[2,-1,4,6]
解释查询处理如下
- Query 2 区间 [2,3] 是包含 2 的最小区间答案为 3 - 2 1 2 。
- Query 19不存在包含 19 的区间答案为 -1 。
- Query 5 区间 [2,5] 是包含 5 的最小区间答案为 5 - 2 1 4 。
- Query 22区间 [20,25] 是包含 22 的最小区间答案为 25 - 20 1 6 。提示
1 intervals.length 1051 queries.length 105intervals[i].length 21 lefti righti 1071 queries[j] 107
实现代码与解析
排序 哈希
class Solution {
public:vectorint minInterval(vectorvectorint itv, vectorint qr) {vectorint res(qr.size(), -1);setpairint, int st;for (int i 0; i qr.size(); i) st.insert({qr[i], i}); // 所求数字编号// 区间从小到大排 lambda表达式sort(itv.begin(), itv.end(), [](const auto a, const auto b){return a[1] - a[0] b[1] - b[0];});for (int i 0; i itv.size(); i){auto it st.lower_bound({itv[i][0], - 1}); //第一个大于等于左边界//找出左边界和右边界之间包含的查询for (it; it ! st.end() (it-first itv[i][1] || it-first itv[i][1]);){res[it-second] itv[i][1] - itv[i][0] 1; //查询编号得到结果st.erase(it);// 删除已经得到结果的que.防止下次覆盖改变结果}}return res;}
};
原理思路 首先按照区间大小对itv进行排序然后利用setpairint ,int对qr进行排序同时记录其编号并且创建一个res数组存放结果初始化为 -1 。 遍历itv在set中找出第一个大于等于itv[i][0]的位置左端点然后开始遍历set中储存的询问找出小于等于 itv[i][0](右端点的询问根据记录的编号位置给对应位置的res赋值位区间长度同时删除set.erase已经得到结果的询问最终得到所有结果。 注意一定不要把遍历set时的it放入for()中而是放入erase中。 lower_bound(x) 是用来寻找第一个大于等于x的位置。 upper_bound(x) 是用来寻找第一个大于x的位置。
不得不说在写仿函数的时候 lambda 写起来确实方便很多学到了。 一开始我写的丑陋代码大家可以不用看我自己记录一下就过了4分之3把qr排序来优化一下应该也可以过。
class Solution {
public:class mycomparison {public:bool operator()(const pairint, int a, const pairint, int b) {return a.first b.first;}};vectorint minInterval(vectorvectorint intervals, vectorint queries) {vectorint qr(10000010, -1); // 用于预处理vectorint res; // 放结果priority_queuepairint ,int, vectorpairint, int, mycomparison que; // pair区间长度编号小堆区间长度排序for (int i 0; i intervals.size(); i){que.push({intervals[i][1] - intervals[i][0] 1, i}); // pair长度编号}while(que.size()){auto t que.top();int len t.first; // 区间长度int idx t.second; // 此区间编号int r intervals[idx][1]; // 右端点int l intervals[idx][0]; // 左端点for (int i l; i r; i){if (qr[i] -1){qr[i] len;}}que.pop();}for (int i 0; i queries.size(); i){res.push_back(qr[queries[i]]);}return res;}
};
