2022-08-17-nvidia实习
逐个插入区间,合并区间,最后返回无重复的一个或多个区间
#include #include using namespace std; #define pii pair class MergeIntervals{ private: vector intervals; vector::iterator mergeNext(vector::iterator p){ while(next(p)!=intervals.end()&&p->second>=next(p)->first){ p->second=next(p).second; intervals.erase(p+1); } return p; } public: void test(pii v){ auto lb = lower_bound(internals.begin(),intervals.end(),v); // >= v.first // merge last auto preInterval = prev(lb); if(preInterval && preInterval.second>=v.second){ return; } // insert new pair to next lb.insert(v); // lb v ... auto p = lb; p = mergeNext(p); // merge lb and its next: lb.second >= v.first if(p==intervals.end()||next(p)==intervals.end()) // no next or p is the last return; p=p+1; mergeNext(p); // merge v and its next: lb.second < v.first return; } vector callHistory(){ return intervals; } }; int main() { return 0; }
感觉数据结构用错了,vector插入太慢了,以前(好像是去年下半年)做过一个leetcode每日一题也是这个
找不到了
当时记录4种语言语法就花了许久功夫,上面是java的(应该只有第一部分)
// 后来发现一大堆错误,除了大致的大致的思路没错,其他全是错的,前面后面全错了!!! // 面试官完全没发现,还给予了一定的肯定。 // 写了个测试用例,自己调出来了,可能还有错 // 其实还是O(n*n)的,完全可以先把n个区间全存起来最后再排序去重... #include <iostream> #include <vector> using namespace std; #define pii pair<int, int> class MergeIntervals { private: vector<pii> intervals; vector<pii>::iterator mergeNext(vector<pii>::iterator p) { while (next(p) != intervals.end() && p->second >= next(p)->first) { p->second = max(p->second, next(p)->second); intervals.erase(p + 1); } return p; } public: void test(pii v) { if (intervals.size() == 0) { intervals.push_back(v); return; } auto lb = lower_bound(intervals.begin(), intervals.end(), v); // >= v.first // merge last if (lb != intervals.begin()) { auto preInterval = prev(lb); if (preInterval->second >= v.second) return; else if(preInterval->second>=v.first){ preInterval->second = max(preInterval->second, v.second); mergeNext(preInterval); return; } } // insert new pair to next vector<pii>::iterator w; if (lb == intervals.end()) { w = intervals.insert(lb, v); // cout << w->first << ", " << w->second << "\n"; return; } else{ w = intervals.insert(lb, v); // w(v) lb ... // cout << w->first << ", " << w->second << "\n"; } auto p = w; p = mergeNext(p); // merge w and its next: w.second >= lb.first // if (p == intervals.end() || next(p) == intervals.end()) // no next or p is the last // return; // p = p + 1; // mergeNext(p); // merge w and its next: w.second < lb.first return; } vector<pii> callHistory() { return intervals; } }; int main() { MergeIntervals m; pii p = make_pair<int, int>(1, 10); m.test(pair<int, int>(1, 10)); m.test(make_pair(10, 15)); m.test(make_pair(17, 20)); m.test(make_pair(13, 30)); m.test(make_pair(40, 50)); m.test(make_pair(27, 40)); vector<pii> h = m.callHistory(); for (auto i : h) { cout << i.first << ", " << i.second << "\n"; } return 0; }#NVIDIA##实习##面试#