开始无脑匹配结果超时：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 |
class
Solution {public: int
maxPoints(vector<Point> &points) { int
ans = 0; for
(int
i = 0; i < points.size(); ++i) { for
(int
j = i + 1; j < points.size(); ++j) { int
num = 1; for
(int
k = 0; k < points.size(); ++k) if
(isOnLine(points[i], points[j], points[k])) num++; if
(num > ans) ans = num; } } if
(ans == 0 && points.size() == 1) ans = 1; return
ans; } bool
isOnLine(const
Point &p1, const
Point &p2, const
Point &p) { if
((p.y - p2.y) * (p.x - p1.x) == (p.y - p1.y) * (p.x - p2.x)) return
true; return
false; }}; |
统计同一斜率的直线数量：
|
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
maxPoints(vector<Point> &points) { int
ans = 0; unordered_map<float, int> kmap; for
(int
i = 0; i < points.size(); ++i) { kmap.clear(); int
duplicate = 1; for
(int
j = 0; j < points.size(); ++j ) { if
(j == i) continue; if
(points[i].x == points[j].x && points[i].y == points[j].y) { ++duplicate; continue; } float
k = (points[i].x == points[j].x) ? INT_MAX : (float)(points[i].y - points[j].y) / (points[i].x - points[j].x); kmap[k]++; } unordered_map<float, int>::iterator it = kmap.begin(); while
(it != kmap.end()) { if
(it->second + duplicate > ans) ans = it->second + duplicate; ++it; } if
(ans < duplicate) ans = duplicate; } return
ans; }}; |
|
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
46 |
class
Solution {public: ListNode *sortList(ListNode *head) { if
(head == NULL || head->next == NULL) return
head; ListNode *slow = head, *fast = head; while
(fast->next != NULL && fast->next->next != NULL) { fast = fast->next->next; slow = slow->next; } fast = slow; slow = slow->next; fast->next = NULL; fast = sortList(head); slow = sortList(slow); return
merge(fast, slow); } ListNode *merge(ListNode *first, ListNode *second) { if
(first == NULL) return
second; if
(second == NULL) return
first; ListNode *ret, *p; if
(first->val < second->val) { ret = first; first = first->next; } else
{ ret = second; second = second->next; } p = ret; while
(first != NULL && second != NULL) { if
(first->val <second->val) { p->next = first; first = first->next; } else
{ p->next = second; second = second->next; } p = p->next; } if
(first != NULL) p->next = first; else
if (second != NULL) p->next = second; return
ret; }}; |
原文：http://www.cnblogs.com/fripside/p/3769919.html