2013. Detect Squares - Medium

前往題目

想法

• 確定對角線
• 四邊等長
• 四個角90°

思路

沒想到對角線就可以確定另外兩個點😭

Add

1. 加入列表，並且紀錄個數

Count

1. 疊代列表中所有的點，根據傳入的點算x1 - x2 == y1 - y2，如果是的話就代表這兩點可以繪製出正方形
2. 確認另外兩點是否在列表中
3. 存在就把個數相乘，因為重複的點可再和其他點組成正方形，即便位置一模一樣(題目設定)

Code

class DetectSquares {

    private List<int[]> pointList; // 紀錄點
    private Map<String, Integer> pointCount; // 紀錄每個點的個數

    public DetectSquares() {
        pointList = new ArrayList<>();
        pointCount = new HashMap<>();
    }

    public void add(int[] point) {
        String s = point[0] + "," + point[1];
        if (pointCount.containsKey(s)) {
            // 有的話直接個數+1
            pointCount.put(s, pointCount.get(s) + 1);
        } else {
            // 沒有的話初始化個數以及加入列表
            pointCount.put(s, 1);
            pointList.add(point);
        }
    }

    public int count(int[] point) {
        int curX = point[0];
        int curY = point[1];
        int res = 0;

        // Iterate all the points
        for (int[] p : pointList) {
            // 確認與點p可以形成正方形，以及面積非0
            if (Math.abs(p[0] - curX) == Math.abs(p[1] - curY) && p[0] != curX && p[1] != curY) {
                // 推算出另外兩個點
                String point1 = curX + "," + p[1];
                String point2 = p[0] + "," + curY;
                // 有的話就相乘，沒有的時候就為0
                res += pointCount.getOrDefault(point1, 0) * pointCount.getOrDefault(point2, 0) * pointCount.get(p[0] + "," + p[1]);
            }
        }
        return res;
    }
}