LeetCode-Go 题解 1232Check If It Is a Straight Line——用叉积判定点共线【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读1232. Check If It Is a Straight Line 仓库中的完整实现与测试为基础讲解如何用斜率相等 叉积乘法的方式避免除法与浮点误差写出一次遍历、常数空间的 Go 解法并给出可直接运行的验证方式。读完本文你将掌握共线判定问题的数学原理、Go 实现要点及其测试用例的组织方法。题目描述与约束题目给出一个二维数组coordinates其中coordinates[i] [x, y]代表平面上一个点的横纵坐标要求判断这些点是否全部落在同一条直线上共线返回true否则返回false。示例 1共线Input: coordinates [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] Output: true这 6 个点满足y x 1全部位于同一条直线上。示例 2不共线Input: coordinates [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]] Output: false点(1,1)、(2,2)与(3,4)已经不在同一条直线上因此整体判定为false。约束条件2 coordinates.length 1000至少有两个点最多 1000 个点coordinates[i].length 2每个点恰好包含两个整数坐标-10^4 coordinates[i][0], coordinates[i][1] 10^4坐标取值范围在[-10000, 10000]coordinates中不含重复的点因此不需要处理两个点重合的边界情况。核心数学原理斜率相等与叉积判断点是否共线最直观的思路是几何中的斜率相等对任意相邻点对(A, B)和(B, C)如果它们各自组成的线段斜率一致则A、B、C三点共线依此类推遍历全部点即可。斜率的定义是两点纵坐标之差与横坐标之差的比值k (y2 - y1) / (x2 - x1)直接使用除法存在两个问题除零风险当线段垂直于 x 轴即x2 - x1 0时分母为 0斜率不存在代码需要额外分支处理浮点精度除法产生浮点数在比较相等性时可能引入误差。原文档给出的技巧是把除法比较换成乘法比较。设两段线段的斜率分别为a/b与c/d斜率相等即a/b c/d交叉相乘得到a * d c * b这样就彻底避免了除法。从几何视角看这等价于计算两个向量的叉积cross product向量(dx0, dy0)与(dx, dy)的叉积dx0*dy - dy0*dx为 0 时两向量平行即对应三点共线。该技巧在同一仓库的另一道几何题 1037. Valid Boomerang 中同样被使用回旋镖要求三个点各不相同且不在一条直线上其一行式实现正是用交叉相乘判断三点是否共线可见这是该仓库处理共线类题目的统一套路。仓库实现解析仓库中的完整实现位于 leetcode/1232.Check-If-It-Is-a-Straight-Line/1232. Check If It Is a Straight Line.go代码与文档一致package leetcode func checkStraightLine(coordinates [][]int) bool { dx0 : coordinates[1][0] - coordinates[0][0] dy0 : coordinates[1][1] - coordinates[0][1] for i : 1; i len(coordinates)-1; i { dx : coordinates[i1][0] - coordinates[i][0] dy : coordinates[i1][1] - coordinates[i][1] if dy*dx0 ! dy0*dx { // check cross product return false } } return true }逐行解读基准向量先取前两个点coordinates[0]与coordinates[1]计算出基准向量(dx0, dy0)。因为题目保证至少有两个点且不重复(dx0, dy0)不会是零向量遍历比较从i 1开始逐段计算点i到点i1的方向向量(dx, dy)并将它与基准向量的叉积dy*dx0 - dy0*dx与 0 比较提前返回只要任何一段向量的方向与基准向量不平行叉积非 0立即返回false无需继续遍历完全共线全部段落通过检查则返回true。关于整数溢出由于坐标范围是[-10^4, 10^4]相邻点坐标之差最大为2 * 10^4叉积计算的两个乘积绝对值最大约为4 * 10^8远小于 Go 中int类型64 位平台下可达9.2 * 10^18的表示范围因此直接使用整数乘法是安全且精确的不存在浮点误差。测试用例验证仓库为该题编写了测试文件 leetcode/1232.Check-If-It-Is-a-Straight-Line/1232. Check If It Is a Straight Line_test.go采用了本项目统一的para参数ans期望答案表格驱动测试风格type question1232 struct { para1232 ans1232 } // para 是参数 // one 代表第一个参数 type para1232 struct { arr [][]int } // ans 是答案 // one 代表第一个答案 type ans1232 struct { one bool } func Test_Problem1232(t *testing.T) { qs : []question1232{ { para1232{[][]int{{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}}}, ans1232{true}, }, { para1232{[][]int{{1, 1}, {2, 2}, {3, 4}, {4, 5}, {5, 6}, {7, 7}}}, ans1232{false}, }, } fmt.Printf(------------------------Leetcode Problem 1232------------------------\n) for _, q : range qs { _, p : q.ans1232, q.para1232 fmt.Printf(【input】:%v 【output】:%v\n, p, checkStraightLine(p.arr)) } fmt.Printf(\n\n\n) }测试覆盖了题目给出的两个典型用例一条正斜率为 1 的直线预期true和第三个点偏离直线的散点集预期false。该测试同时兼顾了文档示例的回归验证与函数调用的输出打印符合本项目每个题解目录都配套_test.go文件的组织规范。复杂度分析时间复杂度O(n)其中n为coordinates的长度。基准向量计算为常数时间随后仅需一次线性遍历空间复杂度O(1)除若干临时变量外没有使用任何额外数据结构。在最坏情况下n 1000整个函数也只需 999 次乘法与比较性能开销极小。如何运行与验证本仓库使用 Go Modules 管理依赖根目录 go.mod 声明模块名为github.com/halfrost/LeetCode-GoGo 版本为 1.19。由于 1232 题的目录是独立包可以直接单独运行其测试# 在仓库根目录执行仅运行 1232 题的测试 go test -v ./leetcode/1232.Check-If-It-Is-a-Straight-Line/若要运行全部题解测试并生成覆盖率报告仓库提供了 gotest.sh 脚本# 对 leetcode 下所有包执行带覆盖率的测试 ./gotest.sh脚本内部实际执行的是go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...生成的coverage.txt可用于 Codecov 等覆盖率平台。你也可以先git clone https://gitcode.com/GitHub_Trending/le/LeetCode-Go.git拉取仓库再在本地执行上述命令复现结果。小结1232. Check If It Is a Straight Line 是平面几何入门的经典题目其核心经验可以概括为三点避免除法将斜率相等转化为向量叉积为零规避除零分支与浮点误差一次遍历以首两点为基准向量逐段校验方向一致性遇到不平行立即返回边界保障题目保证至少两点且无重复点使基准向量必然非零实现可以保持简洁。仓库提供的 实现文件 与 测试文件 给出了可直接参考的完整工程化写法而 1037. Valid Boomerang 则展示了同一数学技巧在共线取反场景下的复用方式。掌握叉积判定共线后后续处理多边形、凸包、点在直线上等几何问题都可以沿用这一思维。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考