ARTS #021
ARTS #021
ARTS is an activity initiated by
由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS) and persist for at least one year.
ARTS 021
This is article 21
Algorihm algorithm question
149. Max Points on a Line
Difficulty Hard
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example 1:
Example 2:
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
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
Solution
Language: C
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* }
*/
int maxPoints(struct Point* points, int pointsSize) {
}
My first thought when I saw this topic was to calculate the slope and use double to represent the slope. The first implementation was as follows:
int maxPoints11(struct point* points, int pointsSize) {
if (pointsSize == 0 || pointsSize == 1) {
return pointsSize;
}
double* averageOfLevels = (double*)malloc(sizeof(double) * (pointsSize * (pointsSize -1) / 2));
int index = 0;
for (int i = 0; i< pointsSize; i++) {
struct point pi = points[i];
for (int j = i+1; j< pointsSize; j++) {
struct point pj = points[j];
double x = pi.x - pj.x;
double y = pi.y - pj.y;
if (x ==0) {
averageOfLevels[index++] =INT_MAX;
}
else{
averageOfLevels[index] = ((double)y)/x;
index++;
}
}
}
//问题转换为数组中x最多相等的元素的个数
//先排序 使用快排
quicksort98(averageOfLevels, 0, index-1);
int max = 0;
int temp = 1;
double pd ;
double ld = INT_MIN;
for (int i = 0; i < index-1; i++) {
pd = averageOfLevels[i];
ld = averageOfLevels[i +1];
if (pd == ld) {
temp++;
}else{
if (temp > max) {
max = temp;
}
temp=1;
}
}
if (temp > max) {
max = temp;
}
//分界位n*(n-1)
int i = 1;
for (;i*(i-1)/2 <=max ; i++) {
if (i*(i-1)/2 ==max) {
break;
}
}
free(averageOfLevels);
return i;
}
void quicksort98(double* a, int left, int right) {
int i, j;
double t, temp;
if(left > right)
return;
temp = a[left]; //temp中存的就是基准数
i = left;
j = right;
while(i != j) { //顺序很重要，要先从右边开始找
while(a[j] >= temp && i < j)
j--;
while(a[i] <= temp && i < j)//再找右边的
i++;
if(i < j)//交换两个数在数组中的位置
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//最终将基准数归位
a[left] = a[i];
a[i] = temp;
quicksort98(a,left, i-1);//继续处理左边的，这里是一个递归的过程
quicksort98(a,i+1, right);//继续处理右边的 ，这里是一个递归的过程
}
The above implementation cannot pass when the test case has equal points, because the situation of equal points is not considered. The above is to calculate the slopes of all points, then sort them to find out the situation of long slopes, and then decompose the number of times the slope appears to calculate the number of long points.
One drawback of this implementation idea is that it first calculates the slope of all points and then performs the calculation. This makes it more difficult to deal with duplicate points.
An improvement to this method is to calculate the slope of the straight line between each point and other points, and then find the most optimal point. The implementation is as follows:
int maxPoints(struct Point* points, int pointsSize){
if (pointsSize == 0 || pointsSize == 1) {
return pointsSize;
}
double* averageOfLevels = (double*)malloc(sizeof(double) * (pointsSize * (pointsSize -1) / 2));
int max = 0;
for (int i = 0; i< pointsSize; i++) {
struct Point pi = points[i];
int smaple = 0;
int index = 0;
for (int j = 0; j< pointsSize; j++) {
if (i==j) {
continue;
}
struct Point pj = points[j];
double x = pi.x - pj.x;
double y = pi.y - pj.y;
if (x ==0) {
if (y==0) {//同一个点
smaple++;
}
else{
averageOfLevels[index++] =INT_MAX;
}
}
else{
averageOfLevels[index] = ((double)y)/x;
index++;
}
}
quicksort98(averageOfLevels, 0, index-1);
int temp = 1;
int maxtemp = 0;
double pd ;
double ld = INT_MIN;
for (int i = 0; i < index-1; i++) {
pd = averageOfLevels[i];
ld = averageOfLevels[i +1];
if (pd == ld) {
temp++;
}else{
if (temp > maxtemp) {
maxtemp = temp;
}
temp=1;
}
}
if (temp > maxtemp) {
maxtemp = temp;
}
if (index >0) {
maxtemp++;
}
maxtemp = maxtemp+ smaple;
if ( maxtemp > max) {
max = maxtemp;
}
free(averageOfLevels);
averageOfLevels = (double*)malloc(sizeof(double) * (pointsSize * (pointsSize -1) / 2));
}
free(averageOfLevels);
return max;
}
The above implementation fails when the test case is [[0,0],[94911151,94911150],[94911152,94911151]], because double represents the slope, and the slopes of these three points are the same. But these three points are not on a straight line.
[[0,0],[94911151,94911150],[94911152,94911151]] This test case should have been added later. Several C language codes found in the comment area could not pass this test case.
The difficulty of this problem is how to express the slope?
Later, I found that changing the slope expressed in double to long double can pass all test cases.
In fact, the long double representation is not an approximate representation, and there may be some buttons that cannot be passed. The slope of this question should be expressed as a fraction.
The complete code is as follows:
void quicksort98(long double* a, int left, int right) {
int i, j;
long double t, temp;
if(left > right)
return;
temp = a[left]; //temp中存的就是基准数
i = left;
j = right;
while(i != j) { //顺序很重要，要先从右边开始找
while(a[j] >= temp && i < j)
j--;
while(a[i] <= temp && i < j)//再找右边的
i++;
if(i < j)//交换两个数在数组中的位置
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//最终将基准数归位
a[left] = a[i];
a[i] = temp;
quicksort98(a,left, i-1);//继续处理左边的，这里是一个递归的过程
quicksort98(a,i+1, right);//继续处理右边的 ，这里是一个递归的过程
}
int maxPoints(struct Point* points, int pointsSize){
if (pointsSize == 0 || pointsSize == 1) {
return pointsSize;
}
long double* averageOfLevels = (long double*)malloc(sizeof(long double) * (pointsSize * (pointsSize -1) / 2));
int max = 0;
for (int i = 0; i< pointsSize; i++) {
struct Point pi = points[i];
int smaple = 0;
int index = 0;
for (int j = 0; j< pointsSize; j++) {
if (i==j) {
continue;
}
struct Point pj = points[j];
long double x = pi.x - pj.x;
long double y = pi.y - pj.y;
if (x ==0) {
if (y==0) {//同一个点
smaple++;
}
else{
averageOfLevels[index++] =INT_MAX;
}
}
else{
averageOfLevels[index] = ((long double)y)/x;
index++;
}
}
quicksort98(averageOfLevels, 0, index-1);
int temp = 1;
int maxtemp = 0;
long double pd ;
long double ld = INT_MIN;
for (int i = 0; i < index-1; i++) {
pd = averageOfLevels[i];
ld = averageOfLevels[i +1];
if (pd == ld) {
temp++;
}else{
if (temp > maxtemp) {
maxtemp = temp;
}
temp=1;
}
}
if (temp > maxtemp) {
maxtemp = temp;
}
if (index >0) {
maxtemp++;
}
maxtemp = maxtemp+ smaple;
if ( maxtemp > max) {
max = maxtemp;
}
free(averageOfLevels);
averageOfLevels = (long double*)malloc(sizeof(long double) * (pointsSize * (pointsSize -1) / 2));
}
free(averageOfLevels);
return max;
}
Review
https://dandan2009.github.io/2018/12/28/exposing-NSDictionary/
TIPS
There are many configuration methods on the Reveal configuration website, such as this: https://www.cnblogs.com/somethingWithiOS/p/6594496.html， Configuration is troublesome and requires changing the project file. Here is a simple method.
The pod configuration method is just one line without modifying the project file:
pod ‘RevealServer’, :configurations => [‘Debug’], :path => ‘./RevealServer’
:configurations means it is only valid under debug
Pod::Spec.new do |s|
s.name = "RevealServer"
s.version = "15.3.3"
s.summary = "RevealServer sdk"
s.description = <<-DESC
RevealServer
DESC
s.homepage = "http://www.baidu.com"
s.license = "MIT"
s.author = { "zzz 2019-1-5" => "" }
s.platform = :ios, "7.0"
s.ios.deployment_target = "7.0"
s.source = { :git => "http://www.baidu.com" }
s.source_files = "RevealServer.framework/**/*.h"
s.vendored_frameworks = 'RevealServer.framework'
end
For the complete demo, see: https://github.com/dandan2009/RevealServerDemo
Share
Not enough time, weak foundation, non-technical learning algorithm:
读完之后，下一步看什么
如果还想继续了解，可以从下面几个方向接着读。