牛客网算法编程题--物流中转站 解答

物流中转站

题目描述

Shopee物流会有很多个中转站。在选址的过程中,会选择离用户最近的地方建一个物流中转站。

假设给你一个二维平面网格,每个格子是房子则为1,或者是空地则为0。找到一个空地修建一个物流中转站,使得这个物流中转站到所有的房子的距离之和最小。 能修建,则返回最小的距离和。如果无法修建,则返回 -1。

若范围限制在100*100以内的网格,如何计算出最小的距离和?

当平面网格非常大的情况下,如何避免不必要的计算?

输入描述

4
0 1 1 0
1 1 0 1
0 0 1 0
0 0 0 0

先输入方阵阶数,然后逐行输入房子和空地的数据,以空格分隔。

输出描述

8

能修建,则返回最小的距离和。如果无法修建,则返回 -1。

相信大家都会使用二维数组和循环遍历,下面我讲这道题将使用大家一些比较不熟悉或者陌生的知识

Lambda Stream+静态内部类

希望大家看完以后可以学会将stream和内部类应用到项目中,也可以进一步学习一下Lambda,时很有必要的

步入正题

思路

使用封装对象Point存放点的坐标,再把他们存放到集合List中(ArrayList读取效率高),编写求距离和的函数和求两点距离和的函数,最后通过stream和Lambda组合获得距离最小值

1562076624237

关键代码就一行

        int re = noBuildings.stream()
            .map(x->distanceSum(x.x,x.y))
            .min(Integer::compareTo)
            .get();

这段代码中stream就是获取一个流对象,map把参数x与求解距离总和的方法映射得到该方法的返回值min就是在这些返回值中获得最小的值(使用了Integer中的ComparaTo方法 最后通过get获得这个最小值)

如果又看不懂的可以看一下我的另外一篇关于Lambda和Stream的博客

我们在输入点的时候就把点封装add到集合中,我们只需要从没有建筑的点中查取出与空地的距离的最小值

源代码:

    private static List<Point> buildings;
    public static void main(String[] args) {
        buildings = new ArrayList<>();
        List<Point> noBuildings = new ArrayList<>();
        Scanner scanner = new Scanner(System.in);
        int l = scanner.nextInt();
        int[][] sites = new int[l][l];
        scanner.nextLine();
        for(int i=0;i<l;i++){
            String[] str;
            str = scanner.nextLine().split(" ");
                for(int m=0;m<l;m++){
                    sites[i][m] = Integer.parseInt(str[m].trim());
                    if(sites[i][m]==0){
                        noBuildings.add(new Point(i,m));
                    }else{
                        buildings.add(new Point(i,m));
                    }
                }
        }
        if(noBuildings.isEmpty()){
            System.out.println("-1");
            return;
        }
        int re = noBuildings.stream().map(x->distanceSum(x.x,x.y)).min(Integer::compareTo).get();
        System.out.println(re);
    }
    private static int distanceSum(int row, int line) {
        int sum = 0;
        for (Point point : buildings) {
            sum+=twoPoint(row,line,point.x,point.y);
        }
        return sum;
    }
    private static int twoPoint(int row1,int line1,int row2,int line2){
        return Math.abs(row2-row1)+Math.abs(line2-line1);
    }

    private static class Point{
        private int x;
        private int y;
        Point(int row,int line){
            x=row;
            y=line;
        }
        public void setX(int x) {
            this.x = x;
        }
        public void setY(int y) {
            this.y = y;
        }
    }
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/90a1be19.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!