分类讨论共线情况1.共点x1x2 y1 y22.x共线 x1 x23.y共线 y1 y24.共斜率 k (y1-y2) / (x1-x2) 注意需要用辗转相处法求得最大公约数换一种问法共线最多的点点个数用max(234) 1规范化的目标是唯一表示一条直线对于方向向量(dx, dy)(dx, dy)和(-dx, -dy)表示同一条直线方向相反但直线相同。规范化的规则是强制让dx 0如果dx 0则强制让dy 0。这样每条直线只有一个唯一的 key。class Solution { public: vectorint bestLine(vectorvectorint points) { int len points.size(); if (len 2) { return {}; } vectorint result {0, 1}; int max_count 0; for (int i 0; i len; i) { unordered_mapstring, int xielv; unordered_mapstring, int first; for (int j i 1; j len; j) { string key calc(points[i], points[j]); /*if (xielv.find(key) xielv.end()) { xielv[key] 0; first[key] j; }*/ xielv[key]; if (xielv[key] 1) { first[key] j; } } // 处理非重合点斜率 for (auto e : xielv) { if (e.first ! 0_0) { int count e.second 1 sameCount; vectorint candidate {i, first[e.first]}; if (count max_count) { max_count count; result candidate; } else if (count max_count) { if (candidate[0] result[0] || (candidate[0] result[0] candidate[1] result[1])) { result candidate; } } } } // 处理全是重合点的情况 if (xielv[0_0] 0) { int count xielv[0_0] 1; vectorint candidate {i, first[0_0]}; if (count max_count) { max_count count; result candidate; } else if (count max_count) { if (candidate[0] result[0] || (candidate[0] result[0] candidate[1] result[1])) { result candidate; } } } } return result; } private: string calc(const vectorint a, const vectorint b) { int dy a[1] - b[1]; int dx a[0] - b[0]; if (dy 0 dx 0) { return 0_0; } int g gcd(abs(dy), abs(dx)); dy / g; dx / g; if (dx 0 || (dx 0 dy 0)) { dx -dx; dy -dy; } return to_string(dy) _ to_string(dx); } int gcd(int a, int b) { while (b ! 0) { int t b; b a % b; a t; } return a; } };class Solution { public: vectorint bestLine(vectorvectorint points) { if (points.size() 0) { return {}; } std::vectorint result; int max_count 0; for (int i 0; i points.size(); i) { std::unordered_mapstd::string, std::vectorint table; int count 0; std::vectorint tmp_result; for (int j i 1; j points.size(); j) { int x1 points[i][0]; int y1 points[i][1]; int x2 points[j][0]; int y2 points[j][1]; if (x1 x2 y1 y2) { auto ite table.find(same); int cnt 0; if (ite table.end()) { std::vectorint tmp{i, j, 1}; table[same] tmp; cnt 1; if (cnt count) { std::vectorint tmp{i, j}; // tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } else { ite-second[2]; cnt ite-second[2]; if (cnt count) { std::vectorint tmp{ite-second[0], ite-second[1]}; // tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } count max(cnt, count); } else if (x1 x2) { auto ite table.find(x_same); int cnt 0; if (ite table.end()) { std::vectorint tmp{i, j, 1}; table[x_same] tmp; cnt 1; if (cnt count) { std::vectorint tmp{i, j}; // tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } else { ite-second[2]; cnt ite-second[2]; if (cnt count) { std::vectorint tmp{ite-second[0], ite-second[1]}; // tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } count max(cnt, count); } else if (y1 y2) { auto ite table.find(y_same); int cnt 0; if (ite table.end()) { std::vectorint tmp{i, j, 1}; table[y_same] tmp; cnt 1; if (cnt count) { std::vectorint tmp{i, j}; // tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } else { ite-second[2]; cnt ite-second[2]; // cout cnt count ite-second[0] // ite-second[1] endl; if (cnt count) { std::vectorint tmp{ite-second[0], ite-second[1]}; // tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } count max(cnt, count); } else { int cnt 0; int delta_x abs(x1 - x2); int delta_y abs(y1 - y2); int value gcd(delta_x, delta_y); int k1 delta_y / value; int k2 delta_x / value; std::string key to_string(k1) _ to_string(k2); auto ite table.find(key); if (ite ! table.end()) { ite-second[2]; cnt ite-second[2]; // cout cnt jj count // ite-second[0] ite-second[1] endl; if (cnt count) { std::vectorint tmp{ite-second[0], ite-second[1]}; // tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } else { std::vectorint tmp{i, j, 1}; table[key] tmp; cnt 1; // cout cnt count i j // endl; if (cnt count) { std::vectorint tmp{i, j}; // tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } count max(cnt, count); } // cout i: i count: count tmp: // tmp_result[0] tmp_result[1] endl; } if (count max_count) { // cout i: i count: count max_count: // max_count tmp: tmp_result[0] tmp_result[1] // endl; // result tmp_result; result get_result(result, tmp_result, count, max_count); max_count count; } } return result; } private: int gcd(int a, int b) { if (a b) { swap(a, b); } return b 0 ? a : gcd(b, a % b); } std::vectorint get_result(std::vectorint ori_result, std::vectorint tmp, int cnt, int count) { if (ori_result.size() 0) { return tmp; } if (cnt count) { return tmp; } if (tmp[0] ori_result[0]) { return tmp; } else if (tmp[0] ori_result[0] tmp[1] ori_result[1]) { return tmp; } return ori_result; } };#include iostream #include vector #include unordered_map using namespace std; class Solution { public: vectorint bestLine(vectorvectorint points) { if (points.size() 0) { return {}; } std::vectorint result; int max_count 0; for (int i 0; i points.size(); i) { std::unordered_mapstd::string, std::vectorint table; int count 0; std::vectorint tmp_result; for (int j i1; j points.size(); j) { int x1 points[i][0]; int y1 points[i][1]; int x2 points[j][0]; int y2 points[j][1]; if (x1 x2 y1 y2) { auto ite table.find(same); int cnt 0; if (ite table.end()) { std::vectorint tmp{i, j, 1}; table[same] tmp; cnt 1; if (cnt count) { std::vectorint tmp{i, j}; //tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } else { ite-second[2]; cnt ite-second[2]; if (cnt count) { std::vectorint tmp{ite-second[0], ite-second[1]}; //tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } count max(cnt, count); } else if (x1 x2) { auto ite table.find(x_same); int cnt 0; if (ite table.end()) { std::vectorint tmp{i, j, 1}; table[x_same] tmp; cnt 1; if (cnt count) { std::vectorint tmp{i, j}; //tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } else { ite-second[2]; cnt ite-second[2]; if (cnt count) { std::vectorint tmp{ite-second[0], ite-second[1]}; //tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } count max(cnt, count); } else if (y1 y2) { auto ite table.find(y_same); int cnt 0; if (ite table.end()) { std::vectorint tmp{i, j, 1}; table[y_same] tmp; cnt 1; if (cnt count) { std::vectorint tmp{i, j}; //tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } else { ite-second[2]; cnt ite-second[2]; //cout cnt count ite-second[0] ite-second[1] endl; if (cnt count) { std::vectorint tmp{ite-second[0], ite-second[1]}; //tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } count max(cnt, count); } else { int cnt 0; int delta_x abs(x1-x2); int delta_y abs(y1-y2); int value gcd(delta_x, delta_y); int k1 delta_y / value; int k2 delta_x / value; std::string key to_string(k1) _ to_string(k2); auto ite table.find(key); if (ite ! table.end()) { ite-second[2]; cnt ite-second[2]; //cout cnt jj count ite-second[0] ite-second[1] endl; if (cnt count) { std::vectorint tmp{ite-second[0], ite-second[1]}; //tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } else { std::vectorint tmp{i, j, 1}; table[key] tmp; cnt 1; //cout cnt count i j endl; if (cnt count) { std::vectorint tmp{i, j}; //tmp_result std::move(tmp); tmp_result get_result(tmp_result, tmp, cnt, count); } } count max(cnt, count); } //cout i: i count: count tmp: tmp_result[0] tmp_result[1] endl; } if (count max_count) { //cout i: i count: count max_count: max_count tmp: tmp_result[0] tmp_result[1] endl; //result tmp_result; result get_result(result, tmp_result, count, max_count); max_count count; } } return result; } private: int gcd(int a, int b) { if (a b) { swap(a, b); } return b 0 ? a : gcd(b, a%b); } std::vectorint get_result(std::vectorint ori_result, std::vectorint tmp, int cnt, int count) { if (ori_result.size() 0) { return tmp; } if (cnt count) { return tmp; } if (tmp[0] ori_result[0]) { return tmp; } else if (tmp[0] ori_result[0] tmp[1] ori_result[1]) { return tmp; } return ori_result; } }; int main() { Solution sol; std::vectorstd::vectorint points{{0,0},{1,1},{1,0},{2,0}}; auto result sol.bestLine(points); for (auto i : result) { cout i ; } cout endl; }https://leetcode.cn/problems/best-line-lcci/?envTypestudy-plan-v2envIdcracking-the-coding-interviewclass Solution { public: int maxPoints(vectorvectorint points) { int n points.size(); if (n 2) return n; int ans 0; for (int i 0; i n; i) { // 如果可能的最大值已经不超过当前答案可以提前退出 if (ans n - i || ans n / 2) break; unordered_mapstring, int slope_cnt; int same_point 0; // 记录和点i完全相同的点 int local_max 0; for (int j i 1; j n; j) { int dx points[j][0] - points[i][0]; int dy points[j][1] - points[i][1]; // 处理重复点 if (dx 0 dy 0) { same_point; continue; } // 对斜率进行约分和规范化 if (dx 0) { // 垂直的线 slope_cnt[v]; } else if (dy 0) { // 水平的线 slope_cnt[h]; } else { // 确保 dx 为正数来统一符号 if (dx 0) { dx -dx; dy -dy; } int g gcd(dy, dx); string key to_string(dy / g) / to_string(dx / g); slope_cnt[key]; } } // 计算当前基准点下的最大点数 for (auto p : slope_cnt) { local_max max(local_max, p.second); } // 最终结果为最大的斜率点数 重复点数 基准点自己 ans max(ans, local_max same_point 1); } return ans; } private: int gcd(int a, int b) { a abs(a); b abs(b); while (b) { int t b; b a % b; a t; } return a; } };