الفنون رقم 021

ARTS هو نشاط بدأه 由左耳朵耗子--陈皓: قم بإجراء سؤال واحد على الأقل عن خوارزمية leetcode كل أسبوع، واقرأ مقالًا تقنيًا واحدًا على الأقل باللغة الإنجليزية وعلق عليه، وتعلم مهارة فنية واحدة على الأقل، وشارك المقالة مع الآراء والأفكار. (أي أن الخوارزمية والمراجعة والنصائح والمشاركة يشار إليها باسم ARTS) وتستمر لمدة عام واحد على الأقل.

الفنون 021

هذه المادة 21

سؤال خوارزمية الخوارزمية

149. أقصى عدد من النقاط على الخط

صعوبة صعبة

بمعلومية n نقطة على مستوى ثنائي الأبعاد، أوجد أكبر عدد من النقاط التي تقع على نفس الخط المستقيم.

مثال 1:

مثال 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

الحل

اللغة: ج

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 * }
 */
int maxPoints(struct Point* points, int pointsSize) {
    
}

أول ما خطر في ذهني عندما رأيت هذا الموضوع هو حساب الميل واستخدام الرقم المزدوج لتمثيل الميل. التنفيذ الأول كان على النحو التالي:

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]]، لأن المزدوج يمثل المنحدر، ومنحدرات هذه النقاط الثلاث هي نفسها. لكن هذه النقاط الثلاث ليست على خط مستقيم.

[[0,0],[94911151,94911150],[94911152,94911151]] كان من المفترض إضافة حالة الاختبار هذه لاحقًا. لم تتمكن العديد من رموز لغة C الموجودة في منطقة التعليق من اجتياز حالة الاختبار هذه.

صعوبة هذه المشكلة هي كيفية التعبير عن المنحدر؟

لاحقًا، وجدت أن تغيير الميل المعبر عنه بالمضاعف إلى المضاعف الطويل يمكن أن يجتاز جميع حالات الاختبار.

في الواقع، التمثيل المزدوج الطويل ليس تمثيلًا تقريبيًا، وقد تكون هناك بعض الأزرار التي لا يمكن تمريرها. ينبغي التعبير عن ميل هذا السؤال في صورة كسر.

الكود الكامل هو كما يلي:

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

مراجعة

https://dandan2009.github.io/2018/12/28/exposing-NSDictionary/

نصائح

هناك العديد من طرق التكوين على موقع تكوين Reveal، مثل: https://www.cnblogs.com/somethingWithiOS/p/6594496.html， التكوين مزعج ويتطلب تغيير ملف المشروع. هنا طريقة بسيطة.

طريقة تكوين pod هي سطر واحد فقط دون تعديل ملف المشروع:

جراب ‘RevealServer’، :configurations => [‘Debug’]، :path => ‘./RevealServer’

: التكوينات تعني أنها صالحة فقط تحت التصحيح

       
 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
  

للحصول على العرض التوضيحي الكامل، راجع: https://github.com/dandan2009/RevealServerDemo

شارك

الوقت غير كافي، الأساس الضعيف، خوارزمية التعلم غير التقنية: