Using string of slope after GCD as key


  • 0
    X

    To avoid the problem brought by using float slope as key, instead, I use string concatenated by a, b where k=a/b as key. Both a and b are divided by their GCD.

    /**
     * Definition for a point.
     * struct Point {
     *     int x;
     *     int y;
     *     Point() : x(0), y(0) {}
     *     Point(int a, int b) : x(a), y(b) {}
     * };
     */
    class Solution {
    public:
        int GCD(int a, int b){
            if(b==0) return a;
            return GCD(b, a%b);
        }
        int maxPoints(vector<Point>& points) {
            if(points.size()<2)
                return points.size();
    
            int globalMax=0;
            for(int i=0; i<points.size(); i++){
                int overlap=1;
                int localMax=0;
                unordered_map<string, int> myMap;
                for(int j=i+1; j<points.size(); j++){
                    if(points[i].x==points[j].x&&points[i].y==points[j].y){
                        overlap++;
                        continue;
                    }
                    int a=points[j].y-points[i].y;
                    int b=points[j].x-points[i].x;
                    int gcd=GCD(a, b);
                    a=gcd!=0? a/gcd:a;
                    b=gcd!=0? b/gcd:b;
                    myMap[string(to_string(a)+"_"+to_string(b))]=myMap[string(to_string(a)+"_"+to_string(b))]+1;
                }
    
                for(auto it=myMap.begin(); it!=myMap.end(); it++)
                    localMax=max(localMax, it->second);
                localMax+=overlap;
                globalMax=max(globalMax, localMax);
            }
            return globalMax;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.