摘要:為了盡量保證右邊的點向左走,左邊的點向右走,那我們就應該去這些點中間的點作為交點。由于是曼哈頓距離,我們可以分開計算橫坐標和縱坐標,結果是一樣的。
Best Meeting Point
橫縱分離 復雜度A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.
For example, given three people living at (0,0), (0,4), and (2,2):
1 - 0 - 0 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0The point (0,2) is an ideal meeting point, as the total travel
distance of 2+2+2=6 is minimal. So return 6.
時間 O(NM) 空間 O(NM)
思路為了保證總長度最小,我們只要保證每條路徑盡量不要重復就行了,比如1->2->3<-4這種一維的情況,如果起點是1,2和4,那2->3和1->2->3這兩條路徑就有重復了。為了盡量保證右邊的點向左走,左邊的點向右走,那我們就應該去這些點中間的點作為交點。由于是曼哈頓距離,我們可以分開計算橫坐標和縱坐標,結果是一樣的。所以我們算出各個橫坐標到中點橫坐標的距離,加上各個縱坐標到中點縱坐標的距離,就是結果了。
代碼public class Solution { public int minTotalDistance(int[][] grid) { Listipos = new ArrayList (); List jpos = new ArrayList (); // 統(tǒng)計出有哪些橫縱坐標 for(int i = 0; i < grid.length; i++){ for(int j = 0; j < grid[0].length; j++){ if(grid[i][j] == 1){ ipos.add(i); jpos.add(j); } } } int sum = 0; // 計算縱坐標到縱坐標中點的距離,這里不需要排序,因為之前統(tǒng)計時是按照i的順序 for(Integer pos : ipos){ sum += Math.abs(pos - ipos.get(ipos.size() / 2)); } // 計算橫坐標到橫坐標中點的距離,這里需要排序,因為統(tǒng)計不是按照j的順序 Collections.sort(jpos); for(Integer pos : jpos){ sum += Math.abs(pos - jpos.get(jpos.size() / 2)); } return sum; } }
文章版權歸作者所有,未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64704.html
摘要:投射法復雜度思路將二維數(shù)組上的點,分別映射到一維的坐標上。然后將兩個結果相加。代碼分別放到一維上來做復雜度思路分別建立行和列的數(shù)組,用來存放,在某一行,或者某一列,一共有多少人在這一個位置上。同理,來處理行的情況。 LeetCode[296] Best Meeting Point A group of two or more people wants to meet and mini...
Problem A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance ...
Problem A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance ...
Problem Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required. Example 1: Input: [[0, 30],[5,...
摘要:關鍵字,,算法,,動態(tài)規(guī)劃,上關于主題的題目有四個這四個題目難度依次遞增。其中第四個問題是尋求一個通解,在給定和最大買賣次數(shù)的情況下,求最大收益。首先大致的解題方向是動態(tài)規(guī)劃,這個應該不難想到。之后就是怎么找到狀態(tài),怎么列狀態(tài)轉移方程。 關鍵字:leetcode,Best Time To Buy And Sell Stock,算法,algorithm,動態(tài)規(guī)劃,dynamic prog...
閱讀 2488·2021-08-11 11:16
閱讀 2926·2019-08-30 15:55
閱讀 3332·2019-08-30 12:53
閱讀 1568·2019-08-29 13:28
閱讀 3264·2019-08-28 18:17
閱讀 935·2019-08-26 12:19
閱讀 2466·2019-08-23 18:27
閱讀 695·2019-08-23 18:17