【LeetCode每日一题】447. 回旋镖的数量(枚举+哈希表)

2024-01-08 16:51:26

2024-1-8

447. 回旋镖的数量

在这里插入图片描述

思路:枚举+哈希表:
  • HashMap,用于存储距离平方和出现次数的映射关系。
  • 遍历每个点 p1,以该点为起始点,计算与其他点的距离,统计距离相等的点对数。
  • 每次遍历新的起始点,需要清空之前存储的距离和出现次数
  • 使用 getOrDefault 方法获取当前距离平方在 哈希表 中出现的次数。如果没有出现过,则默认为 0。
  • 如果当前距离平方在 哈希表 中已经出现过,说明存在距离相等的点对,需要将答案 ans 加上当前距离平方出现次数的两倍。最后,将当前距离平方的出现次数加 1,更新 cnt
class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int ans = 0;
        // 在外面 new,比在内层循环 new 效率更高
        HashMap<Integer, Integer> cnt = new HashMap<>();
        // 遍历每个点,以该点为起始点,计算与其他点的距离,统计距离相等的点对数
        for (int[] p1 : points) {
            // 每次遍历新的起始点,需要清空之前存储的距离和出现次数
            cnt.clear();
            for (int[] p2 : points) {
                // 计算两点间距离的平方
                int d2 = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
                // 统计距离相等的点对数
                int c = cnt.getOrDefault(d2, 0);
                //获取当前距离平方在 cnt 中出现的次数。如果没有出现过,则默认为 0。
                ans += c * 2;
                cnt.put(d2, c + 1);
            }
        }
        return ans;
    }
}

点击移步博客主页,欢迎光临~

偷cyk的图

文章来源:https://blog.csdn.net/m0_64003319/article/details/135459737
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。