2001. Number of Pairs of Interchangeable Rectangles - Medium

前往題目

想法

• 只能往後找相同ratio

思路

關鍵點是遇到當前ratio，直接加上之前走過的相同ratio數量

1. 走過所有num
2. 計算當前ratio
3. 加上這個ratio的數量(因為是往前搭配)，並且更新此ratio的數量

還有另一種做法是利用數學公式，但那樣就太specific的解法，所以選擇general的

Code

class Solution {
    public long interchangeableRectangles(int[][] rectangles) {
        long res = 0;
        // Ratio -> count
        Map<Double, Long> map = new HashMap<>(); 

        for (int[] rect : rectangles) {
            // Current ratio, cast to double first then do the division
            double a = rect[0];
            double b = rect[1];
            double ratio = (double) a / b;

            if (map.containsKey(ratio)) {
                res += map.get(ratio);
            }
            map.put(ratio, map.getOrDefault(ratio, 0L) + 1);
        }

        return res;
    }
}