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

資訊專欄INFORMATION COLUMN

[LintCode] Build Post Office I & II

1treeS / 1217人閱讀

Build Post Office Problem

Given a 2D grid, each cell is either an house 1 or empty 0 (the number zero, one), find the place to build a post office, the distance that post office to all the house sum is smallest. Return the smallest distance. Return -1 if it is not possible.

Notice

You can pass through house and empty.
You only build post office on an empty.

Example

Given a grid:

0 1 0 0
1 0 1 1
0 1 0 0
return 6. (Placing a post office at (1,1), the distance that post office to all the house sum is smallest.)

Solution DP

會超時。

public class Solution {
    public class Node {
        int x;
        int y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;
        ArrayList house = new ArrayList<>();
        ArrayList empty = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    house.add(new Node(i, j));
                }
                else {
                    empty.add(new Node(i, j));
                }
            }
        }
        if (empty.size() == 0) return -1;
        int min = Integer.MAX_VALUE;
        for (Node node: empty) {
            min = Math.min(min, helper(house, node));
        }
        return min;
    }
    private int helper(ArrayList house, Node node) {
        int dist = 0;
        for (Node cur: house) {
            dist += Math.abs(cur.x - node.x) + Math.abs(cur.y - node.y);
        }
        return dist;
    }
}
public class Solution {
    public int shortestDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid == null || m == 0 || n == 0) return -1;
        List x = new ArrayList<>();
        List y = new ArrayList<>();
        List xSum = new ArrayList<>();
        List ySum = new ArrayList<>();
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    x.add(i);
                    y.add(j);
                }
            }
        }
        Collections.sort(x);
        Collections.sort(y);
        int total = x.size();
        xSum.add(0);
        ySum.add(0);
        for (int i = 1; i <= total; i++) {
            xSum.add(xSum.get(i-1) + x.get(i-1));
            ySum.add(ySum.get(i-1) + y.get(i-1));
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    int costX = getCost(x, xSum, i, total);
                    int costY = getCost(y, ySum, j, total);
                    if (costX + costY < res) res = costX + costY;
                }
            }
        }
        return res;
        
    }
    public int getCost(List list, List sum, int pos, int size) {
        if (size == 0) return 0;
        if (list.get(0) > pos) return sum.get(size) - pos * size;
        int l = 0, r = size-1;
        while (l + 1 < r) {
            int mid = l + (r-l)/2;
            if (list.get(mid) <= pos) l = mid;
            else r = mid-1;
        }
        int index = 0;
        if (list.get(r) <= pos) index = r;
        else index = l;
        return sum.get(size) - sum.get(index+1) - pos * (size-index-1) + pos * (index+1) - sum.get(index+1);
    }
}
Build Post Office II Problem

Given a 2D grid, each cell is either a wall 2, an house 1 or empty 0 (the number zero, one, two), find the place to build a post office, the distance that post office to all the house sum is smallest. Return the smallest distance. Return -1 if it is not possible.

Notice

You cannot pass through wall and house, but can pass through empty.
You only build post office on an empty.

Example

Given a grid:

0 1 0 0 0
1 0 0 2 1
0 1 0 0 0

return 8, You can build at (1,1). (Placing a post office at (1,1), the distance that post office to all the house sum is smallest.)

Challenge

Solve this problem within O(n^3) time.

Solution
public class Solution {
    class Node {
        int x, y, dist;
        public Node(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;
        int m = grid.length;
        int n = grid[0].length;
        List house = new ArrayList<>();
        List empty = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) house.add(new Node(i, j, 0));
                else if (grid[i][j] == 0) empty.add(new Node(i, j, 0));
            }
        }
        if (empty.size() == 0) return -1;
        int k = house.size();
        int[][][] distance = new int[k][m][n];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < m; j++) {
                Arrays.fill(distance[i][j], Integer.MAX_VALUE);
            }
        }
        boolean[][] visited;
        for (int i = 0; i < k; i++) {
            visited = new boolean[m][n];
            getDistance(house.get(i), distance, i, grid, visited);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    int sum = 0;
                    for (int l = 0; l < k; l++) {
                        if (distance[l][i][j] == Integer.MAX_VALUE) {
                            sum = Integer.MAX_VALUE;
                            break;
                        }
                        sum += distance[l][i][j];
                    }
                    min = Math.min(min, sum);
                }
            }
        }
        if (min == Integer.MAX_VALUE) return -1;
        return min;
    }
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    private void getDistance(Node cur, int[][][] distance, int k, int[][] grid, boolean[][] visited) {
        Queue q = new LinkedList();
        q.offer(cur);
        visited[cur.x][cur.y] = true;
        int m = grid.length;
        int n = grid[0].length;
        while (!q.isEmpty()) {
            Node now = q.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = now.x + dx[i];
                int nextY = now.y + dy[i];
                if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && grid[nextX][nextY] == 0 && !visited[nextX][nextY]) {
                    distance[k][nextX][nextY] = now.dist + 1;
                    q.add(new Node(nextX, nextY, now.dist+1));
                    visited[nextX][nextY] = true;
                }
            }
        }
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66054.html

相關文章

  • [LintCode] Segment Tree Query I &amp; Segment Tree

    摘要:題目是要查詢到這個區間內某一點的。值是從最底層的子節點值里取最大值。因此,不用太復雜,遞歸就可以了。與所不同的是,對所給區間內的元素個數求和,而非篩選。這樣就會出現的情況,視作本身處理。 Segment Tree Query Problem For an integer array (index from 0 to n-1, where n is the size of this ar...

    vibiu 評論0 收藏0
  • [LintCode] Segment Tree Build &amp; Segment Tree B

    摘要:唯一需要注意的就是的賦值取左右子樹的的較大值,最后一層的獨立結點的為對應數組中的值。 Segment Tree Build I Problem The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment / interv...

    honhon 評論0 收藏0
  • [LintCode/LeetCode] Subsets &amp; Subsets II

    Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

    tracy 評論0 收藏0
  • [LintCode/LeetCode] Single Number I &amp; II [位運算]

    摘要:整個過程相當于,直接在和里去掉既是又是的。所以最后返回的,一定是只出現過一次的,而出現兩次的都在里,出現三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

    Drinkey 評論0 收藏0
  • [LintCode] Spiral Matrix I &amp; Spiral Matrix II

    摘要:如果不在前兩個循環之后的話,那么那多余的一行或一列就會被加入數組兩次,造成錯誤的結果。解法和一樣,只是簡化了,甚至可以用一樣的方法去做,只要把也換成。使用,以及最后討論是否為奇數以判斷中間是否有一個未循環的點,是這道題的兩個有趣的地方。 Spiral Matrix I Problem Given a matrix of m x n elements (m rows, n columns...

    tuantuan 評論0 收藏0

發表評論

0條評論

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