【LeetCode】窮舉法 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.

 翻譯：給定2D平面上的Ñ個點，找出位于同一直線上的最大點數。

算法思路

//注意：需要兩重循環，第一重循環周遊起始點 a，第二重循環周遊剩餘點 b

//當a與b不重合時，即可構成一條直線

//除點位于垂線上時需單獨考慮外（因斜率為無窮大），其它點均可根據公式得出斜率

//對于每個點a，建構 斜率->點數 的map

//b與a重合，以a起始的所有直線點數+1 (用dup統一相加)

//b與a不重合，a與b确定的直線點數+1

知識點補充

map用法

map是一種二叉樹的資料存儲結構。map内部自建一顆紅黑樹

map的特點:  （1）存儲Key-value對（2）支援快速查找，查找的複雜度基本是Log(N)（3）快速插入，快速删除，快速修改記

map<string,int>mp;//這裡的mp就是自己取的名字。定義map類型的變量mp

定義了一個map<int,int>FEL,怎麼給FEl指派（值為{2,1}{3,4}{4,5}）

FEL[2] = 1;

FEL[3] = 4;

FEL[4] = 5;

代碼詳解

class Solution {

public:

    intmaxPoints(vector<Point> &points) {

        intnum = points.size();

       if(num < 2)  //考慮特殊情況，點數為0和1時，傳回0或1

           return num;

        intret = 0;    //必須定義一個相對兩重循環的全局變量

       for(int i=0; i<num; i++)

        {

           int dup = 0,vcnt = 1; //重複與垂直(必須放for循環裡面，因每次i+1，都要重置參數開始計數)

           int curmax = 1; //必須初始化，否則輸入（0,0）（0,0）時，直接dup++，curmax未初始化取随機值了

           map<double,int> mp;

           for(int j=0; j<num; j++)

            {

               if(i!=j)//不是同一個點

               {

                   double x1 = points[i].x - points[j].x; //注意：x1，y1必須為double型，否則計算斜率時，強制轉換後會不準确

                   double y1 = points[i].y - points[j].y;

                   if(x1==0 && y1==0)

                        dup++;

                   else if(x1 == 0)

                         curmax = ++vcnt;

                   else

                   {

                        double k = y1/x1;

                        if(mp[k] == 0)//如果斜率對應的點數為0，則另其為2（說明之前沒有這樣斜率的點）

                            mp[k] = 2;

                        else

                            mp[k]++;

                       curmax =max(mp[k],curmax);

                   }

               }

            }

           ret = max(ret, curmax+dup);//沒輪完一輪（選取一個起始點，再與其他所有點連線判點數），判斷一回

        }

       return ret;

    }

};