資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中直線上的最大點數
假設我們有一個二維平面。我們必須找到位於同一條直線上的最大點數。如果點是這樣的：
那麼就有4個點
為了解決這個問題，我們將遵循以下步驟：
n := 點的數量，如果 n < 3，則返回 n
ans := 2
對於 i 從 1 到 n – 1 的範圍
count := 0
從索引 i 和 i – 1 獲取兩個點，這些是 p1、p2
如果 p1 和 p2 點相同，則
對於 j 從 0 到 n – 1 的範圍
如果 points[j].x = p1.x 並且 points[j].y = p1.y，則將 count 加 1
否則：
對於 j 從 0 到 n – 1 的範圍
p3 := 來自索引 j 的點
如果 p3.y – p2.y * p2.x – p1.x = p2.y – p1.y * p3.x – p2.x，則將 count 加 1
ans := ans 和 count 的最大值
返回 ans
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int n = points.size();
if(n<3)return n;
int ans = 2;
for(int i = 1;i<n;i++){
int count = 0;
lli x1 = points[i-1][0];
lli x2 = points[i][0];
lli y1 = points[i-1][1];
lli y2 = points[i][1];
if(x1 == x2 && y1 == y2){
for(int j =0;j<n;j++){
if(points[j][0] ==x1 && points[j][1] == y1)count++;
}
} else {
for(int j =0;j<n;j++){
int x3 = points[j][0];
int y3 = points[j][1];
if((y3-y2)*(x2-x1) == (y2-y1)*(x3-x2))count++ ;
}
}
ans = max(ans, count);
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};
cout << (ob.maxPoints(v));
}輸入
[{1,1},{3,2},{5,3},{4,1},{2,3},{1,5}]輸出
4
更新於：2020年5月26日
478 次瀏覽
廣告