成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

[Leetcode] Best Meeting Point 最佳見面點(diǎn)

王軍 / 3077人閱讀

摘要：為了盡量保證右邊的點(diǎn)向左走，左邊的點(diǎn)向右走，那我們就應(yīng)該去這些點(diǎn)中間的點(diǎn)作為交點(diǎn)。由于是曼哈頓距離，我們可以分開計(jì)算橫坐標(biāo)和縱坐標(biāo)，結(jié)果是一樣的。

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 - 0



The point (0,2) is an ideal meeting point, as the total travel
distance of 2+2+2=6 is minimal. So return 6.
橫縱分離 復(fù)雜度

時(shí)間 O(NM) 空間 O(NM)

思路

為了保證總長(zhǎng)度最小，我們只要保證每條路徑盡量不要重復(fù)就行了，比如1->2->3<-4這種一維的情況，如果起點(diǎn)是1，2和4，那2->3和1->2->3這兩條路徑就有重復(fù)了。為了盡量保證右邊的點(diǎn)向左走，左邊的點(diǎn)向右走，那我們就應(yīng)該去這些點(diǎn)中間的點(diǎn)作為交點(diǎn)。由于是曼哈頓距離，我們可以分開計(jì)算橫坐標(biāo)和縱坐標(biāo)，結(jié)果是一樣的。所以我們算出各個(gè)橫坐標(biāo)到中點(diǎn)橫坐標(biāo)的距離，加上各個(gè)縱坐標(biāo)到中點(diǎn)縱坐標(biāo)的距離，就是結(jié)果了。

代碼 
public class Solution {
    public int minTotalDistance(int[][] grid) {
        List ipos = new ArrayList();
        List jpos = new ArrayList();
        // 統(tǒng)計(jì)出有哪些橫縱坐標(biāo)
        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;
        // 計(jì)算縱坐標(biāo)到縱坐標(biāo)中點(diǎn)的距離，這里不需要排序，因?yàn)橹敖y(tǒng)計(jì)時(shí)是按照i的順序
        for(Integer pos : ipos){
            sum += Math.abs(pos - ipos.get(ipos.size() / 2));
        }
        // 計(jì)算橫坐標(biāo)到橫坐標(biāo)中點(diǎn)的距離，這里需要排序，因?yàn)榻y(tǒng)計(jì)不是按照j的順序
        Collections.sort(jpos);
        for(Integer pos : jpos){
            sum += Math.abs(pos - jpos.get(jpos.size() / 2));
        }
        return sum;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64704.html

相關(guān)文章

  • LeetCode[296] Best Meeting Point

    摘要：投射法復(fù)雜度思路將二維數(shù)組上的點(diǎn)，分別映射到一維的坐標(biāo)上。然后將兩個(gè)結(jié)果相加。代碼分別放到一維上來做復(fù)雜度思路分別建立行和列的數(shù)組，用來存放，在某一行，或者某一列，一共有多少人在這一個(gè)位置上。同理，來處理行的情況。 LeetCode[296] Best Meeting Point A group of two or more people wants to meet and mini...

    XUI 評(píng)論0 收藏0

  • [LintCode/LeetCode] Best Meeting Point

    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 ...

    morgan 評(píng)論0 收藏0

  • [LeetCode] 296. Best Meeting Point

    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 ...

    zzir 評(píng)論0 收藏0

  • [LeetCode] 253. Meeting Rooms II

    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,...

    mengera88 評(píng)論0 收藏0

  • Best Time To Buy And Sell Stock 買賣股票最佳時(shí)機(jī)

    摘要：關(guān)鍵字，，算法，，動(dòng)態(tài)規(guī)劃，上關(guān)于主題的題目有四個(gè)這四個(gè)題目難度依次遞增。其中第四個(gè)問題是尋求一個(gè)通解，在給定和最大買賣次數(shù)的情況下，求最大收益。首先大致的解題方向是動(dòng)態(tài)規(guī)劃，這個(gè)應(yīng)該不難想到。之后就是怎么找到狀態(tài)，怎么列狀態(tài)轉(zhuǎn)移方程。 關(guān)鍵字：leetcode，Best Time To Buy And Sell Stock，算法，algorithm，動(dòng)態(tài)規(guī)劃，dynamic prog...

    elliott_hu 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<