成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LeetCode] 296. Best Meeting Point

zzir / 939人閱讀

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 is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example:

Input: 

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 6 

Explanation: Given three people living at (0,0), (0,4), and (2,2):
             The point (0,2) is an ideal meeting point, as the total travel distance 
             of 2+2+2=6 is minimal. So return 6.
Solution 
class Solution {
    public int minTotalDistance(int[][] grid) {
        List x = new ArrayList<>();
        List y = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    x.add(i);
                    y.add(j);
                }
            }
        }
        Collections.sort(x);
        Collections.sort(y);
        int i = 0, j = x.size()-1, res = 0;
        while (i < j) {
            res += (x.get(j)-x.get(i)+y.get(j)-y.get(i));
            i++; j--;
        }
        return res;
    }
}

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72257.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 評論0 收藏0

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

    摘要：為了盡量保證右邊的點(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 ...

    王軍 評論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 評論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 評論0 收藏0

  • [Leetcode] Meeting Rooms 會議室

    摘要：排序法復(fù)雜度時(shí)間空間思路這題和很像，我們按開始時(shí)間把這些都給排序后，就挨個(gè)檢查是否有沖突就行了。有沖突的定義是開始時(shí)間小于之前最晚的結(jié)束時(shí)間。這里之前最晚的結(jié)束時(shí)間不一定是上一個(gè)的結(jié)束時(shí)間，所以我們更新的時(shí)候要取最大值。 Meeting Rooms Given an array of meeting time intervals consisting of start and end...

    jubincn 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<