ARTS #021

ARTS是由左耳朵耗子--陈皓发起的一个活动: 每周至少做一个leetcode的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的文章。（也就是Algorithm、Review、Tip、Share简称ARTS），至少坚持一年。

ARTS 021

这是第21篇

Algorihm 算法题

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) {
    
}

看到这个题目我的第一想法，就是计算斜率，用double表示斜率，第一次实现如下：

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);//继续处理右边的 ，这里是一个递归的过程
}

上面的实现当测试案例有相等的点时是通不过的，因为上面没有考虑相等点的情况，上面是把所有点的斜率计算完成之后，然后排序,找出斜率做多的情况，然后对斜率出现的次数进行分解计算出做多的点数。

这个实现想法有个缺点就是他是先计算出所有点组成的斜率，然后才进行计算。导致了出现重复点的时候比较难以处理。

对这个方法的改进是，计算每一个点的和其他点组成的直线斜率，然后找出最做的点，实现如下：

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;
}

上面的实现在测试案例是 [[0,0],[94911151,94911150],[94911152,94911151]]是通不过的，因为用double表示是斜率，这个三个点的斜率是一样的。但是这三个点是不在一条直线上的。

[[0,0],[94911151,94911150],[94911152,94911151]]这个测试案例应该是后来加上的，在评论区找的几个C语言的代码，都通不过这个测试案例。

这个问题的难点就在于斜率怎么表示？

后来发现把用double表示的斜率改为用long double表示，即可通过全部测试案例。

其实用long double表示也不是近似表示，应该也有通不过的按钮。这个题的斜率应该可以用分数表示。

完整的代码如下：

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

Reveal 配置网上有很多配置方法，比如这个：https://www.cnblogs.com/somethingWithiOS/p/6594496.html，配置比较麻烦，需要更改工程文件，这里介绍一个简单的方法。

pod配置方法，一行即可，不用修改工程文件：

pod ‘RevealServer’, :configurations => [‘Debug’], :path => ‘./RevealServer’

:configurations 意思是只有在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
   

完整demo参见： https://github.com/dandan2009/RevealServerDemo

时间不够，基础薄弱，非科班学习算法： 20110222559426