直线上最多的点数(LeetCode 149)
哪些公司问过
答案要点
- 枚举每个点为基准,哈希统计与其他点的斜率频次,取最大值加 1
- 斜率用 (dy/g, dx/g) 最简分数表示,避免浮点误差
- 统一符号:保证 dx>0,dx=0 时统一表示竖直线
- 有重复点时单独计数并累加到各斜率上
- 复杂度 O(n² log C),空间 O(n);n≤2 直接返回 n
易错点
- 用浮点数做斜率键导致误判
- 忘记统一 gcd 后的符号,(1,-1) 和 (-1,1) 被当成不同斜率
- 忽略竖直线或重复点的特殊情况
面试官常见追问
- 为什么只需要统计 j>i 的点?
- 能不能用 dy/dx 的 double 作为键?
- 有什么剪枝?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。