农业银行算法题，为什么用初中知识出题，这么多人不会？

背景介绍

总所周知，有相当一部分的大学生是不会初高中知识的。

因此，每当那种「初等数学为背景编写的算法题」在笔面出现，舆论往往分成"三大派":

甚至那位说"致敬高考"的同学也搞岔了，高考哪有这么简单，美得你 🤣

这仅仅是初中数学「几何学」中较为简单的知识点。

抓住大学生对初高中知识这种「会者不难，难者不会」的现状，互联网大厂似乎更喜欢此类「考察初等数学」的算法题。

因为十个候选人，九个题海战术，HOT 100 和剑指 Offer 大家都刷得飞起了。

冷不丁的考察这种题目，反而更能起到"筛选"效果。

但此类算法题，农业银行 并非首创，甚至是同一道题，也被 华为云、美的 和 百度 先后出过。

下面，一起来看看这道题。

题目描述

平台：LeetCode

题号：149

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

示例 1：

输入：points = [[1,1],[2,2],[3,3]]


输出：3

示例 2：

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]


输出：4

提示：

• 
  
• $1<=points.length<=300$
  
• $points[i].length=2$
  
• −104<=xi,yi<=104-10^4 <= x_i, y_i <= 10^4−104<=xi​,yi​<=104
  
• points 中的所有点互不相同
  

枚举直线 + 枚举统计

我们知道，两点可以确定一条线。

一个朴素的做法是先枚举两点（确定一条线），然后检查其余点是否落在该线中。

为避免除法精度问题，当我们枚举两个点 $x$ 和 $y$ 时，不直接计算其对应直线的 斜率和 截距。

而是通过判断 $x$ 和 $y$ 与第三个点 $p$ 形成的两条直线斜率是否相等，来得知点 $p$ 是否落在该直线上。

斜率相等的两条直线要么平行，要么重合。

平行需要 $4$ 个点来唯一确定，我们只有 $3$ 个点，因此直接判定两条直线是否重合即可。

详细说，当给定两个点 (x1,y1)(x_1, y_1)(x1​,y1​) 和 (x2,y2)(x_2, y_2)(x2​,y2​) 时，对应斜率 y2−y1x2−x1\frac{y_2 - y_1}{x_2 - x_1}x2​−x1​y2​−y1​​。

为避免计算机除法的精度问题，我们将「判定 ay−byax−bx=by−cybx−cx\frac{a_y - b_y}{a_x - b_x} = \frac{b_y - c_y}{b_x - c_x}ax​−bx​ay​−by​​=bx​−cx​by​−cy​​ 是否成立」改为「判定 (ay−by)×(bx−cx)=(ax−bx)×(by−cy)(a_y - b_y) \times (b_x - c_x) = (a_x - b_x) \times (b_y - c_y)(ay​−by​)×(bx​−cx​)=(ax​−bx​)×(by​−cy​) 是否成立」。

将存在精度问题的「除法判定」巧妙转为「乘法判定」。

Java 代码：

class Solution {
public int maxPoints(int[][] points) {
int n = points.length, ans = 1;
for (int i = 0; i < n; i++) {
int[] x = points[i];
for (int j = i + 1; j < n; j++) {
int[] y = points[j];
// 枚举点对 (i,j) 并统计有多少点在该线上, 起始 cnt = 2 代表只有 i 和 j 两个点在此线上
int cnt = 2;
for (int k = j + 1; k < n; k++) {
int[] p = points[k];
int s1 = (y[1] - x[1]) * (p[0] - y[0]);
int s2 = (p[1] - y[1]) * (y[0] - x[0]);
if (s1 == s2) cnt++;

                }

                ans = Math.max(ans, cnt);

            }

        }
return ans;

    }

}

C++ 代码：

class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int n = points.size(), ans = 1;
for (int i = 0; i < n; i++) {

            vector<int> x = points[i];
for (int j = i + 1; j < n; j++) {

                vector<int> y = points[j];
// 枚举点对 (i,j) 并统计有多少点在该线上, 起始 cnt = 2 代表只有 i 和 j 两个点在此线上
int cnt = 2;
for (int k = j + 1; k < n; k++) {

                    vector<int> p = points[k];
int s1 = (y[1] - x[1]) * (p[0] - y[0]);
int s2 = (p[1] - y[1]) * (y[0] - x[0]);
if (s1 == s2) cnt++;

                }

                ans = max(ans, cnt);

            }

        }
return ans;

    }

};

Python 代码：

class Solution:
def maxPoints(self, points: List[List[int]]) -> int:

        n, ans = len(points), 1
for i, x in enumerate(points):
for j in range(i + 1, n):

                y = points[j]
# 枚举点对 (i,j) 并统计有多少点在该线上, 起始 cnt = 2 代表只有 i 和 j 两个点在此线上

                cnt = 2
for k in range(j + 1, n):

                    p = points[k]

                    s1 = (y[1] - x[1]) * (p[0] - y[0])

                    s2 = (p[1] - y[1]) * (y[0] - x[0])
if s1 == s2: cnt += 1

                ans = max(ans, cnt)
return ans

TypeScript 代码：

function maxPoints(points: number[][]): number {
let n = points.length, ans = 1;
for (let i = 0; i < n; i++) {
let x = points[i];
for (let j = i + 1; j < n; j++) {
// 枚举点对 (i,j) 并统计有多少点在该线上, 起始 cnt = 2 代表只有 i 和 j 两个点在此线上
let y = points[j], cnt = 2;
for (let k = j + 1; k < n; k++) {
let p = points[k];
let s1 = (y[1] - x[1]) * (p[0] - y[0]);
let s2 = (p[1] - y[1]) * (y[0] - x[0]);
if (s1 == s2) cnt++;

            }

            ans = Math.max(ans, cnt);

        }

    }
return ans;

};

• 
  
• 时间复杂度：O(n3)O(n^3)O(n3)
  
• 空间复杂度：$O(1)$
  

枚举直线 + 哈希表统计

根据「朴素解法」的思路，枚举所有直线的过程不可避免，但统计点数的过程可以优化。

具体的，我们可以先枚举所有可能出现的 直线斜率（根据两点确定一条直线，即枚举所有的「点对」），使用「哈希表」统计所有 斜率 对应的点的数量，在所有值中取个 $max$ 即是答案。

一些细节：在使用「哈希表」进行保存时，为了避免精度问题，我们直接使用字符串进行保存，同时需要将 斜率 约干净（套用 gcd 求最大公约数模板）。

Java 代码：

class Solution {
public int maxPoints(int[][] points) {
int n = points.length, ans = 1;
for (int i = 0; i < n; i++) {

            Map<String, Integer> map = new HashMap<>();
// 由当前点 i 发出的直线所经过的最多点数量
int max = 0;
for (int j = i + 1; j < n; j++) {
int x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
int a = x1 - x2, b = y1 - y2;
int k = gcd(a, b);
String key = (a / k) + "_" + (b / k);

                map.put(key, map.getOrDefault(key, 0) + 1);

                max = Math.max(max, map.get(key));

            }

            ans = Math.max(ans, max + 1);

        }
return ans;

    }
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);

    }

}

C++ 代码：

class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int n = points.size(), ans = 1;
for (int i = 0; i < n; i++) {

            map<string, int> map;
int maxv = 0;
for (int j = i + 1; j < n; j++) {
int x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
int a = x1 - x2, b = y1 - y2;
int k = gcd(a, b);

                string key = to_string(a / k) + "_" + to_string(b / k);

                map[key]++;

                maxv = max(maxv, map[key]);

            }

            ans = max(ans, maxv + 1);

        }
return ans;

    }
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);

    }

};

Python 代码：

class Solution:
def maxPoints(self, points):
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)


        n, ans = len(points), 1
for i in range(n):

            mapping = {}

            maxv = 0
for j in range(i + 1, n):

                x1, y1 = points[i]

                x2, y2 = points[j]

                a, b = x1 - x2, y1 - y2

                k = gcd(a, b)

                key = str(a // k) + "_" + str(b // k)

                mapping[key] = mapping.get(key, 0) + 1

                maxv = max(maxv, mapping[key])

            ans = max(ans, maxv + 1)    
return ans

TypeScript 代码：

function maxPoints(points: number[][]): number {
const gcd = function(a: number, b: number): number {
return b == 0 ? a : gcd(b, a % b);

    }
let n = points.length, ans = 1;
for (let i = 0; i < n; i++) {
let mapping = {}, maxv = 0;
for (let j = i + 1; j < n; j++) {
let x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
let a = x1 - x2, b = y1 - y2;
let k = gcd(a, b);
let key = `${a / k}_${b / k}`;

            mapping[key] = mapping[key] ? mapping[key] + 1 : 1;

            maxv = Math.max(maxv, mapping[key]);

        }

        ans = Math.max(ans, maxv + 1);

    }
return ans;

};

• 
  
• 时间复杂度：枚举所有直线的复杂度为 O(n2)O(n^2)O(n2)；令坐标值的最大差值为 $m$，gcd 复杂度为 $O(\log m)$。整体复杂度为 O(n2×log⁡m)O(n^2 \times \log{m})O(n2×logm)
  
• 空间复杂度：$O(n)$
  

总结

虽然题目是以初中数学中的"斜率 & 截距"为背景，但仍有不少细节需要把握。

这也是「传统数学题」和「计算机算法题」的最大差别：

• 
  
• 过程分值: 传统数学题有过程分，计算机算法题没有过程分，哪怕思路对了 $90$%，代码没写出来，就是 $0$ 分；
  
• 数据类型：传统数学题只涉及数值，计算机算法题需要考虑各种数据类型；
  
• 运算精度：传统数学题无须考虑运算精度问题，而计算机算法题需要；
  
• 判定机制：传统数学题通常给定具体数据和问题，然后人工根据求解过程和最终答案来综合评分，而计算机算法题不仅仅是求解一个具体的 case，通常是给定数据范围，然后通过若个不同的样例，机器自动判断程序的正确性；
  
• 执行效率/时空复杂度：传统数学题无须考虑执行效率问题，只要求考生通过有限步骤（或引用定理节省步骤）写出答案即可，计算机算法题要求程序在有限时间空间内执行完；
  
• 边界/异常处理：由于传统数学题的题面通常只有一个具体数据，因此不涉及边界处理，而计算机算法题需要考虑数据边界，甚至是对异常的输入输出做相应处理。
  

可见，传统数学题，有正确的思路基本上就赢了大半，而计算机算法题嘛，有正确思路，也只是万里长征跑了个 $400$ 米而已。