Leetcode-PHP题解D103-447-Number-of-Boomerangs

74次阅读

共计 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) 资助。

正文完
 0