447. Number of Boomerangs
of number
2023-09-11 14:22:45 时间
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]]
Approach #1: C++. Using triple cycle .[Time Limit Exceeded]
class Solution { public: int numberOfBoomerangs(vector<pair<int, int>>& points) { int size = points.size(); int counter = 0; for (int i = 0; i < size; ++i) { for (int j = 0; j < size; ++j) { if (i == j) continue; for (int k = 0; k < size; ++k) { if (i == k || j == k) continue; int x1 = abs(points[i].first - points[j].first); int x2 = abs(points[i].first - points[k].first); int y1 = abs(points[i].second - points[j].second); int y2 = abs(points[i].second - points[k].second); double fs = sqrt(pow(x1, 2) + pow(y1, 2)); double ft = sqrt(pow(x2, 2) + pow(y2, 2)); if (fs == ft) counter++; } } } return counter; } };
Approach #2: C++.
class Solution { public: int numberOfBoomerangs(vector<pair<int, int>>& points) { int size = points.size(); int counter = 0; for (int i = 0; i < size; ++i) { unordered_map<int, int> distances; for (int j = 0; j < size; ++j) { if (i == j) continue; int distance = (points[i].first - points[j].first) * (points[i].first - points[j].first) + (points[i].second - points[j].second) * (points[i].second - points[j].second); distances[distance]++; } for (auto& p : distances) { if (p.second > 1) counter += p.second * (p.second - 1); } } return counter; } };
Approach #2: Java.
class Solution { public int numberOfBoomerangs(int[][] points) { int res = 0; for (int i = 0; i < points.length; ++i) { HashMap<Integer, Integer> map = new HashMap<>(); for (int j = 0; j < points.length; ++j) { if (points[i] == points[j]) continue; int dx = points[i][0] - points[j][0]; int dy = points[i][1] - points[j][1]; int d = dx * dx + dy * dy; map.put(d, map.getOrDefault(d, 0) + 1); } for (int val : map.values()) { res += val * (val - 1); } } return res; } }
Approach #3: Python.
class Solution(object): def numberOfBoomerangs(self, points): """ :type points: List[List[int]] :rtype: int """ res = 0 for p in points: cmap = {} for q in points: f = p[0] - q[0] s = p[1] - q[1] cmap[f*f + s*s] = 1 + cmap.get(f*f + s*s, 0) for k in cmap: res += cmap[k] * (cmap[k] - 1) return res
Time Submitted | Status | Runtime | Language |
---|---|---|---|
a few seconds ago | Accepted | 241 ms | java |
5 minutes ago | Accepted | 1436 ms | python |
8 minutes ago | Accepted | 196 ms | cpp |
相关文章
- Leetcode: Minimum Number of Arrows to Burst Balloons
- Wrong detect of Parsing error: invalid-first-character-of-tag-name in expression.
- Number of Rectangles in a Grid
- 【SPOJ】NUMOFPAL - Number of Palindromes(Manacher,回文树)
- hdu 3006 The Number of set(思维+壮压DP)
- Codeforces466C Number of Ways
- BZOJ2911 : [Poi1997]The Number of Symmetrical Choices
- Google Earth Engine ——数据全解析专辑(Global Map of Oil Palm Plantations)全球油棕种植园数据集!
- 异常Failed to convert value of type ‘java.lang.String‘ to required type ‘java.util.Date‘;
- English trip V1 - B 19. Life of Confucius 孔子的生活 Teacher:Patrick Key:
- 93Echarts - 地理坐标/地图(Bus Lines of Beijing - Line Effect)
- Can't create a new thread (errno 11); if you are not out of available memory, you can consult the manual for a possible OS-dependent bug
- js detect the type of device
- 继承“HibernateDaoSupport”后,报“The hierarchy of the type AccoutDaoImpl is inconsistent”的解决方案
- [ShapeInferenceError] Mismatch between number of source and target dimensions. Source=1 Target=0
- eclipse 创建maven web错误Cannot change version of project facet Dynamic web module to 3.1解决方案
- 浅析Object.entries()方法的使用及解决使用for of或for in遍历对象的问题和普通对象与Map对象互相转换的问题
- 第1讲:The nature of Testing--測试的本质
- jdbcTemplate异常:like模糊查询报错(Parameter index out of range (1 > number of parameters)
- [LeetCode] 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance 阈值距离内邻居最少的城市
- [LeetCode] 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix 转化为全零矩阵的最少反转次数
- [LeetCode] 1207. Unique Number of Occurrences 独一无二的出现次数
- [LeetCode] 1178. Number of Valid Words for Each Puzzle 猜字谜
- [LeetCode] 1155. Number of Dice Rolls With Target Sum 掷骰子的N种方法
- [LeetCode] 1020. Number of Enclaves 飞地的数量
- [LeetCode] Number of Subarrays with Bounded Maximum 有界限最大值的子数组数量
- [LintCode] Letter Combinations of a Phone Number 电话号码的字母组合
- [CareerCup] 5.2 Binary Representation of Real Number 实数的二进制表示
- [LeetCode] Number of 1 Bits 位1的个数
- jenkins构建,拉取不到最新版本代码,报clock of the subversion server appears to be out of sync
- 项目报错This is often the result of over-eager type matching
- 17. Letter Combinations of a Phone Number