LeetCode 447. Number of Boomeran

题目

Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).
Find the number of boomerangs. You may assume that n will be at most 500 and 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]]

解析

此题难度为easy，难度来说是简单的。但是如果使用二维数组来存储各个距离的话，可能会time exceed limit，超时。另外一种方法是使用哈希表HashMap。这种类型的题目和字符串类型使用的Hash不一样，字符串可以-'a'来存储位置，此题是distance，该怎么存？
题目中给定了n最大为500，因此可以设置一个长度为500的HashMap。在计算distance存储key的过程中，如果key % 500相等的话，则需要将该key链到该slot的后面，即每一个slot都是一个动态链表，这样问题便解决了。

代码（C语言）

#define HASHMAP_SIZE        500

typedef struct DistanceHashMap
{
    int count;
    int distance;
    struct DistanceHashMap* next;
} DisHashMap;

void add2HashMap(DisHashMap* disHashMap, int distance) {
    int slot = distance % HASHMAP_SIZE;
    
    if (disHashMap[slot].distance == distance) {
        ++disHashMap[slot].count;
    } else if (disHashMap[slot].distance == 0) {
        disHashMap[slot].distance = distance;
        
        ++disHashMap[slot].count;
    } else {
        DisHashMap* p = &disHashMap[slot];
        
        while (p->distance != distance && p->next)
            p = p->next;
        
        if (p->distance == distance) {
            ++p->count;
        } else {
            p->next = (DisHashMap*)calloc(1, sizeof(DisHashMap));
            
            p = p->next;
            p->count = 1;
            p->distance = distance;
            p->next = NULL;
        }
    }
}

int cal2PointDistance(int* p1, int* p2) {
    int xDiffAbs = abs(p1[0] - p2[0]);
    int yDiffAbs = abs(p1[1] - p2[1]);
    
    return xDiffAbs * xDiffAbs + yDiffAbs * yDiffAbs;
}

int numberOfBoomerangs(int** points, int pointsRowSize, int pointsColSize) {
    if (!points || pointsRowSize == 0 || pointsColSize == 0)
        return 0;
    
    int totalBoomerangs = 0;
    DisHashMap* disHashMap = (DisHashMap*)calloc(HASHMAP_SIZE,
                                                 sizeof(DisHashMap));
    
    for (int i = 0; i < pointsRowSize; ++i) {
        // clear disHashMap
        for (int j = 0; j < HASHMAP_SIZE; ++j) {
            DisHashMap* curHashMap = &disHashMap[j];
            
            if (curHashMap->next) {
                DisHashMap* p = curHashMap->next;
                
                while (p) {
                    DisHashMap* q = p->next;
                    
                    free(p);
                    p = q;
                }
            }
            
            curHashMap->next = NULL;
            curHashMap->count = 0;
            curHashMap->distance = 0;
        }
        
        // construct distance hashmap
        for (int j = 0; j < pointsRowSize; ++j) {
            if (i == j)
                continue;
            
            add2HashMap(disHashMap, cal2PointDistance(points[i], points[j]));
        }
        
        for (int j = 0; j < HASHMAP_SIZE; ++j) {
            DisHashMap* curHashMap = &disHashMap[j];
            
            while (curHashMap) {
                if (curHashMap->count > 1) {
                    totalBoomerangs += (curHashMap->count *
                                        (curHashMap->count - 1));
                }
                
                curHashMap = curHashMap->next;
            }
        }
    }
    
    // free hashmap
    for (int i = 0; i < HASHMAP_SIZE; ++i) {
        DisHashMap* curHashMap = (&disHashMap[i])->next;
        
        while (curHashMap) {
            DisHashMap* p = curHashMap;

            curHashMap = curHashMap->next;
            free(p);
        }
    }
    
    free(disHashMap);
    
    return totalBoomerangs;
}

此题仍然考验笔者的编程和调试能力。要注意的是开始初始化HashMap的时候，它有可能是上次计算完留下的HashMap，因此要对每一个slot的链表进行free，最后再对头结点进行初始化，直接初始化头结点会造成内存泄露。在最后的时候需要将之前使用的堆区内存free掉。
此题仍建议读者亲自编写一下，提高逻辑思维能力和编码能力。