php 解法, 执行用时: 636 ms, 内存消耗: 142.3 MB, 提交时间: 2023-09-14 01:08:07

class Solution {
    /**
     * @param Integer[][] $rectangles
     * @return Integer
     */
    function interchangeableRectangles($rectangles) {
        $total = 0;
        //获取相同倍数的数字
        foreach($rectangles as $value){
            $key = $value[1]/$value[0];
            $key = (string)$key;
            $arr[$key]++;
            //每遇到相同倍数的就添加组合倍数
            $total = $total + ($arr[$key]-1);
        }
        return $total;
    }
}

python3 解法, 执行用时: 200 ms, 内存消耗: 60.6 MB, 提交时间: 2023-09-14 01:07:16

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        from math import gcd
        n = len(rectangles)
        d = {}
        cnt = 0
        for w, h in rectangles:
            _gcd = gcd(w, h)
            key = (w // _gcd, h // _gcd)
            if key in d:
                cnt += d[key]
                d[key] += 1
            else:
                d[key] = 1
        return cnt
        # return sum(1 for i in range(n) for j in range(i + 1, n) 
        #     if rectangles[i][0] * rectangles[j][1] == rectangles[i][1] * rectangles[j][0])

cpp 解法, 执行用时: 368 ms, 内存消耗: 137.5 MB, 提交时间: 2023-09-14 01:06:50

class Solution {
public:
    using LL = long long;

    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    LL interchangeableRectangles(vector<vector<int>>& rectangles) {
        unordered_map<LL, LL> map;
        constexpr LL BASE = (LL)1e8;

        for (auto& p : rectangles) {
            int x = p[0], y = p[1];
            int div = gcd(x, y);
            // 使用十进制压缩 [x, y]
            LL frac = (x / div) * BASE + (y / div);
            map[frac]++;
        }

        LL res = 0L;
        for (auto& [k, v] : map) {
            res += v * (v - 1) / 2;
        }

        return res;
    }
};

java 解法, 执行用时: 55 ms, 内存消耗: 89.8 MB, 提交时间: 2023-09-14 01:06:25

class Solution {
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    public long interchangeableRectangles(int[][] arr) {
        Map<Long, Long> map = new HashMap<>();
        final long BASE = (long)1e8;
        
        for (var p : arr) {
            int a = p[0], b = p[1];
            int div = gcd(a, b);
            // String frac = (a / div) + "/" + (b / div);
            // 使用数字压缩 [x, y] 比较快
            long frac = (a / div) * BASE + (b / div);
            map.put(frac, map.getOrDefault(frac, 0L) + 1);
        }
        
        long sum = 0L;
        for (var x : map.values()) {
            sum += x * (x - 1) / 2;
        }
        
        return sum;
    }
}

golang 解法, 执行用时: 268 ms, 内存消耗: 19.8 MB, 提交时间: 2023-09-14 01:05:35

func interchangeableRectangles(rectangles [][]int) (ans int64) {
	cnt := map[[2]int]int64{}
	for _, p := range rectangles {
		// 计算 w/h 的最简分数，计入哈希表
		w, h := p[0], p[1]
		g := gcd(w, h)
		cnt[[2]int{w / g, h / g}]++
	}
	for _, m := range cnt {
		ans += m * (m - 1) / 2
	}
	return
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

rust 解法, 执行用时: 60 ms, 内存消耗: 11.5 MB, 提交时间: 2023-09-14 01:05:15

use std::collections::HashMap;
impl Solution {
    pub fn interchangeable_rectangles(rectangles: Vec<Vec<i32>>) -> i64 {
        fn simplify(m0: i32, n0: i32) -> (i32, i32) {
            let (mut m, mut n) = if m0 > n0 { (m0, n0) } else { (n0, m0) };
            let mut r = m % n;
            while r != 0 {
                m = n;
                n = r;
                r = m % n;
            }
            (m0 / n, n0 / n)
        }
        let mut m: HashMap<(i32, i32), i64> = HashMap::new();
        for r in rectangles {
            let pair = simplify(r[0], r[1]);
            *m.entry(pair).or_default() += 1;
        }
        m.values()
            .filter(|&n| n >= &2)
            .map(|&n| n * (n - 1) / 2)
            .sum()
    }

    // 解法二
    pub fn interchangeable_rectangles2(rectangles: Vec<Vec<i32>>) -> i64 {
        //采用最大公约数算法,把tuple 作为key
        let mut map: HashMap<(i32, i32), i64> = HashMap::new();
        for item in rectangles {
            let gcd = Self::gcd(item[0], item[1]);
            let count = map.entry((item[0] / gcd, item[1] / gcd)).or_insert(0);
            *count += 1;
        }
        let mut res: i64 = 0;
        for val in map.values() {
            res += Self::acm(*val);
        }
        res
    }
    
    //累加
    pub fn acm(num: i64) -> i64 {
        num as i64 * (num as i64 - 1) / 2
    }
    
    //求最大公约数
    pub fn gcd(mut m: i32, mut n: i32) -> i32 {
        while n > 0 {
            let temp = n;
            n = m % n;
            m = temp;
        }
        m
    }
}