0%

找中位数,用两个大根堆来记录按大小排列时中间的两个数

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
class 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();

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
class Solution {
public:
int longestValidParentheses(string s) {
if(s.length()<2)
return 0;
int ret=0;
vector<int> dp(s.length(),0);
for(int i=1;i<s.length();++i)
{
if(s[i]=='(')
continue;
else
{
if(s[i-1]=='(')
{
dp[i]=i>1?(dp[i-2]+2):2;
}
else{
if(i-dp[i-1]-1>=0 && s[i-dp[i-1]-1]=='(')
{
dp[i]=dp[i-1]+2+((i-dp[i-1]-2)>=0?dp[i-dp[i-1]-2]:0);
}
}
}
ret=max(ret, dp[i]);
}
return ret;
}
};

第一步,等分链表

第二步,反转第二个链表

第三步,合并两个链表

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;
}
}
};

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(k==0 || !head)
return head;
int count=0;
ListNode *root = new ListNode(0);
root->next=head;
auto p=root->next, q=root;
while(p)
{
p=p->next;
++count;
}
p=root;
k=k%count;
for(int i=0;i<k && p ; ++i, p=p->next);
while(p && p->next)
{
p=p->next;
q=q->next;
}
p->next=root->next;
root->next=q->next;
q->next=NULL;
return root->next;
}
};

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 a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
int *ret = new int(INT_MIN);
foo(root, ret);
return *ret;
}

int foo(TreeNode* root, int *ret)
{
if(root==NULL)
return 0;
int left=max(foo(root->left, ret), 0);
int right=max(foo(root->right, ret), 0);
*ret = max(left+right+root->val, *ret);
return max(left, right)+root->val;
}
};

按照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
30
class 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;
}

};

挺好的一道排序题

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;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int numSquares(int n) {
if(n<0)
return 0;
vector<int> vec(n+1, INT_MAX);
vec[0]=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j*j<=i;++j)
{
vec[i]=min(vec[i], vec[i-j*j]+1);
}
}
return vec.back();
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> mmap;
for(auto i: strs)
{
auto str = i;
sort(str.begin(),str.end());
mmap[str].push_back(i);
}
vector<vector<string>> ret;
for(auto i: mmap)
{
sort(i.second.begin(),i.second.end());
ret.push_back(i.second);
}
return ret;
}
};

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
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> vec;
foo(s, 0, s.size(), res, vec);
return res;
}

void foo(string s, int beg, int end, vector<vector<string>> &res, vector<string> &vec)
{
if(beg>=end)
{
res.push_back(vec);
return;
}

for(int i=beg; i<end; ++i)
{
if(bar(s, beg, i))
{
vec.push_back(s.substr(beg, i-beg+1));
foo(s, i+1, end, res, vec);
vec.pop_back();
}
}
}

bool bar(string s, int beg, int end)
{
while(beg<=end)
{
if(s[beg]==s[end])
{
++beg;
--end;
}
else
return false;
}
return true;
}
};