[leetcode]352. Data Stream as Disjoint Intervals

数据流合并成区间,每次新来一个数,表示成一个区间,然后在已经保存的区间中进行二分查找,最后结果有3种,插入头部,尾部,中间,插入头部,不管插入哪里,都判断一下左边和右边是否能和当前的数字接起来,我这样提交了,发现错了,想到之前考虑要不要判重,我感觉是这个问题,然后就是在二分查找的时候,判断一下左右区间是否包含当前的值,包含就直接返回。

 /**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
bool cmp(Interval a, Interval b) {
if(a.start == b.start) return a.end < b.end;
return a.start < b.start;
}
class SummaryRanges {
public:
/** Initialize your data structure here. */ vector<Interval> v;
SummaryRanges() {
v.clear();
} void addNum(int val) {
//cout << val << " " << v.size() << endl;
Interval d(val, val);
if(v.size() == ) v.push_back(d);
else {
int t = lower_bound(v.begin(), v.end(), d, cmp) - v.begin();
//cout << val << " " << t << endl;
if(t == ) {
if(val == v[].start) return;
if(v[].start - == val) {
v[].start = val;
} else {
v.insert(v.begin() + t, d);
}
} else if(t == v.size()) {
if(v[t - ].end >= val) return;
if(v[t - ].end + == val) {
v[t - ].end = val;
} else {
v.push_back(d);
}
} else {
if(v[t - ].start == val || v[t - ].end >= val || v[t].start == val) return;
if(v[t - ].end + == v[t].start) {
v[t - ].end = v[t].end;
v.erase(v.begin() + t);
} else if(v[t - ].end + == val) {
v[t - ].end = val;
} else if(v[t].start - == val) {
v[t].start = val;
} else {
v.insert(v.begin() + t, d);
}
} }
} vector<Interval> getIntervals() {
return v;
}
}; /**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();
* obj.addNum(val);
* vector<Interval> param_2 = obj.getIntervals();
*/
上一篇:JVM-操作码助记符


下一篇:使用Entity Framework通过code first方式创建数据库和数据表