首页 > 代码库 > 6-5日
6-5日
Max Points on a Line
开始无脑匹配结果超时:
+ View Code?
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 ; } }; |
统计同一斜率的直线数量:
+ View Code?
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; } }; |
Sort List
+ View Code?
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; } }; |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。