找中位数,用两个大根堆来记录按大小排列时中间的两个数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31class MedianFinder {
public:
// Adds a number into the data structure.
void addNum(int num) {
small.push(num);
big.push(-small.top());
small.pop();
if(small.size()<big.size())
{
small.push(-big.top());
big.pop();
}
}
// Returns the median of current data stream
double findMedian() {
if(big.size()==small.size())
return small.top()-(big.top()+small.top())/2.0;
else
return small.top();
}
private:
priority_queue<int> small, big;
};
// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();
LeetCode: Longest Valid Parentheses
1 | class Solution { |
LeetCode: Reorder List
第一步,等分链表
第二步,反转第二个链表
第三步,合并两个链表1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if(!head || !head->next)
return;
auto p1=head;
auto p2=head->next;
while(p2 && p2->next)
{
p1=p1->next;
p2=p2->next->next;
}
auto h2=p1->next;
p1->next = NULL;
p1=h2->next;
h2->next=NULL;
while(p1)
{
p2=p1;
p1=p1->next;
p2->next=h2;
h2=p2;
}
p1=head;
while(h2)
{
p2=h2->next;
h2->next=p1->next;
p1->next=h2;
p1=h2->next;
h2=p2;
}
}
};
LeetCode: Rotate List
1 | /** |
LeetCode: Binary Tree Maximum Path Sum
1 | /** |
LeetCode: Course Schedule
按照hints,用dfs来判断有没有环1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
for(auto i: prerequisites)
{
graph[i.second].push_back(i.first);
}
vector<bool> visit(numCourses, false);
for(int i=0;i<numCourses; ++i)
if(!dfs(graph, i, visit))
return false;
return true;
}
bool dfs(vector<vector<int>> &graph, int cur, vector<bool> &visit)
{
if(visit[cur])
return false;
visit[cur]=true;
for(auto i: graph[cur])
{
if(!dfs(graph, i, visit))
return false;
}
visit[cur]=false;
return true;
}
};
LeetCode: Merge Intervals
挺好的一道排序题1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27/**
* 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:
vector<Interval> merge(vector<Interval>& intervals) {
vector<Interval> ret;
sort(intervals.begin(), intervals.end(), [](Interval &lhs, Interval &rhs){
return lhs.start<rhs.start;
});
for(auto &i: intervals)
{
if(ret.empty() ||
ret.back().end < i.start)
ret.push_back(i);
else
ret.back().end = ret.back().end>i.end ? ret.back().end : i.end;
}
return ret;
}
};
LeetCode: Perfect Squares
1 | class Solution { |
LeetCode: Group Anagrams
1 | class Solution { |
LeetCode: Palindrome Partitioning
1 | class Solution { |