LeetCode:149 Max Points on a Line

本文主要是介绍LeetCode:149 Max Points on a Line，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述：

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

 

解法：

错误解法：使用斜率，会存在测试用例，卡精度,如：[[0,0],[94911151,94911150],[94911152,94911151]]

class Solution {public int maxPoints(int[][] points) {int samePoint = 0;int max = 0;if (points.length <= 2)return points.length;for (int i = 0; i < points.length; i++) {HashMap<Float, List<Integer[][]>> hashMap = new HashMap<Float, List<Integer[][]>>();samePoint = 0;for (int j = 0; j < points.length; j++) {float k;if (i == j) continue;if(points[i][0] == points[j][0] && points[i][1] == points[j][1]){samePoint++;continue;}if (points[j][0] == points[i][0])k = Integer.MIN_VALUE; //负无穷k = ((float) (points[j][1] - points[i][1]) / (points[j][0] - points[i][0]));List<Integer[][]> array_list = hashMap.get(k);if (array_list == null) {array_list = new ArrayList<>();Integer[][] tmp = {{points[i][0], points[i][1]}};array_list.add(tmp);hashMap.put(k, array_list);}Integer[][] tmp = {{points[j][0], points[j][1]}};array_list.add(tmp);}for (List list : hashMap.values()) {int len = list.size();if ((len + samePoint) > max) {max = len + samePoint;}}}return max == 0 ?(samePoint+1) : max;}
}

正解：使用最大公约数

class Solution {public int maxPoints(int[][] points) {if(points.length <= 2) return points.length; //返回边界值//int maxPoints = -1;int max = 0;int samePoints = 0;  //设置重复点，最后返回maxPoints = max + samePoints;for (int i = 0; i < points.length; i++) {HashMap<String,Integer> hashMap = new HashMap<String , Integer>();samePoints = 0;for (int j = 0; j < points.length; j++) {if(i == j) continue;if(points[i][0] == points[j][0] && points[i][1] == points[j][1]) {samePoints++;continue;}int dx = points[j][0] - points[i][0];int dy = points[j][1] - points[i][1];int d = gcd(dx,dy);String temp = Integer.toString(dx/d) + '#' + Integer.toString(dy/d);if(hashMap.get(temp) == null){hashMap.put(temp,2); //包括点i}else {int tmp_a = hashMap.get(temp) + 1;hashMap.put(temp,tmp_a);}}for(int a : hashMap.values()){if((a + samePoints) > max)max = a+samePoints;}}return max == 0 ?(samePoints+1) : max; //若全为相同点，则不会进入循环，因此需添加此情况}//求解最大公约数public static int gcd(int a,int b){return b==0?a:gcd(b,a%b);}}

 

这篇关于LeetCode:149 Max Points on a Line的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---