| 日期 |
2022年9月14日 |
| 是否独立完成 |
否 |
| 涉及算法 |
暴力枚举、几何 |
题面
LeetCode 149. 直线上最多的点数
给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
示例 1：
1
2
| 输入：points = [[1,1],[2,2],[3,3]]
输出：3
|
示例 2：
1
2
| 输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4
|
题解
暴力枚举
对于点a,b,c，如果其中任意两点构成的直线斜率相同，则三点共线。我们可以枚举所有的点对，用哈希表记录斜率，则可以判断有多少个点出现在同一条直线上。
本题难点在于计算斜率需要用到除法，而浮点数的除法是存在误差的。为了避免这个误差，一共有两种思路：
- 利用乘法来避免除法（把两个斜率相等的表达式用对角相乘法则化为两个乘法表达式相等）。
- 用字符串来哈希。
本题我选择用第二个思路解。在计算斜率时通过最大公约数把分式约分为最间，保证相同斜率的直线能全部哈希在一起。
代码：
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
| class Solution {
private:
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public:
int maxPoints(vector<vector<int>>& points) {
int res = 0;
for (int i = 0; i < points.size(); i++) {
unordered_map<string, int> map;
int mx = 0;
for (int j = i + 1; j < points.size(); j++) {
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
int a = x1 - x2;
int b = y1 - y2;
int g = gcd(a, b);
string key = to_string(a / g) + "_" + to_string(b / g);
map[key]++;
mx = max(mx, map[key]);
}
res = max(res, mx + 1);
}
return res;
}
};
|