关注
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
相关推荐
点赞 评论 收藏
分享
牛客热帖
更多
- 1... 工作半年后更确定:我们依然不欠优绩主义什么6712
- 2... 我建了一个分享实习业务的仓库,欢迎大家贡献哦3001
- 3... 岁末论道:谁才是牛客 2025 最强修仙者?2750
- 4... #牛客2025仙途报告#居然是五颗星2499
- 5... 腾讯 微信支付一面面经2288
- 6... 【2025-年终总结】25届毕业生果果牛这一年~2157
- 7... 仙途报告1911
- 8... 一个程序员的自救书|从酒吧陪玩DM到上岸大厂1814
- 9... 28第二次面试1525
- 10... 在当下这个社会,在人生这个无常的时代,我真心希望你和各位牛友开心1457
正在热议
更多
# 牛客2025仙途报告 #
11423次浏览 223人参与
# 实习要如何选择和准备? #
129619次浏览 1494人参与
# 2025年终总结 #
192094次浏览 3224人参与
# 上班后和你想的一样吗? #
95053次浏览 701人参与
# 你有哪些缓解焦虑的方法? #
44354次浏览 867人参与
# 找工作,行业重要还是岗位重要? #
87033次浏览 1739人参与
# 今年你最想重开的一场面试是? #
11033次浏览 121人参与
# 元旦假期你打算怎么过 #
606次浏览 19人参与
# 你面试体验感最差/最好的公司 #
27825次浏览 461人参与
# 礼物开箱Plog #
2953次浏览 100人参与
# 一人说一个提前实习的好处 #
20571次浏览 289人参与
# 秋招落幕,你是He or Be #
21358次浏览 363人参与
# 我们是不是被“优绩主义”绑架了? #
1415次浏览 56人参与
# 没有合适的工作,你会先找个干着,还是考公考研 #
149189次浏览 1241人参与
# 机械人晒出你的简历 #
148007次浏览 885人参与
# 工作中听到最受打击的一句话 #
11909次浏览 170人参与
# 重来一次,你会对开始求职的自己说 #
9601次浏览 235人参与
# 实习没事做是福还是祸? #
22825次浏览 332人参与
# 工作两年,想和老板谈涨薪怎么说 #
39101次浏览 176人参与
# 实习的内耗时刻 #
212693次浏览 1580人参与
查看14道真题和解析