国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Best Meeting Point

morgan / 2364人閱讀

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

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.

Solution
public class Solution {
    /**
     * @param grid: a 2D grid
     * @return: the minimize travel distance
     */
    public int minTotalDistance(int[][] grid) {
        // Write your code here
        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);
                }
            }
        }
        return getMD(x) + getMD(y);
    }
    public int getMD(List nums) {
        // zhong dian is here
        Collections.sort(nums);
        int i = 0, j = nums.size()-1;
        int distance = 0;
        while (i < j) {
            distance += nums.get(j--) - nums.get(i++);
        }
        return distance;
    }
}

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

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/71398.html

相關文章

  • [LintCode/LeetCode] Meeting Rooms

    Problem Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings. Example Given intervals = [[0,30],[...

    Noodles 評論0 收藏0
  • [Leetcode] Best Meeting Point 最佳見面點

    摘要:為了盡量保證右邊的點向左走,左邊的點向右走,那我們就應該去這些點中間的點作為交點。由于是曼哈頓距離,我們可以分開計算橫坐標和縱坐標,結果是一樣的。 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
  • LeetCode[296] Best Meeting Point

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

    XUI 評論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 評論0 收藏0
  • [LintCode/LeetCode] Rotate Array

    Problem Given an array, rotate the array to the right by k steps, where k is non-negative. Example Example 1: Input: [1,2,3,4,5,6,7] and k = 3Output: [5,6,7,1,2,3,4]Explanation:rotate 1 steps to the r...

    chanthuang 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<