leetcode
leetcode 1751 ~ 1800
可互换矩形的组数

可互换矩形的组数

难度:

标签:

题目描述

代码结果

运行时间: 144 ms, 内存: 61.5 MB


// 思路:
// 使用Java Stream API来实现与上面相同的逻辑。
// 我们将矩形转换为宽高比,并计算每个比率的数量,然后计算成对的可互换矩形。

import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Solution {
    public long interchangeableRectangles(int[][] rectangles) {
        Map<Double, Long> ratioCount = Arrays.stream(rectangles)
                .map(rect -> (double) rect[0] / rect[1])
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        return ratioCount.values().stream()
                .mapToLong(count -> count * (count - 1) / 2)
                .sum();
    }
}

解释

方法:

The solution leverages a hash map (Counter) to record the frequency of each unique width-to-height ratio encountered among the rectangles. Instead of using the raw division result, which could suffer from floating-point precision issues, it implicitly uses the ratio of width to height. For each unique ratio found, if there are 'x' rectangles with that ratio, the number of interchangeable pairs among these rectangles can be calculated using the combination formula 'x choose 2', which simplifies to x*(x-1)/2. This approach counts all such pairs across different unique ratios.

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在计算宽高比时,为什么选择使用`w/h`而不是其他形式,例如`h/w`或是两者的差异?
选择使用`w/h`作为矩形宽高比的表示是出于对比例一致性的考虑。使用`w/h`可以直接反映矩形的形状比例,因为在几何学中,这种比例能够唯一确定一个矩形的相似类。如果使用`h/w`,虽然也能达到相似的效果,但需要保持使用一致性以避免混淆。此外,使用两者的差异(如`w-h`)则不能正确反映矩形的比例关系,因为不同的矩形可能有相同的差异但形状比例完全不同。
🦆
如何确保`w/h`的计算中不会受到Python浮点数精度问题的影响?
为了避免浮点数精度问题,实际上应该避免直接使用`w/h`的浮点结果作为键存储。一种常见的方法是使用整数比来表示,即通过存储每个矩形宽高比的最简分数形式。可以通过计算宽度和高度的最大公约数,然后用宽度除以最大公约数和高度除以最大公约数得到约简后的比例。这样,即使宽高比为有理数,其最简分数形式也可以精确表示,从而避免了浮点数的精度问题。
🦆
在使用Counter计算频率时,是否有可能出现某些比例因为精度问题而被错误地认为不相等?
如果直接使用浮点数结果作为键,确实可能因为浮点数的精度问题导致本应相等的比例被认为是不相等的。例如,由于计算误差,两个非常接近的浮点数可能不完全相等。正如之前所述,最佳做法是使用整数比(即最简分数形式),这样可以完全避免这种情况,确保只有真正具有相同宽高比的矩形才会被计算在内。
🦆
题解中提到使用组合公式`x*(x-1)/2`来计算可互换矩形的组数,为什么这种方法是适用的?
当你有`x`个相同宽高比的矩形时,你可以从这`x`个矩形中任选两个来形成一对。组合数`C(x, 2)`即是从`x`个元素中选择两个不同元素的方法数,其公式为`x*(x-1)/2`。这是因为每选择一个矩形,都有`x-1`个其他矩形可以与之配对,然后由于每对矩形被计算了两次(一次以A为第一个,B为第二个,一次以B为第一个,A为第二个),所以需要将结果除以2。这种计算方法简单且直接反映了组合的本质。

相关问题