共计 746 个字符,预计需要花费 2 分钟才能阅读完成。
D103 447. Number of Boomerangs
题目链接
447. Number of Boomerangs
题目分析
给定一个坐标数组,从中任意取 3 个坐标 (i,j,k)
,使得从 i 到 j 的距离等于 i 到 k 的距离。且(i,j,k)
与(i,k,j)
不是同一个组合,需单独计算。
思路
逐个遍历,计算两点距离。并记录在一个数组中。
对于具有相同距离的边的个数,组合数量有以下规律:
当有 2 条边时,可以组合成 2 条;
当有 3 条边时,可以组合成 6 条;
当有 4 条边时,可以组合成 12 条;
当有 n 条边时,可以组合成 n(n-1)条。
对于每一个起点都如此计算,将最后的和返回即可。
最终代码
<?php | |
class Solution { | |
/** | |
* @param Integer[][] $points | |
* @return Integer | |
*/ | |
function numberOfBoomerangs($points) { | |
$c = 0; | |
$totalPoints = count($points); | |
for($i = 0; $i<$totalPoints; $i++){$distances = []; | |
$iv = $points[$i]; | |
for($j = 0; $j<$totalPoints; $j++){if($i == $j){continue;} | |
$jv = $points[$j]; | |
$ij = pow($iv[0]-$jv[0],2) + pow($iv[1]-$jv[1],2); | |
if(!isset($distances[$ij])){$distances[$ij] = 0; | |
} | |
$distances[$ij]++; | |
} | |
foreach($distances as $v){$c += $v*$v-$v;} | |
} | |
return $c; | |
} | |
} |
若觉得本文章对你有用,欢迎用 [爱发电](https://afdian.net/@skys215) 资助。 |
正文完