感谢各位大佬流光溢彩的代码。
求最大公约数的函数不需要有对调a、b的逻辑,否则会超时。(其实已经隐藏了对调逻辑)。
另外学会了map<pair<int, int> > myMap
以及myMap[{a, b}]++
的骚操作。
开心😄
class Solution { public: /** * * @param points Point类vector * @return int整型 */ int maxPoints(vector& points) { // write code here int len = points.size(); if (len <= 2) { return len; } int result = 0; for (int i = 0; i < len; ++i) { map<pair<int, int> > recordMap; int dup = 1; // 自身也算一个点,另外重合点也算 for (int j = i + 1; j < len; ++j) { int x = points[i].x - points[j].x; int y = points[i].y - points[j].y; if (x == 0 && y == 0) { ++dup; } else { int g = gcd(x, y); // 获取最大公约数 x = x / g; y = y / g; recordMap[{x, y}]++; } } result = max(result, dup); for (auto it = recordMap.begin(); it != recordMap.end(); ++it) { result = max(result, it->second + dup); } } return result; } int gcd(int a, int b) { // 注意:此处如果加上判断a、b大小的逻辑会超时 // 其实最下面👇隐含了对调a、b的功能 /*if (a > b) { a = a + b; b = a - b; a = a - b; }*/ return b == 0 ? a : gcd(b, a % b); } };