Archive for April 30th, 2013
Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4]
,
the contiguous subarray [4,−1,2,1]
has the largest sum = 6
.
class Solution { public: int maxSubArray(int A[], int n) { // Start typing your C/C++ solution below // DO NOT write int main() function int maxSum = INT_MIN; int sum = 0; for(int i = 0; i < n; i++){ if(sum + A[i] < 0){ sum = 0; maxSum = max(maxSum, A[i]); }else{ sum = sum + A[i]; maxSum = max(maxSum, sum); } } return maxSum; } };
Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9]
, insert and merge [2,5]
in as [1,5],[6,9]
.
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16]
, insert and merge [4,9]
in as [1,2],[3,10],[12,16]
.
This is because the new interval [4,9]
overlaps with [3,5],[6,7],[8,10]
.
/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { public: bool hasOverlap(Interval &a, Interval &b){ if(a.start > b.end || b.start > a.end){ return false; } return true; } vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<Interval> ret; ret.clear(); int size = intervals.size(); bool flag_addNew = false; for(int i = 0; i < size; i++){ if(!flag_addNew && hasOverlap(intervals[i], newInterval)){ newInterval.start = min(newInterval.start, intervals[i].start); newInterval.end = max(newInterval.end, intervals[i].end); }else{ if(flag_addNew == false && (newInterval.start < intervals[i].start)){ ret.push_back(newInterval); flag_addNew = true; } ret.push_back(intervals[i]); } } if(flag_addNew == false){ ret.push_back(newInterval); } return ret; } };
Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18]
,
return [1,6],[8,10],[15,18]
.
/** * 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 compare(const Interval &a, const Interval &b){ return a.start < b.start; } class Solution { public: vector<Interval> merge(vector<Interval> &intervals) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<Interval> ret; ret.clear(); int size = intervals.size(); if(size == 0) return ret; sort(intervals.begin(), intervals.end(), mycompare); Interval pre = intervals[0]; for(int i = 1; i <= size; i++){ if(i == size){ ret.push_back(pre); break; } Interval cur = intervals[i]; if(pre.end >= cur.start){ pre.end = max(cur.end, pre.end);//error: forget max }else{ ret.push_back(pre); pre = cur; } } return ret; } };