在刷Leetcode的时候，第149题需要求经过两点的直线的表达式，所以总结一下如何用代码求出经过两点的直线的表达式

注：只考虑 x, y 为整数的情况，且不考虑计算中整型溢出的情况

1.求坐标系中经过两点的直线的表达式

表达式的形式为：y = a * x + b

根据两个点的坐标得到方程式：

①. y1 = a * x1 + b

②. y2 = a * x2 + b

得出 a 和 b 的表达式为（x1 - x2 不为 0 的情况下）：

a = (y1 - y2)/(x1 - x2)

b = (x1 * y2 - x2 * y1)/(x1 - x2)

2.分数化简为真分数

由于 a, b 都可能为无限小数，且计算机存储浮点数存在精度问题，需要将 a, b 都用分数表示

若 a, b 不是真分数，那么同一条直线可能会有多条表达式，所以需要将 a, b 都化简为真分数

分数化简为真分数方法是：分子分母同时除以分子分母的最大公约数

3.求最大公约数

使用辗转相除法

* 表达式的形式为：y = a * x + b *

* 根据两个点的坐标得到方程式： * ①. y1 = a * x1 + b * ②. y2 = a * x2 + b *

* 得出 a 和 b 的表达式为（x1 - x2 不为 0 的情况下）： * a = (y1 - y2)/(x1 - x2) * b = (x1 * y2 - x2 * y1)/(x1 - x2) * * @param point1 第一个点的坐标 * @param point2 第二个点的坐标 * @return 经过point1和point2的直线的表达式 */ public static String getExpression(int[] point1, int[] point2) { if (point1.length != 2 || point2.length != 2) { throw new IllegalArgumentException("无效的点坐标"); } if (point1[0] == point2[0] && point1[1] == point2[1]) { throw new IllegalArgumentException("两个点的坐标不能相同"); } int x1 = point1[0]; int y1 = point1[1]; int x2 = point2[0]; int y2 = point2[1]; // 如果x1 == x2，无法套用公式，直接返回 int denominator = x1 - x2; if (denominator == 0) { return "x = " + x1; } int numerator = y1 - y2; String a = fractionSimplification(denominator, numerator); numerator = x1 * y2 - x2 * y1; String b = fractionSimplification(denominator, numerator); String expression; if (ZERO.equals(a)) { expression = "y = " + b; } else if (ZERO.equals(b)) { expression = "y = " + a + " * x"; } else { expression = "y = " + a + " * x + " + b; } return expression; } /** * 分数化简为真分数 * * @param denominator 分母 * @param numerator 分子 * @return 真分数 分子/分母 */ public static String fractionSimplification(int denominator, int numerator) { if (denominator == 0) { throw new IllegalArgumentException("分母不能为0"); } if (numerator == 0) { return ZERO; } String simpleFraction = new String(); if (numerator % denominator == 0 && numerator / denominator != 0) { // 如果 分子/分母 为整数，相除的结果即为化简结果 simpleFraction += numerator / denominator; } else { // 分数化简就是分母分子同时除以它们的最大公约数 int gcd = gcd(denominator, numerator); simpleFraction = (numerator / gcd) + "/" + (denominator / gcd); } return simpleFraction; } /** * 求最小公倍数 * * @param a 第一个数 * @param b 第二个数 * @return 最小公倍数 */ public static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } public static void main(String[] args) { int[] a = {1, 1}; int[] b = {1, 2}; int[] c = {3, 2}; int[] d = {1, 2}; int[] e = {0, 0}; int[] f = {1, 3}; int[] g = {0, 1}; int[] h = {1, 3}; int[] i = {2, 4}; int[] j = {5, 2}; System.out.println(getExpression(a, b)); System.out.println(getExpression(c, d)); System.out.println(getExpression(e, f)); System.out.println(getExpression(g, h)); System.out.println(getExpression(i, j)); } }

题目描述：

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

思路：

1.求出每两个点之间的直线表达式

2.统计每个表达式出现的次数，次数最多的表达式即为点最多的直线

3.根据表达式出现的次数求出点的个数：

代码：

* 表达式的形式为：y = a * x + b *

* 根据两个点的坐标得到方程式： * ①. y1 = a * x1 + b * ②. y2 = a * x2 + b *

* 得出 a 和 b 的表达式为（x1 - x2 不为 0 的情况下）： * a = (y1 - y2)/(x1 - x2) * b = (x1 * y2 - x2 * y1)/(x1 - x2) * * @param point1 第一个点的坐标 * @param point2 第二个点的坐标 * @return 经过point1和point2的直线的表达式 */ public static String getExpression(int[] point1, int[] point2) { if (point1.length != 2 || point2.length != 2) { throw new IllegalArgumentException("无效的点坐标"); } if (point1[0] == point2[0] && point1[1] == point2[1]) { throw new IllegalArgumentException("两个点的坐标不能相同"); } int x1 = point1[0]; int y1 = point1[1]; int x2 = point2[0]; int y2 = point2[1]; // 如果x1 == x2，无法套用公式，直接返回 int denominator = x1 - x2; if (denominator == 0) { return "x = " + x1; } int numerator = y1 - y2; String a = fractionSimplification(denominator, numerator); numerator = x1 * y2 - x2 * y1; String b = fractionSimplification(denominator, numerator); String expression; if (ZERO.equals(a)) { expression = "y = " + b; } else if (ZERO.equals(b)) { expression = "y = " + a + " * x"; } else { expression = "y = " + a + " * x + " + b; } return expression; } /** * 分数化简为真分数 * * @param denominator 分母 * @param numerator 分子 * @return 真分数 分子/分母 */ public static String fractionSimplification(int denominator, int numerator) { if (denominator == 0) { throw new IllegalArgumentException("分母不能为0"); } if (numerator == 0) { return ZERO; } String simpleFraction = new String(); if (numerator % denominator == 0 && numerator / denominator != 0) { // 如果 分子/分母 为整数，相除的结果即为化简结果 simpleFraction += numerator / denominator; } else { // 分数化简就是分母分子同时除以它们的最大公约数 int gcd = gcd(denominator, numerator); simpleFraction = (numerator / gcd) + "/" + (denominator / gcd); } return simpleFraction; } /** * 求最小公倍数 * * @param a 第一个数 * @param b 第二个数 * @return 最小公倍数 */ public static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } public static int maxPoints(int[][] points) { // 先获取每个点与其它任一点构成的直线表达式，并统计每个表达式的数量 Map expressionCountMap = new HashMap(); for (int firstIndex = 0; firstIndex < points.length - 1; firstIndex++) { for (int secondIndex = firstIndex + 1; secondIndex < points.length; secondIndex++) { String expression = getExpression(points[firstIndex], points[secondIndex]); Integer count = expressionCountMap.get(expression); if (count == null) { expressionCountMap.put(expression, 1); } else { expressionCountMap.put(expression, count + 1); } } } // 出现次数最多的表达式即为点最多的直线的表达式 int maxCount = 0; for (Map.Entry entry : expressionCountMap.entrySet()) { if (entry.getValue() > maxCount) { maxCount = entry.getValue(); } } // n个点两两组合方式有 C(n, 2) = n!/(2! * (n-2)!) = (n² - n)/2 种 // 所以我们点最多的直线表达式的出现次数count与点的个数n之间的关系为: count = (n² - n)/2 // 解方程： // Δ = √(b² - 4ac) = √(1/4 + 2 * count) // n = 1/2 ± √(1/4 + 2 * count) // ∵ count为非负整数 // ∴ min(Δ) = 1/2 // ∵ n > 0 // ∴ n = 1/2 + √(1/4 + 2 * count) return (int) (0.5 + Math.sqrt((0.25 + 2 * maxCount))); } }