LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 对于每个点，找到一条经过该点，且经过点数量最多的直线。经过一个点，且斜率相同的直线必然唯一

经过 (x1, y1)、(x2, y2) 的两点式方程为
(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1)

• 由于斜率为浮点数，除法可能存在精度损失，因此采用 分子#分母 的字符串来存储斜率。为了保证相同斜率的字符串相同，应对分子分母约分。水平线斜率应表示为 0#1，垂直线斜率应表示为 1#0，如果斜率为负数则负号在前，如 -1#1
• 用辗转相除法求最大公约数，再用分子分母同时除以最大公约数即可

string getK(int x, int y) {
  int a = x;
  int b = y;
  while (b) {  // 辗转相除法
    int t = a % b;
    a = b;
    b = t;
  }  // a 即为 x 与 y 的最大公约数，任何数与 0 的最大公约数为本身
  x /= a;
  y /= a;
  return to_string(x) + "#" + to_string(y);
}
// x = 2  y = 1  => "2#1"
// x = 4  y = 2  => "2#1"
// x = 3  y = 0  => "1#0"
// x = 1  y = 2  => "1#2"
// x = 0  y = 3  => "0#1"
// x = 1  y = -1 => "-1#1"
// x = -1 y = 1  => "-1#1"
// x = -1 y = -2 => "1#2"
// x = -3 y = 0  => "1#0"
// x = 0  y = -3 => "0#1"

• 对于重复点，一点无法确定唯一直线，无法计算斜率，因此对相同的点需要额外计数。最终完整解法如下

class Solution {
 public:
  int maxPoints(vector<vector<int>>& points) {
    int sz = size(points);
    if (sz < 3) {
      return sz;
    }
    int res = 0;
    for (int i = 0; i < sz; ++i) {
      int cnt = 0;  // 与 points[i] 重合的点数量（不含 points[i] 自身）
      int mx = 0;  // 经过 points[i] 的所有直线中，经过最多的点数量
      unordered_map<string, int> m;  // 斜率为 k 的直线，经过点数量为 m[k]
      for (int j = i + 1; j < sz; ++j) {  // points[i] 与 points[j] 连成的直线
        int dx = points[j][0] - points[i][0];
        int dy = points[j][1] - points[i][1];
        if (dx == 0 && dy == 0) {  // 重合点
          ++cnt;
        } else {
          string k = getK(dx, dy);
          ++m[k];
          mx = max(mx, m[k]);
        }
      }
      res = max(res, mx + cnt + 1);  // 最大点数 + 重合点数 + 自身
    }
    return res;
  }

 private:
  string getK(int x, int y) {
    int a = x;
    int b = y;
    while (b) {
      int t = a % b;
      a = b;
      b = t;
    }
    x /= a;
    y /= a;
    return to_string(x) + "#" + to_string(y);
  }
};