[LintCode] 최대 몇 개의 점이 한 직선에 있습니까?
5311 단어 code
1 /**
2 * Definition for a point.
3 * struct Point {
4 * int x;
5 * int y;
6 * Point() : x(0), y(0) {}
7 * Point(int a, int b) : x(a), y(b) {}
8 * };
9 */
10 class Solution {
11 public:
12 /**
13 * @param points an array of point
14 * @return an integer
15 */
16 int maxPoints(vector<Point>& points) {
17 // Write your code here
18 unordered_map<float, int> slopes;
19 int maxp = 0, n = points.size();
20 for (int i = 0; i < n; i++) {
21 slopes.clear();
22 int duplicate = 1;
23 for (int j = i + 1; j < n; j++) {
24 if (points[i].x == points[j].x && points[i].y == points[j].y) {
25 duplicate++;
26 continue;
27 }
28 float slope = (points[i].x == points[j].x) ? INT_MAX:
29 (float)(points[i].y - points[j].y) / (points[i].x - points[j].x);
30 slopes[slope]++;
31 }
32 maxp = max(maxp, duplicate);
33 for (auto slope : slopes)
34 if (slope.second + duplicate > maxp)
35 maxp = slope.second + duplicate;
36 }
37 return maxp;
38 }
39 };
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
소스 코드가 포함된 Python 프로젝트텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.