Hard
今天上午有幸參加了Refdash的免費(fèi)Mock interview, 被暴擊一萬(wàn)點(diǎn).不過(guò)先刷完L家tag題再說(shuō)那道題吧.
這也是一道邏輯其實(shí)很簡(jiǎn)單智亮，但是很多細(xì)節(jié)容易出錯(cuò)的題.
要找到共線最多的點(diǎn)，我們主線是通過(guò)找斜率. 遍歷每個(gè)點(diǎn)和它后面的點(diǎn)腔彰，找到倆倆斜率，構(gòu)建一個(gè)以斜率為key, 斜率出現(xiàn)的次數(shù)為value的hashMap. 我們用String來(lái)存斜率迹卢，要將dx, dy處理到lowest term拗小， 通過(guò)除以他們的最大公約數(shù)來(lái)做到. 這里求gcd的算法叫做Euclidean算法，具體見(jiàn)鏈接努隙，比較簡(jiǎn)單好用. 注意我們處理跟points[i]重合的點(diǎn)的方法是統(tǒng)計(jì)samePoint這個(gè)變量. 如果遇到i之后有相同的點(diǎn)就累加. 首先我們有一個(gè)總的res來(lái)統(tǒng)計(jì)當(dāng)前共線最多的點(diǎn)球恤，然后每遍歷一個(gè)點(diǎn)和其后面的點(diǎn)時(shí)（即每次進(jìn)入外層for循環(huán)）都再記錄一個(gè)max來(lái)記錄這個(gè)點(diǎn)能跟后面的點(diǎn)組成共線點(diǎn)最多的那條直線上的點(diǎn)數(shù). 每走一遍內(nèi)循環(huán)，就是遍歷到這個(gè)點(diǎn)后面的某個(gè)點(diǎn)荸镊，就用這個(gè)斜率下的頻數(shù)和當(dāng)前max的中的最大值來(lái)更新max. 每次遍歷完某個(gè)點(diǎn)之后所有的點(diǎn)（即內(nèi)循環(huán)遍歷完）咽斧，則更新一下總的res為Math.max(res, max). 同時(shí)注意一下，每一次外循環(huán)換一個(gè)點(diǎn)躬存，map要全部清除之前的記錄张惹。因?yàn)槲覀円业氖菑倪@個(gè)點(diǎn)出發(fā)的共線的最多點(diǎn)，不能要之前的mapping, 只需要之前的res拿來(lái)更新就可以.
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
class Solution {
public int maxPoints(Point[] points) {
if (points == null || points.length == 0){
return 0;
}
Map<String, Integer> map = new HashMap<>();
int res = 0;
for (int i = 0; i < points.length; i++){
map.clear();
int samePoint = 1;
int max = 0;
for (int j = i + 1; j < points.length; j++){
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
if (dx == 0 && dy == 0){
samePoint++;
continue;
}
int gcd = generateGCD(dx, dy);
dx /= gcd;
dy /= gcd;
String slope = dy + "/" + dx;
if (map.containsKey(slope)){
map.put(slope, map.get(slope) + 1);
} else {
map.put(slope, 1);
}
max = Math.max(max, map.get(slope));
}
res = Math.max(res, max + samePoint);
}
return res;
}
private int generateGCD(int a, int b){
if (b == 0){
return a;
} else {
return generateGCD(b, a % b);
}
}
}
