C++實現LeetCode(149.共線點個數)
[LeetCode] 149. Max Points on a Line 共線點個數
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example 1:
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
Example 2:
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
這道題給了我們一堆二維點，然后讓求最大的共線點的個數，根據初中數學可以知道，兩點確定一條直線，而且可以寫成 y = ax + b 的形式，所有共線的點都滿足這個公式。所以這些給定點兩兩之間都可以算一個斜率，每個斜率代表一條直線，對每一條直線，帶入所有的點看是否共線并計算個數，這是整體的思路。但是還有兩點特殊情況需要考慮，一是當兩個點重合時，無法確定一條直線，但這也是共線的情況，需要特殊處理。二是斜率不存在的情況，由于兩個點 (x1, y1) 和 (x2, y2) 的斜率k表示為 (y2 - y1) / (x2 - x1)，那么當 x1 = x2 時斜率不存在，這種共線情況需要特殊處理。這里需要用到 TreeMap 來記錄斜率和共線點個數之間的映射，其中第一種重合點的情況假定其斜率為 INT_MIN，第二種情況假定其斜率為 INT_MAX，這樣都可以用 TreeMap 映射了。還需要頂一個變量 duplicate 來記錄重合點的個數，最后只需和 TreeMap 中的數字相加即為共線點的總數，但這種方法現在已經無法通過 OJ 了，代碼可以參見評論區(qū)八樓。
由于通過斜率來判斷共線需要用到除法，而用 double 表示的雙精度小數在有的系統(tǒng)里不一定準確，為了更加精確無誤的計算共線，應當避免除法，從而避免無線不循環(huán)小數的出現，那么怎么辦呢，這里把除數和被除數都保存下來，不做除法，但是要讓這兩數分別除以它們的最大公約數，這樣例如8和4，4和2，2和1，這三組商相同的數就都會存到一個映射里面，同樣也能實現目標，而求 GCD 的函數如果用遞歸來寫那么一行就搞定了，叼不叼，這個方法能很好的避免除法的出現，算是犧牲了空間來保證精度吧，參見代碼如下：
C++ 解法一：
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int res = 0;
for (int i = 0; i < points.size(); ++i) {
map<pair<int, int>, int> m;
int duplicate = 1;
for (int j = i + 1; j < points.size(); ++j) {
if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
++duplicate; continue;
}
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
int d = gcd(dx, dy);
++m[{dx / d, dy / d}];
}
res = max(res, duplicate);
for (auto it = m.begin(); it != m.end(); ++it) {
res = max(res, it->second + duplicate);
}
}
return res;
}
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
};
Java 解法一：
class Solution {
public int maxPoints(int[][] points) {
int res = 0;
for (int i = 0; i < points.length; ++i) {
Map<Map<Integer, Integer>, Integer> m = new HashMap<>();
int duplicate = 1;
for (int j = i + 1; j < points.length; ++j) {
if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
++duplicate; continue;
}
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
int d = gcd(dx, dy);
Map<Integer, Integer> t = new HashMap<>();
t.put(dx / d, dy / d);
m.put(t, m.getOrDefault(t, 0) + 1);
}
res = Math.max(res, duplicate);
for (Map.Entry<Map<Integer, Integer>, Integer> e : m.entrySet()) {
res = Math.max(res, e.getValue() + duplicate);
}
}
return res;
}
public int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
}
令博主驚奇的是，這道題的 OJ 居然容忍 brute force 的方法通過，博主認為下面這種 O(n3) 的解法之所以能通過 OJ，可能還有一個原因就是用了比較高效的判斷三點共線的方法。一般來說判斷三點共線有三種方法，斜率法，周長法，面積法 。而其中通過判斷叉積為零的面積法是墜好的。比如說有三個點 A(x1, y1)、B(x2, y2)、C(x3, y3)，那么判斷三點共線就是判斷下面這個等式是否成立：
行列式的求法不用多說吧，不會的話回去翻線性代數，當初少打點刀塔不就好啦~
C++ 解法二：
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int res = 0;
for (int i = 0; i < points.size(); ++i) {
int duplicate = 1;
for (int j = i + 1; j < points.size(); ++j) {
int cnt = 0;
long long x1 = points[i][0], y1 = points[i][1];
long long x2 = points[j][0], y2 = points[j][1];
if (x1 == x2 && y1 == y2) {++duplicate; continue;}
for (int k = 0; k < points.size(); ++k) {
int x3 = points[k][0], y3 = points[k][1];
if (x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3 == 0) {
++cnt;
}
}
res = max(res, cnt);
}
res = max(res, duplicate);
}
return res;
}
};
Java 解法二：
class Solution {
public int maxPoints(int[][] points) {
int res = 0, n = points.length;
for (int i = 0; i < n; ++i) {
int duplicate = 1;
for (int j = i + 1; j < n; ++j) {
int cnt = 0;
long x1 = points[i][0], y1 = points[i][1];
long x2 = points[j][0], y2 = points[j][1];
if (x1 == x2 && y1 == y2) {++duplicate;continue;}
for (int k = 0; k < n; ++k) {
int x3 = points[k][0], y3 = points[k][1];
if (x1*y2 + x2*y3 + x3*y1 - x3*y2 - x2*y1 - x1 * y3 == 0) {
++cnt;
}
}
res = Math.max(res, cnt);
}
res = Math.max(res, duplicate);
}
return res;
}
}
Github 同步地址：
https://github.com/grandyang/leetcode/issues/149
類似題目：
參考資料：
https://leetcode.com/problems/max-points-on-a-line/
https://leetcode.com/problems/max-points-on-a-line/discuss/221044/
https://leetcode.com/problems/max-points-on-a-line/discuss/47113/A-java-solution-with-notes
到此這篇關于C++實現LeetCode(149.共線點個數)的文章就介紹到這了,更多相關C++實現共線點個數內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
通過頭文件的形式直接調用自定義的函數，從而免去對函數的原型進行聲明，本文就詳細的介紹一下VS2019中在源文件中如何使用自己寫的頭文件，感興趣的可以了解一下2021-09-09
這篇文章主要給大家介紹了關于C語言字符/字符串的相關函數，文中通過示例代碼總結的非常詳細，對大家學習或者使用C語言具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2021-07-07
這篇文章主要介紹了C++之重載 重定義與重寫用法詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-09-09
大家好，本篇文章主要講的是C語言對冒泡排序進行升級介紹，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
詳解Visual Studio 2019(VS2019) 基本操作
這篇文章主要介紹了詳解Visual Studio 2019(VS2019) 基本操作，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-03-03
這篇文章主要為大家詳細介紹了如何使用C++自定義實現比較器,文中的示例代碼講解詳細,具有一定的借鑒價值,感興趣的小伙伴可以跟隨小編一起學習一下2024-01-01
在C/C++中使用庫的技術,庫主要分為兩種類型：靜態(tài)庫和動態(tài)庫,本文主要介紹了C++中靜態(tài)庫與動態(tài)庫的使用示例,具有一定的參考價值,感興趣的可以了解一下2023-09-09
這篇文章主要介紹了VC判斷進程是否具有administrator權限的方法,在Windows應用程序設計中具有一定的實用價值,需要的朋友可以參考下2014-10-10
這篇文章主要為大家詳細介紹了C語言實現學生宿舍信息管理系統(tǒng)課程設計，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要為大家詳細介紹了C語言實現簡單猜拳小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-03-03