Google 电面

yangdaxian 发表于 2018-6-17 22:53
前面给过反例了～

之前写的时候没考虑小数，所以把判定范围扩大到了（0，2），输入格式是{左下角坐标，右上角坐标}

1. public class Main {
   
2.     public static void main(String[] args) {
   
3.         int[][] test= new int[][]{{0,0,1,1},{2,2,4,4},{1,1,5,5}};
   
4.         System.out.println(rectangleArea(test));
   
5.     }
   
6.     static class Interval{
   
7.         int lo, hi;
   
8.         List<Interval> vtc= new LinkedList<>();
   
9.         public Interval(int lo, int hi){this.lo=lo; this.hi=hi;}
   
10.     }
    
11.     public static boolean rectangleArea(int[][] rectangles) {
    
12.         Arrays.sort(rectangles, (a, b)-> a[0]==b[0]?a[1]-b[1]:a[0]-b[0]);
    
13.         List<Interval> list= new LinkedList<>();
    
14.         int s=0, e=0;
    
15.         for (int[] r: rectangles){
    
16.             if (!list.isEmpty() && r[0]<=e) e=Math.max(e, r[2]);
    
17.             else{
    
18.                 s=r[0];
    
19.                 e=r[2];
    
20.                 list.add(new Interval(s, e));
    
21.             }
    
22.             list.get(list.size()-1).vtc.add(new Interval(r[1], r[3]));
    
23.         }
    
24.         System.out.println(list.size());
    
25.         for (Interval hor: list){
    
26.             hor.vtc.sort((a,b)->(a.lo-b.lo));
    
27.             s=Integer.MIN_VALUE;
    
28.             e=0;
    
29.             for (Interval vtc: hor.vtc){
    
30.                 System.out.println(vtc.lo+" "+vtc.hi);
    
31.                 if (s!=Integer.MIN_VALUE && vtc.lo<=e) e=Math.max(e, vtc.hi);
    
32.                 else{
    
33.                     s=vtc.lo;
    
34.                     e=vtc.hi;
    
35.                 }
    
36.                 if (s>2) break;
    
37.                 if (s<=0 && e>=2) return true;
    
38.             }
    
39.         }
    
40.         return false;
    
41.     }
    
42. }

复制代码

谢谢分享！

FML 发表于 2018-6-18 02:37
之前写的时候没考虑小数，所以把判定范围扩大到了（0，2），输入格式是{左下角坐标，右上角坐标}
[mw_sh ...

前面提到的反例是{0,0,2,2},{2,2,4,4},{-1,4,0,5}这样的。（假设路是0～5），这个情况应该是没有挡住。

yangdaxian 发表于 2018-6-18 08:29
前面提到的反例是{0,0,2,2},{2,2,4,4},{-1,4,0,5}这样的。（假设路是0～5），这个情况应该是没有挡住。

改了一下，你再看看

1. public class Main {
   
2.     public static void main(String[] args) {
   
3.         int[][] test= new int[][]{{0,0,2,2},{2,2,4,4},{-1,4,0,5}};
   
4.         System.out.println(rectangleArea(test));
   
5.     }
   
6.     static class Interval{
   
7.         int lo, hi;
   
8.         List<Interval> vtc= new LinkedList<>();
   
9.         public Interval(int lo, int hi){this.lo=lo; this.hi=hi;}
   
10.     }
    
11.     public static boolean rectangleArea(int[][] rectangles) {
    
12.         Arrays.sort(rectangles, (a, b)-> a[0]==b[0]?a[1]-b[1]:a[0]-b[0]);
    
13.         List<Interval> list= new LinkedList<>();
    
14.         int s=0, e=0;
    
15.         for (int[] r: rectangles){
    
16.             if (!list.isEmpty() && r[0]<=e && overlap(list.get(list.size()-1).vtc, r[1], r[3])) e=Math.max(e, r[2]);
    
17.             else{
    
18.                 s=r[0];
    
19.                 e=r[2];
    
20.                 list.add(new Interval(s, e));
    
21.             }
    
22.             list.get(list.size()-1).vtc.add(new Interval(r[1], r[3]));
    
23.         }
    
24.         System.out.println(list.size());
    
25.         for (Interval hor: list){
    
26.             hor.vtc.sort((a,b)->(a.lo-b.lo));
    
27.             s=Integer.MIN_VALUE;
    
28.             e=0;
    
29.             for (Interval vtc: hor.vtc){
    
30.                 System.out.println(vtc.lo+" "+vtc.hi);
    
31.                 if (s!=Integer.MIN_VALUE && vtc.lo<=e) e=Math.max(e, vtc.hi);
    
32.                 else{
    
33.                     s=vtc.lo;
    
34.                     e=vtc.hi;
    
35.                 }
    
36.                 if (s>5) break;
    
37.                 if (s<=0 && e>=5) return true;
    
38.             }
    
39.         }
    
40.         return false;
    
41.     }
    
42.     public static boolean overlap(List<Interval> list, int s, int e){
    
43.         for (Interval i: list) if (Math.max(i.lo, s)<=Math.min(i.hi, e)) return true;
    
44.         return false;
    
45.     }
    
46. }

复制代码

aiyawocao 发表于 2018-6-14 12:24
1. 哇，好题～
2. nlgn (排序左下角坐标y值) 可以做.
3. 和 粒扣 的Merge Intervals + rectangle overlap ...

同意这个方法

楼主把分数降到100可否，新农每天攒1个，要好久才到120

FML 发表于 2018-6-18 13:08
改了一下，你再看看
[mw_shl_code=java,true]public class Main {
    public static void main(String ...

那您再试试{0,0,10,2},{3,3,4,4},{9,1,10,6}吧，应该是挡住了，但按照这个方法是没挡住...

dionwang 发表于 2018-6-18 13:51
同意这个方法

这个目前看是不可行的，因为无论怎么排序都无法保证能够找到所有重叠的长方形。讲真，我已经有点累了，之前的帖子大家已经讨论的挺清楚，目前这些排序方法都不可行，但还是不断有新同学了进来说可行，给的还是之前讨论过的方法...我又得一个一个回复。简直想求删帖暴风哭泣

yangdaxian 发表于 2018-6-19 00:08
这个目前看是不可行的，因为无论怎么排序都无法保证能够找到所有重叠的长方形。讲真，我已经有点累了，之 ...

哈哈哈哈哈哈lz不用一个个回复啦，认真看了前面的讨论都会有自己的判断的。

补充内容 (2018-6-19 01:09):
给lz加个米以表谢意

Anakin09 发表于 2018-6-19 01:08
哈哈哈哈哈哈lz不用一个个回复啦，认真看了前面的讨论都会有自己的判断的。

补充内容 (2018-6-19 01:09) ...

哈哈谢谢你！