leetcode算法题的作用（LeetCode基础算法题第98篇）

leetcode算法题的作用（LeetCode基础算法题第98篇）首先这道题的结果一定是偶数，因为一旦一个点a到b的距离和到c的距离相等那么元祖(a b c)和(a c b)都是符合条件的，也就是说一旦有N个点到a的距离相等，那么这个点的任意组合都是符合条件的，那么就有N*(N-1)中可能。剩下的就是求其他点到a的距离的问题。找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000 10000] 中。我会持续分享下去，敬请您的关注。LeetCode 447. 回旋镖的数量 （Number of Boomerangs）给定平面上 n 对不同的点，"回旋镖" 是由点表示的元组 (i j k) ，其中 i 和 j 之间的欧氏距离和 i 和 k 之间的欧式距离相等（需要考虑元组的顺序）。

技术提高是一个循序渐进的过程，所以我讲的leetcode算法题从最简单的level开始写的，然后到中级难度，最后到hard难度全部完。

目前我选择C语言，python和Java作为实现语言，因为这三种语言还是比较典型的。由于篇幅和精力有限，其他语言的实现有兴趣的朋友请自己尝试。

初级难度说的差不多的时候，我打算再加点其他内容，我可能会从操作系统到协议栈，从分布式聊到大数据框架，从大数据聊到人工智能，... ...。

如果有任何问题可以在文章后评论或者私信给我。

我会持续分享下去，敬请您的关注。

LeetCode 447. 回旋镖的数量 （Number of Boomerangs）

问题描述：

给定平面上 n 对不同的点，"回旋镖" 是由点表示的元组 (i j k) ，其中 i 和 j 之间的欧氏距离和 i 和 k 之间的欧式距离相等（需要考虑元组的顺序）。

找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000 10000] 中。

示例：

C语言实现：

首先这道题的结果一定是偶数，因为一旦一个点a到b的距离和到c的距离相等那么元祖(a b c)和(a c b)都是符合条件的，也就是说一旦有N个点到a的距离相等，那么这个点的任意组合都是符合条件的，那么就有N*(N-1)中可能。剩下的就是求其他点到a的距离的问题。

但是在求距离的过程我没有什么比较好的方法，我能想到两种办法，但是算法复杂度都是O(n^2)，

第一种方法：

依次计算数组中的每一个点到其他点的欧式距离 以得出的距离值为key保存到一个hashmap中，其中value是统计有几个点与这个点的距离等于这个key。然后遍历这个map通过上面推导出的公式，计算出最终的总数。

第二种方法：

第一种方法的计算量比较大，实际上有一半的距离计算是重复计算的。如下图，

实际上我们只要计算上面标记有绿色箭头部分的距离，跳过冗余的部分。这样，距离的计算部分仅仅是第一种方法的一半，但是面临的问题是，我们仅仅是计算出了距离，对于每个点，统计不同距离的数量是要分开做的，而第一种方法，我们可以在一次遍历中就做好，甚至对于每一个点的符合要求的回旋镖的数量也可以一并求出，而对于第二种方法不行。

我的解法是第一种方法。

代码如下：

这是逻辑处理函数，count用来统计所有满足条件的回旋镖的数量，

map是我们自定义的hashmap结构（代码在后面）。题目限定了数组的最大长度是500，所有对于某一点来说，数组中所有点到它的距离，最多不会超过500中不同的值，所以宏MAP_SIZE定义为500

数组nodes的作用是map对象池，就是存放所有已经动态分配的map的地址。额外的好处是，后面释放这些节点的时候会比较方便。

变量nodesSize用来统计已经动态分配的map节点的数量。

第48~49行，counter数组是真正意义的map表，mallocNodes初始化为nodesSize。

第51~55行，计算欧式距离，注意真正的欧式距离是要开根号的，但是我们仅仅用来做比较的话，不用增加这个计算量。另外距离的值可能超过int的精度，所以要用long类型来表示。

第56行，调用自定义的mapGet函数，先查找map表counter中到点pointsp[i]距离为d的点的数量，如果counter没有相应的记录会返回0。（mapGet的代码见后面。）

第57行，如果curCount大于0，说明之前存在其他点到pointsp[i]的距离等于d，那么现在点pointsp[j]将作为新的点加入其中，而新加入一个节点，将使得对于这个距离的回旋镖数量翻倍。

第58~59行，更新map表counter。这里存在两种可能：

1. 如果i=0的话，即，第一次遍历的话，数组nodes是空的，即map池里面是没有对象的，那么总是会malloc一个新的map对象；
2. 如果i>0的话 nodes不是空的，里面的map对象会被复用，如果nodes被用完，就会分配一个新的，并加入到nodes，新的map会在下一个节点的时候被复用。malloc一个对象可能是比较耗时的，比如当前的内存碎片程度，一个对象的大小都影响分配的速度，如果内对象能复用，将会节省很多时间。

自定义函数mapPut会做两种处理：

1. 如果它在counter中找到了有关距离d的记录，那么该记录的cnt值加1，并返回NULL；
2. 如果找不到相关的记录，它就需要一个新的map对象来记录，它会看传递的参数locat是否为空，如果不是，则复用locat，并返回locat；如果locat为空，则malloc一个新的map对象，最后返回新的map对象。

代码60~66行，根据mapPut的返回值和locat的值，来更新map的复用信息以及map池nodes的信息。

代码69行，遍历完成后，释放掉所有动态分配的内存。

自定义的map以及相关函数代码如下：

python语言的实现：

python的实现和C实现基本是一致的

代码如下：

Java语言的实现：

Java 的实现和C语言的实现基本一致。

代码如下：