关注
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
相关推荐
迷茫的大四🐶:有钱卷啥,回去找个轻松点的享受生活不香吗
点赞 评论 收藏
分享
06-23 12:08
广州大学 硬件测试 小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享

点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 你遇到最难的面试题目是_ #
14105次浏览 188人参与
# 反问环节如何提问 #
95366次浏览 1949人参与
# 中兴秋招 #
202829次浏览 2272人参与
# 简历上的经历如何包装 #
22591次浏览 702人参与
# 如何看待offer收割机的行为 #
814883次浏览 6079人参与
# 你最讨厌面试问你什么? #
23784次浏览 271人参与
# 秋招最大的收获是什么? #
38530次浏览 322人参与
# 我的实习收获 #
90744次浏览 1038人参与
# 26届的你,投了哪些公司? #
35176次浏览 418人参与
# 我对___祛魅了 #
41953次浏览 400人参与
# 数字马力求职进展汇总 #
184374次浏览 1500人参与
# 你跟室友的关系怎么样? #
5814次浏览 94人参与
# 什么样的背景能拿SSP? #
29574次浏览 189人参与
# 工作中哪个瞬间让你想离职 #
59948次浏览 540人参与
# 和同事相处最忌讳的是__ #
20449次浏览 213人参与
# 去年你投递实习了吗? #
22836次浏览 331人参与
# 如何快速融入团队? #
14463次浏览 176人参与
# 滴滴求职进展汇总 #
233051次浏览 2114人参与
# 不考虑转正,实习多久合适 #
38007次浏览 181人参与
# 机械人的金三校招总结 #
36136次浏览 461人参与
# 初创公司值得加入吗? #
27228次浏览 194人参与