某人丢给我的算法题...
给定一个二维平面,平面有n个点,求最多有多少个点在同一条直线上
示例1:
输入:[[1,1],[2,2],[3,3]]
输出:3
解释:
^
| o
| o
| o
+--------------->
0 1 2 3 4 5
示例2:
输入:[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出:4
解释:
^
| o
| o o
| o
| o o
+------------------>
0 1 2 3 4 5 6
## java代码实现
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class PointMapTest {
public static void main(String[] args) {
//int[][] t = new int[][]{{1,1},{2,2},{3,3}};
int[][] t = new int[][]{{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};
/**
* 运算有多少直线公式
*/
Set<String> kset = new HashSet<>();
for(int i=0;i<t.length-1;i++){
for(int j=0;j<t.length-1-i;j++){
String k = calKey(t[j], t[j+1]);
kset.add(k);
}
}
/**
* 验证每个直线公式有多少点
*/
Map<String,Integer> countMap = new HashMap<>();
Iterator<String> it = kset.iterator();
while(it.hasNext()){
String k = it.next();
int count = 0;
for(int i = 0; i < t.length; i++){
boolean flag = mat(t[i], k);
if(flag) count ++;
}
countMap.put(k, count);
}
/**
* 输出做大的一个公式有多少个点
*/
List<Integer> l1 = new ArrayList<>(countMap.values());
Integer max = Collections.max(l1);
System.out.println("输出:" + max);
System.out.println("解释:");
/**
* 计算地图大小
*/
int maxX = 0;
int maxY = 0;
for(int i = 0 ; i< t.length; i++){
int tempX = t[i][0];
int tempY = t[i][1];
maxX = maxX > tempX ? max : tempX;
maxY = maxY > tempY ? maxY : tempY;
}
/**
* 生成初始化地图数组
*/
String[][] map = new String[maxX][maxY+2];
for(int i = 0 ; i < map.length; i ++){
for(int j = 0 ; j < map[0].length ; j++){
try{
map[i][j] = " ";
}catch (Exception e) {
System.err.println("i:" + i+ ",j :" + j);
}
}
}
/**
* 将坐标点转换到地图数组中
* 1.上下反转
* 2.逆时针旋转90度
*/
for(int i = 0 ; i < t.length; i++){
map[t[i][1] - 1][t[i][0] - 1] = " o ";
}
/**
* 打印地图
*/
String mapString = printMap(map);
System.out.println(mapString);
}
/**
* 计算两个点的公式
* AX+BY+C=0
* A = Y2 - Y1
* B = X1 - X2
* C = X2*Y1 - X1*Y2
*/
public static String calKey(int[] a, int[] b){
int y2 = b[1];
int y1 = a[1];
int x1 = a[0];
int x2 = b[0];
int aa = y2 - y1;
int ba = x1 - x2;
int c = x2 * y1 - x1 * y2;
return aa + "_" +ba + "_" + c;
}
/**
* 验证点是否在直线上
* @param a 点
* @param k 直线公式
*/
public static boolean mat(int[]a, String k){
String[] s = k.split("_");
int x = Integer.parseInt(s[0]);
int y = Integer.parseInt(s[1]);
int c = Integer.parseInt(s[2]);
return 0 == (x * a[0] + y * a[1] + c);
}
/**
* 打印地图
*/
public static String printMap(String[][] map){
StringBuilder sb = new StringBuilder();
sb.append("^");
sb.append("\n");
for(int i = 0 ; i < map.length; i ++){
sb.append("|");
for(int j = 0 ;j < map[0].length; j++){
sb.append(map[map.length - i - 1][j]);
}
sb.append("\n");
}
sb.append("+");
for(int i = 0 ; i < map[0].length; i++){
sb.append("---");
}
sb.append(">").append("\n");
sb.append("0");
for(int i = 0 ; i < map[0].length; i++){
sb.append(" "+(i+1)+" ");
}
sb.append("\n");
return sb.toString();
}
}
控制台打印结果
输出:4
解释:
^
| o
| o o
| o
| o o
+------------------>
0 1 2 3 4 5 6
楼主,你这个WP主题能给我一份吗,万分感谢,微信号:zhongguoyantai