Skip to content

Commit b0e85e3

Browse files
ayleiaylei
committed
solve #149
1 parent 4a1ae2e commit b0e85e3

File tree

6 files changed

+172
-2
lines changed

6 files changed

+172
-2
lines changed

‎src/lib.rs

+1
Original file line numberDiff line numberDiff line change
@@ -143,3 +143,4 @@ mod n0145_binary_tree_postorder_traversal;
143143
mod n0146_lru_cache;
144144
mod n0147_insertion_sort_list;
145145
mod n0148_sort_list;
146+
mod n0149_max_points_on_a_line;

‎src/main.rs

+3
Original file line numberDiff line numberDiff line change
@@ -67,6 +67,9 @@ fn parse_extra_use(code: &str) -> String {
6767
if code.contains("pub struct TreeNode") {
6868
extra_use_line.push_str("\nuse super::util::tree::{TreeNode, to_tree};")
6969
}
70+
if code.contains("pub struct Point") {
71+
extra_use_line.push_str("\nuse super::util::point::Point;")
72+
}
7073
extra_use_line
7174
}
7275

‎src/n0149_max_points_on_a_line.rs

+138
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,138 @@
1+
/**
2+
* [149] Max Points on a Line
3+
*
4+
* Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
5+
*
6+
* Example 1:
7+
*
8+
*
9+
* Input: [[1,1],[2,2],[3,3]]
10+
* Output: 3
11+
* Explanation:
12+
* ^
13+
* |
14+
* | o
15+
* | o
16+
* | o
17+
* +------------->
18+
* 0 1 2 3 4
19+
*
20+
*
21+
* Example 2:
22+
*
23+
*
24+
* Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
25+
* Output: 4
26+
* Explanation:
27+
* ^
28+
* |
29+
* | o
30+
* | o o
31+
* | o
32+
* | o o
33+
* +------------------->
34+
* 0 1 2 3 4 5 6
35+
*
36+
*
37+
*/
38+
pub struct Solution {}
39+
use super::util::point::Point;
40+
41+
/*
42+
要回顾下高中数学：已知两点, 求解一般式:
43+
44+
* Ax + By + C = 0
45+
* A = y2 - y1, B = x1 - x2, C = x2y1 - x1y2
46+
47+
有这个知识之后，化为一般式，做三层遍历就行，再加上一个 HashSet，避免对同一直线上点的重复计算，时间复杂度可以是 O(N^2)
48+
49+
有两个坑要注意避免：
50+
51+
* 给的 case 会导致 i32 溢出，这里直接用了 i64 表示
52+
* 给的 case 里有相同的点，直接处理相同点的话会导致最坏情况复杂度到 O(N^3)，因此要先做一次转化，归并相同的点
53+
54+
用 Rust 实现有另一点注意的，给的 Point 没有实现 Hash Trait，要自己转化一下
55+
*/
56+
// straight-line expression: Ax + By + C = 0
57+
// A = y2 - y1, B = x1 - x2, C = x2y1 - x1y2
58+
#[derive(PartialEq,Hash,Eq,Debug)]
59+
struct Line(i64, i64, i64);
60+
61+
impl Line {
62+
// Assumes that there is no same point
63+
fn new(p1: &Point, p2: &Point) -> Self {
64+
let x1 = p1.x as i64;
65+
let x2 = p2.x as i64;
66+
let y1 = p1.y as i64;
67+
let y2 = p2.y as i64;
68+
Line(y2-y1, x1-x2, x2*y1 - x1*y2)
69+
}
70+
fn contains(&self, p: &Point) -> bool {
71+
self.0 * p.x as i64 + self.1 * p.y as i64 + self.2 == 0_i64
72+
}
73+
}
74+
75+
use std::collections::HashSet;
76+
use std::collections::HashMap;
77+
impl Solution {
78+
pub fn max_points(points: Vec<Point>) -> i32 {
79+
// fold same point, record the point count
80+
let points: Vec<(Point, i32)> = points.into_iter()
81+
.fold(HashMap::new(), |mut map, v| {
82+
*map.entry((v.x, v.y)).or_insert(0) += 1; map
83+
})
84+
.into_iter()
85+
.map(|(k,v)| { (Point::new(k.0, k.1), v) }) // Point did not implement Hash trait
86+
.collect();
87+
88+
// any two points in a straight-line, return quickly
89+
if points.len() < 3 {
90+
return points.into_iter().fold(0, |acc, v| { acc + v.1 });
91+
}
92+
let mut max = 2;
93+
let mut set: HashSet<Line> = HashSet::new();
94+
for i in 0..(points.len()-1) {
95+
for j in i+1..points.len() {
96+
let line = Line::new(&points[i].0, &points[j].0);
97+
if set.contains(&line) {
98+
continue;
99+
}
100+
let mut curr = points[i].1 + points[j].1;
101+
for k in j+1..points.len() {
102+
if line.contains(&points[k].0) {
103+
curr += points[k].1;
104+
}
105+
}
106+
max = i32::max(max, curr);
107+
}
108+
}
109+
max
110+
}
111+
}
112+
113+
// submission codes end
114+
115+
#[cfg(test)]
116+
mod tests {
117+
use super::*;
118+
119+
#[test]
120+
fn test_149() {
121+
assert_eq!(
122+
Solution::max_points(vec![point![1,1],point![2,2],point![3,3]]),
123+
3);
124+
assert_eq!(
125+
Solution::max_points(vec![point![1,1],point![3,2],point![5,3],point![4,1],point![2,3],point![1,4]]),
126+
4);
127+
assert_eq!(
128+
Solution::max_points(vec![point![0,0],point![1,65536],point![65536,0]]),
129+
2);
130+
assert_eq!(
131+
Solution::max_points(vec![point![1,1],point![1,1],point![1,1]]),
132+
3);
133+
assert_eq!(
134+
Solution::max_points(vec![point![0,9],point![138,429],point![115,359],point![115,359],point![-30,-102],point![230,709],point![-150,-686],point![-135,-613],point![-60,-248],point![-161,-481],point![207,639],point![23,79],point![-230,-691],point![-115,-341],point![92,289],point![60,336],point![-105,-467],point![135,701],point![-90,-394],point![-184,-551],point![150,774]]),
135+
12
136+
)
137+
}
138+
}

‎src/util/mod.rs

+3-1
Original file line numberDiff line numberDiff line change
@@ -3,4 +3,6 @@ pub mod linked_list;
33
#[macro_use]
44
pub mod vec_string;
55
#[macro_use]
6-
pub mod tree;
6+
pub mod tree;
7+
#[macro_use]
8+
pub mod point;

‎src/util/point.rs

+26
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
#[derive(Debug, PartialEq, Eq)]
2+
pub struct Point {
3+
pub x: i32,
4+
pub y: i32,
5+
}
6+
7+
impl Point {
8+
#[inline]
9+
pub fn new(x: i32, y: i32) -> Self {
10+
Point {
11+
x,
12+
y
13+
}
14+
}
15+
}
16+
17+
#[macro_export]
18+
macro_rules! point {
19+
($($e:expr),*) => {
20+
{
21+
let vec = vec![$($e.to_owned()), *];
22+
Point::new(vec[0], vec[1])
23+
}
24+
};
25+
($($e:expr,)*) => (point![$($x),*])
26+
}

‎src/util/vec_string.rs

+1-1
Original file line numberDiff line numberDiff line change
@@ -2,4 +2,4 @@
22
macro_rules! vec_string {
33
($($e:expr),*) => {vec![$($e.to_owned()), *]};
44
($($e:expr,)*) => {vec![$($e.to_owned()), *]};
5-
}
5+
}

0 commit comments

Comments
 (0)