首页 > 考试 > 其他 > 正文
LeetCode 447. Number of Boomerangs
2016-11-23 09:24:00       个评论    来源:James Pan  
收藏    我要投稿

原题网址:https://leetcode.com/problems/number-of-boomerangs/

Givennpoints in the plane that are all pairwise distinct, a "boomerang" is a tuple of points(i, j, k)such that the distance betweeniandjequals the distance betweeniandk(the order of the tuple matters).

Find the number of boomerangs. You may assume thatnwill be at most500and coordinates of points are all in the range[-10000, 10000](inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

方法:使用哈希映射保存距离的计数器。

 

public class Solution {
    private void put(Map map, int d) {
        Integer count = map.get(d);
        if (count == null) {
            count = 1;
        } else {
            count++;
        }
        map.put(d, count);
    }
    public int numberOfBoomerangs(int[][] points) {
        Map distance = new HashMap<>();
        int numbers = 0;
        for(int i = 0; i < points.length; i++) {
            distance.clear();
            for(int j = 0; j < points.length; j++) {
                if (j == i) continue;
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];
                int d2 = dx * dx + dy * dy;
                put(distance, d2);
            }
            for(Map.Entry entry : distance.entrySet()) {
                int v = entry.getValue();
                if (v < 2) continue;
                numbers += v * (v - 1);
            }
        }
        return numbers;
    }
}


 

点击复制链接 与好友分享!回本站首页
相关TAG标签 LeetCode
上一篇:HDU-1317-XYZZY
下一篇:ZSTUOJ 2016ACM新生选拔赛 (更新中)
相关文章
图文推荐
文章
推荐
热门新闻

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站