149. Max Points on a Line
Tags:
Hard
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm số điểm lớn nhất nằm trên cùng một đường thẳng từ một tập hợp các điểm trên mặt phẳng 2D
Approach
slope (hệ số góc) của dường thẳng đi qua hai điểm(dy, dx) sau khi chia cho GCD của dy và dx Các bước chínht
delta_x. delta_y chuẩn hóa bằng GCD và lưu slope vào hashmapSolution
1function maxPoints(points: number[][]): number {
2 if(points.length <= 2) return points.length;
3
4 function gcd(a: number, b: number): number {
5 return b === 0 ? a : gcd(b, a % b)
6 }
7
8 let max_res = 0;
9 for(let i = 1; i < points.length; i++) {
10 let slopes: Record<string, number> = {};
11 let duplicate = 0;
12 let local_max = 0;
13
14 for(let j = i + 1; j < points.length; j++) {
15 let dx = points[j][0] - points[i][0];
16 let dy = points[j][1] - points[i][1];
17
18 if(dx === 0 && dy === 0) {
19 duplicate++;
20 continue;
21 }
22
23 let g = gcd(dx, dy)
24 dx /= g;
25 dy /= g;
26
27 if(dx < 0) {
28 dx = -dx;
29 dy = -dy;
30 } else if (dx === 0) {
31 dy = 1;
32 } else if (dy === 0) {
33 dx = 1;
34 }
35
36 const key = `${dx},${dy}`;
37 slopes[key] = (slopes[key] || 0) + 1;
38 local_max = Math.max(local_max, slopes[key]);
39 }
40
41 max_res = Math.max(max_res, local_max, duplicate + 1)
42 }
43
44 return max_res
45};