关注
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
//(1,1),(2,2),(3,3) 3
//(0,0),(1,1),(1,-1) 2
public class Main {
//坐标点类
static class Point {
int x;
int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
sc.close();
//解析坐标
String[] strs = str.split("\\),");
List<Point> list = new ArrayList<Point>();
for (int i = 0; i < strs.length; i++) {
strs[i] = strs[i].substring(1);
String[] ps = strs[i].split(",");
int x = Integer.parseInt(ps[0]);
if (i == strs.length - 1)
ps[1] = ps[1].substring(0, ps[1].length() - 1);
int y = Integer.parseInt(ps[1]);
Point p = new Point(x, y);
list.add(p);
}
System.out.println(cal(list));
}
//计算
public static int cal(List<Point> list) {
if (list.size() == 0)
return 0;
if (list.size() == 1)
return 1;
int res = 0;
for (int i = 0; i < list.size(); i++) {
//在leetcode上亲测在循环外定义HashMap并在循环内调用map.clear()比直接
//在循环内定义HashMap慢了2ms,内存少用了0.1m
Map<String, Integer> map = new HashMap<String, Integer>();
Point cur = list.get(i);
//共线数
int g = 0;
//共点数
int gd = 1;
//共x数
int gx = 0;
//共y数
int gy = 0;
//共斜率数
int gk = 0;
for (int j = 0; j < list.size(); j++) {
if (i == j)
continue;
Point temp = list.get(j);
int x1 = cur.x - temp.x;
int y1 = cur.y - temp.y;
if (x1 == 0 && y1 == 0) {
gd++;
continue;
}
if (x1 == 0) {
gx++;
continue;
}
if (y1 == 0) {
gy++;
continue;
}
//由于直接算出double类型的斜率之后再进行比较会有误差
//所以使用HashMap存储不同斜率值得数量
int gc = gcd(x1, y1);
x1 /= gc;
y1 /= gc;
String key = x1 + "/" + y1;
if (!map.containsKey(key)) {
map.put(key, 0);
}
int curGk = map.get(key) + 1;
map.put(key, curGk);
gk = Math.max(gk, curGk);
}
g = Math.max(gx, gy);
g = Math.max(g, gk);
res = Math.max(res, g + gd);
}
return res;
}
//求x、y最大公约数
public static int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
}
查看原帖
点赞 2
牛客热帖
更多
正在热议
更多
# 牛客新年AI问运 #
3213次浏览 79人参与
# 刚工作,应该先搞钱or搞成长? #
20842次浏览 159人参与
# 牛客AI体验站 #
15614次浏览 277人参与
# 你觉得第一学历对求职有影响吗? #
229996次浏览 1266人参与
# 如何提高实习转正率? #
85688次浏览 503人参与
# 找工作中的小确幸 #
80402次浏览 448人参与
# 实习在多还是在精 #
82790次浏览 509人参与
# 你觉得技术面多长时间合理? #
168108次浏览 1170人参与
# 牛友的春节生活 #
11891次浏览 229人参与
# 月薪多少能在一线城市生存 #
136420次浏览 898人参与
# 选了这个offer,你有没有后悔? #
738551次浏览 4472人参与
# 备战春招/暑实,现在应该做什么? #
7927次浏览 204人参与
# 从夯到拉,锐评职场mentor #
7760次浏览 113人参与
# 实习到现在,你最困惑的一个问题 #
6945次浏览 169人参与
# 电网笔面经互助 #
59689次浏览 476人参与
# 找工作中的意难平 #
983431次浏览 6424人参与
# 制造业的秋招小结 #
143363次浏览 2089人参与
# 春招什么时候投? #
13241次浏览 209人参与
# 秋招踩过的“雷”,希望你别再踩 #
185697次浏览 1684人参与
# 你有哪些缓解焦虑的方法? #
51164次浏览 906人参与
查看4道真题和解析