狗家实习电面面经，感觉差不多跪了，来攒人品……

amazinglu 发表于 2018-3-5 02:45
第一题 O(n^2) 就可以

找到左上方的点(x1, y1) 和 右下方的点 (x2, y2)

pointSet的type不是Point[]嗎？
請問pointSet.x代表甚麼？

给一串数组代表坐标，求问这些坐标中能连成的长方形中，面积最大的那个是多大

假設長方行的邊皆與X軸或Y軸垂直或平行，不會有斜的長方形

1. import java.util.*;
   
2. public class RectangleMaxArea {
   
3.     public static void main(String[] args){
   
4.         Coordinate[] coordinates= new Coordinate[10];
   
5.         coordinates[0] = new Coordinate(-1,5);
   
6.         coordinates[1] = new Coordinate(-1,-3);
   
7.         coordinates[2] = new Coordinate(2,7);
   
8.         coordinates[3] = new Coordinate(2,3);
   
9.         coordinates[4] = new Coordinate(4,-1);
   
10.         coordinates[5] = new Coordinate(6,7);
    
11.         coordinates[6] = new Coordinate(6,3);
    
12.         coordinates[7] = new Coordinate(7,2);
    
13.         coordinates[8] = new Coordinate(2,-4);
    
14.         coordinates[9] = new Coordinate(6,-4);
    
15.         System.out.println(new RectangleMaxArea().getMaxArea(coordinates));
    
16.     }
    
17. 
    
18.     int getMaxArea(Coordinate[] coordinates){
    
19.         int maxArea = 0;
    
20.         Set<Coordinate> mySet = new HashSet<>();
    
21.         Collections.addAll(mySet,coordinates);
    
22.         if(mySet.size() < 4)
    
23.             return 0;
    
24.         int pointNum = coordinates.length;
    
25. 
    
26.         //we want to pick two diagonal points
    
27.         for(int i=0; i<pointNum; i++){
    
28.             for(int j=0; j<pointNum; j++){
    
29.                 // if we pick two points with
    
30.                 // 1. same coordinates or
    
31.                 // 2. they are on the same vertical line or
    
32.                 // 3. they are on the same horizontal line
    
33.                 // we skip them because we want to pick diagonal point of the rectangle
    
34.                 if(coordinates[i].equals(coordinates[j])
    
35.                         || coordinates[i].x == coordinates[j].x
    
36.                         || coordinates[i].y == coordinates[j].y)
    
37.                     continue;
    
38.                 int[] p1 = {coordinates[i].x, coordinates[i].y};
    
39.                 int[] p2 = {coordinates[j].x, coordinates[j].y};
    
40.                 int[] p3 = new int[2];
    
41.                 int[] p4 = new int[2];
    
42. 
    
43.                 if(mySet.contains(new Coordinate(p2[0],p1[1])) && mySet.contains(new Coordinate(p1[0],p2[1]))){
    
44.                     p3[0] = p2[0];
    
45.                     p3[1] = p1[1];
    
46.                     p4[0] = p1[0];
    
47.                     p4[1] = p2[1];
    
48.                     maxArea = Math.max(maxArea,getArea(p1,p3,p4));
    
49.                 }
    
50.             }
    
51.         }
    
52. 
    
53.         return maxArea;
    
54.     }
    
55. 
    
56.     int getArea(int[] p1, int[] p2, int[] p3){
    
57.         int edge1 = p1[0]-p2[0] + p1[1]-p2[1];
    
58.         int edge2 = p1[0]-p3[0] + p1[1]-p3[1];
    
59.         return edge1 * edge2;
    
60.     }
    
61. }
    
62. 
    
63. class Coordinate{
    
64.     int x;
    
65.     int y;
    
66.     Coordinate(int x, int y){
    
67.         this.x = x;
    
68.         this.y = y;
    
69.     }
    
70. 
    
71.     public boolean equals(Object p){
    
72.         Coordinate c = (Coordinate)p;
    
73.         return c.x == this.x && c.y == this.y;
    
74.     }
    
75. 
    
76.     public int hashCode(){
    
77.         final int prime = 997;
    
78.         return x + prime * y;
    
79.     }
    
80. }
    

复制代码