Ən yaxşı görüş nöqtəsi LeetCode Həlli

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr

Mündəricat

Problem bəyanat

The Ən yaxşı görüş nöqtəsi LeetCode Həlli ikili grid verilir deyir grid ölçüdə m x n harada 1 Bir dostumuzun evini təyin, geri qayıtmaq istəyirik minimal ümumi səyahət məsafəsi harada ümumi səyahət məsafəsi dostların evləri ilə görüş yeri arasındakı məsafələrin cəmidir.

The ümumi səyahət məsafəsi cəmi kimi hesablanır Manhetten məsafəsi nöqtələr arasında.

Manhetten məsafəsi: kimi hesablanmış məsafə iki vektor arasındakı mütləq fərqlərin cəmi. yəni (x1,y1) və (x2,y2) nöqtələri arasındakı Manhetten məsafəsi belə hesablana bilər:

D= | x1-x2| + |y1-y2|

Yuxarıdakı misalda:

Input:

 grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]

Çıxış:

Explanation:

Given are three friends located at positions (0,0), (0,4), and (2,2).
The point (0,2) is an appropriate meeting point because the total travel distance is minimal i.e.  2 + 2 + 2 = 6.
Hence, we return 6.

Başqa bir misal:

Input:

 grid = [[1,1]]

Çıxış:

Həll yanaşması

Konsepsiya

Median koordinatlarda (midx,midy) yerləşən nöqtə, burada midx x-koordinat dəyərlərinin vektorunun medianı, midy isə y-koordinat qiymətlərinin vektorunun medianıdır. minimal Total səyahət məsafəsi.

sübut

Pin

Budur, qrafikdə,

Qoy a,b,c,d,e beş yer nöqtəsi və x cəmi səyahət məsafəsinin nöqtəsi olsun Məqsədimiz bütün nöqtələrdən x, yəni D-ə qədər olan məsafənin minimum olduğu yeri tapmaqdır.

1-ci hal: x (0,0) nöqtəsində yatsın D1= a+b+c+d+e

2-ci hal: a (a-ya ən yaxın) nöqtəsindən əvvəl x yatsın D2= (ax)+(bx)+(cx)+(dx)+(məs) D2= a+b+c+d+e – 5*x D2= D1 -5*x => D2

3-cü hal : e (e-yə ən yaxın) nöqtəsindən sonra x yatsın D3= (xa)+(xb)+(xc)+(xd)+(xe) D3= 5*x- a+b+c+d+e D3= 5*x – D1 [ Burada x 3-cü halda >>> x 2-ci halda] => D3>D2 [ 3-cü halda>2-ci halda ümumi səyahət məsafəsi]

4-cü hal: c nöqtəsindən sonra x yatsın (median nöqtəsi) D4= (ca)+(cb)+(cc)+(dc)+(ec) D4= a+b+c+d+e – 5*c D4 = a+b+d+e-4*c => D4 Case2]

Aydındır ki, yuxarıdakı 4 halı nəzərə alsaq, bütün nöqtələrdən mediana qədər ümumi məsafənin minimum olduğunu deyə bilərik.

Buna görə Median nöqtə minimum səyahət məsafəsinin nöqtəsidir.

Yanaşma

Vektorda '1' olan bütün mövqelərin x-koordinatlarını toplayın xkoordinatları.
Vektorda '1' olan bütün mövqelərin y-koordinatlarını toplayın ykoordinatları.
Bir vektor yaradın bütün mövqelərin cütü '1' fərqlərlə.
Cür xkoordinatları və ykoordinatları.
Medianı tapın orta in xkoordinatları və orta yəlaqələndirir [median = sıralanmış massivdə orta element, orta elementlərin ilk indeksini nəzərə alın]
Aradan keçin fərqlər və hər bir nöqtə yeri vasitəsilə Manhetten məsafəsini in mediana əlavə edin ümumi_səyahət_məsafəsi
Qayıtmaq ümumi_səyahət_məsafəsi.

Kodu

Ən yaxşı görüş nöqtəsi üçün C++ Həlli LeetCode Həll

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        vector<int>xcoordinates;
        vector<int>ycoordinates;
        //store pair of coordinate points
        vector<pair<int,int>>distpoints;
        
        // store all x-coordinates and y-coordinates in separate vectors O(nm)
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                if(grid[i][j]==1)
                {
                    xcoordinates.push_back(i);
                    ycoordinates.push_back(j);
                    distpoints.push_back({i,j});
                }
            }
        }
      
        //sort both vectors O(nlogn)
        sort(xcoordinates.begin(),xcoordinates.end());
        sort(ycoordinates.begin(),ycoordinates.end());
        
        //find mid element in both vectors  [Median coordinates]
        int index=0;
        int midx=0;
        int midy=0;
        if (xcoordinates.size()%2==0)
            index=xcoordinates.size()/2-1;
        else
            index=xcoordinates.size()/2;
        
        midx= xcoordinates[index];
        midy=ycoordinates[index];
        
        //Find manhatten distance O(n)
        int total_travel_distance=0;
        for(int i=0;i<xcoordinates.size();i++){
            total_travel_distance+=abs(distpoints[i].first-midx)+abs(distpoints[i].second-midy);
        
        }
        return total_travel_distance;
    }
};

Ən yaxşı görüş nöqtəsi üçün Python Həlli LeetCode Həll

class Solution(object):
    def minTotalDistance(self, grid):
        colvals = []
        rowvals = []
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    colvals.append(j)
                    rowvals.append(i)
        colvals.sort()
        rowvals.sort()
        
        result = 0
        total_travel_distance = (rowvals[len(rowvals)//2], colvals[len(colvals)//2])
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    result += abs(i-total_travel_distance[0]) + abs(j-total_travel_distance[1])
        return result