谷歌近期新题 - leetcode 已收录

Job Hunting Interview
, ,
1 
  1. Minimum Area Rectangle

  1. Minimum Area Rectangle II
2

963 好像两种
一种是3个相邻点组成的向量乘积为0，另一种是找同中心点同长度吧？

3

能一种解出来就不错了，详细说说你认为的最优解吧

4

963 看下 vote most 的解法吧，

  1. Two diagonals of a rectangle bisect each other, and are of equal length.
  2. The map’s key is String including diagonal length and coordinate of the diagonal center; map’s value is the index of two points forming the diagonal.

代码如下

class Solution {
    public double minAreaFreeRect(int[][] points) {
        int len = points.length;
        double res = Double.MAX_VALUE;
        if (len < 4) return 0.0;
        Map<String, List<int[]>> map = new HashMap<>(); // int[] is the index of two points forming the diagonal
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                long dis = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                double centerX = (double)(points[j][0] + points[i][0])/2; // centerX and centerY is the coordinate of the diagonal center
                double centerY = (double)(points[j][1] + points[i][1])/2;
                String key = "" + dis + "+" + centerX + "+" + centerY; // key includes the length of the diagonal and the coordinate of the diagonal center
                if (map.get(key) == null) map.put(key, new ArrayList<int[]>());
                map.get(key).add(new int[]{i,j});
            }
        }
        for (String key : map.keySet()) {
            if (map.get(key).size() > 1) {  
                List<int[]> list = map.get(key);
                for (int i = 0; i < list.size(); i++) { // there could be multiple rectangles inside
                    for (int j = i + 1; j < list.size(); j++) {
                        int p1 = list.get(i)[0]; // p1, p2 and p3 are the three vertices of a rectangle
                        int p2 = list.get(j)[0];
                        int p3 = list.get(j)[1];
                        // len1 and len2 are the length of the sides of a rectangle
                        double len1 = Math.sqrt((points[p1][0] - points[p2][0]) * (points[p1][0] - points[p2][0]) +  (points[p1][1] - points[p2][1]) * (points[p1][1] - points[p2][1])); 
                        double len2 = Math.sqrt((points[p1][0] - points[p3][0]) * (points[p1][0] - points[p3][0]) +  (points[p1][1] - points[p3][1]) * (points[p1][1] - points[p3][1]));
                        double area = len1 * len2; 
                        res = Math.min(res, area);
                    }
                }
            }
        }
        return res == Double.MAX_VALUE ?  0.0 : res;
    }
}

这里对 double 的使用我觉得可能会出问题，精度的问题

5

这个map的key我觉得不要用string，自建一个class，里面有对角线长度，中心坐标的x和y，并override equals，保证double的equals。string的效率也不高。

1 Like
6

我感觉也是第二种好，不过当时打contest也没做出来。向量操作忘光了。

不过说实话老师你觉得compute自己custom class的hashcode速度咋样呀？我记得在leetcode做题的时候偶尔用过，感觉也没快多少。。。

另外其实没必要担心中心点的精度，看到有些解法中心点没有除以2直接拿去当key了。

7

额，你要咋判断毫秒的区别

8

你没理解我说的，对double的存储复习一下

9

我的意思是他没有用double，直接这样了：

        long dis = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
        int cx = points[j][0] + points[i][0];
        int cy = points[j][1] + points[i][1];
        String key = "" + dis + "+" + cx + "+" + cy;

确实我对速度的判断其实是看beat了多少，哈哈哈，太不严谨了

10

你的代码怎么变成int了？