Leetcode--Java--447. 回旋镖的数量

本文主要是介绍Leetcode--Java--447. 回旋镖的数量，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述

给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

返回平面上所有回旋镖的数量。

样例描述

示例 1：

输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：2

思路

哈希表

1. 由题意，需要假设一个作为拐点，寻找两个点使得它们到拐点的距离相等。
2. 可以假设某个点作为拐点，利用哈希表记录其他点到拐点的距离，然后在所有距离相同的点里面选取两个，将结果累加起来就是所求。
3. 所有点里面选两个，结合排列组合的知识，总m个的话，第一次选m种选法，第二次选是m - 1种选法。。。

代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int n = points.length;
        int res = 0;
        for (int i = 0; i < n; i ++ ) {
            //[距离，数量] 对于某个端点i，具有相同距离的端点个数
            Map<Integer, Integer> map = new HashMap<>();
             //先统计距离相同的端点个数
             for (int j = 0; j < n; j ++ ) {
                 //如果就是本端点，直接跳过
                 if (j == i) continue;
                int x = points[i][0] - points[j][0], y = points[i][1] - points[j][1];
                int dis = x * x + y * y;
                map.put(dis, map.getOrDefault(dis, 0) + 1);
             }
             //在根据某个点作为拐点 统计有多少种
             //由于 其他点都是相同距离，相等于m个数量里面选两个
             for (int disc: map.keySet()) {
                 int num = map.get(disc);
                 res += num * (num - 1);
             }
        }
        return res;
    }
}

这篇关于Leetcode--Java--447. 回旋镖的数量的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！