This is the question of the day for LeetCode 2021-9-13: “447. Number of boomerangs”

1. Topic description

Given n pairs of different points on the plane, where points[I] = [xi, yi]. Boomerangs are tuples represented by points (I, j, k) where the distance between I and j is the same as the distance between I and K (the order of the tuples needs to be considered).

Returns the number of all boomerangs in the plane.

Example 1:

Input: points = [[0, 0), (1, 0), (2, 0]] output: 2: two maneuver dart for [[1, 0], [0, 0], [2, 0]] and [[1, 0], [2, 0], [0, 0]]Copy the code

Example 2:

Points = [[1,1],[2,2],[3,3]Copy the code

Example 3:

Input: points = [[1,1]] output: 0Copy the code

2. Answer

1. traversepoints, take each point asThe vertices, calculate the distance from other points to the vertex, save the distance of points with the same distanceThe number ofinmapIn the
2. Through eachmapIf the number of points with the same distance from the vertex is greater than 1, the number of boomerangs is counted
3. A total ofnumPick two of them. There arenum*(num-1)A possible

// Square the distance between two points
const getD = ([a1, a2], [b1, b2]) = > (b1 - a1) ** 2 + (b2 - a2) ** 2;

const numberOfBoomerangs = points= > {
    if (points.length < 3) return 0;

    const map = {};
    let res = 0;

    points.forEach((a, i) = > {
        // Take each point as a vertex
        map[a] = {};
        // Iterate again to get the distance from the remaining points to the vertex
        points.forEach((b, j) = > {
            // exclude points with self
            if(i ! == j) {// Calculate the distance
                const d = getD(a, b);
                // Save the distance
                map[a][d] = (map[a][d] || 0) + 1; }});// Iterate over the vertex map
        for (const item in map[a]) {
            // The number of points that are the same distance from the vertex
            const num = map[a][item];
            // num>1 to form a boomerang with vertices
            Num *(num-1) = num*(num-1
            if (num > 1) res += num * (num - 1); }});return res;
};
Copy the code

😄 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions!

🖥️ Warehouse address: “One of the Day series”