447 - 回旋镖的数量(number-of-boomerangs)

Create by jsliang on 2019-07-29 19:45:23
Recently revised in 2019-7-29 22:42:06

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
四 执行测试
五 LeetCode Submit
六 解题思路

二 前言

返回目录

给定平面上 n 对不同的点,“回旋镖” 是由点表示的元组 (i, j, k) ,其中 i 和 j 之间的距离和 i 和 k 之间的距离相等(需要考虑元组的顺序)。

找到所有回旋镖的数量。你可以假设 n 最大为 500,所有点的坐标在闭区间 [-10000, 10000] 中。

示例:

输入:
[[0,0],[1,0],[2,0]]

输出:
2

解释:
两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

  • 解题代码
const dist = (i, j) => {
  return (i[0] - j[0]) * (i[0] - j[0]) + (i[1] - j[1]) * (i[1] - j[1]);
};

const judge = (i, j, k) => {
  let count = 0;
  if (dist(i, j) == dist(i, k)) {
    count += 2;
  }
  if (dist(j, i) == dist(j, k)) {
    count += 2;
  }
  if (dist(k, i) == dist(k, j)) {
    count += 2;
  }
  return count;
};

const numberOfBoomerangs = (points) => {
  let result = 0;
  for (let i = 0; i < points.length - 2; i++) {
    for (let j = i + 1; j < points.length - 1; j++) {
      for (let k = j + 1; k < points.length; k++) {
        result += judge(points[i], points[j], points[k]);
      }
    }
  }
  return result;
};

四 执行测试

返回目录

  1. point[[0,0],[1,0],[2,0]]
  2. return
2

五 LeetCode Submit

返回目录

√ Accepted
  √ 31/31 cases passed (2048 ms)
  √ Your runtime beats 27.69 % of javascript submissions
  √ Your memory usage beats 93.75 % of javascript submissions (35 MB)

六 解题思路

返回目录

目测第一眼,LeetCode 又丧心病狂啦!!!

首先,个人猜测,对于题意,个人先解析一波:

  • 回旋镖表示的为元组(i, j, k),咱不太理解,姑且认为 x, y, z 构成的三维地址。
  • i 到 j 的距离 === i 到 k 的距离。
  • [[0,0],[1,0],[2,0]] 对应的即是:[[1,0],[0,0],[2,0]][[1,0],[2,0],[0,0]]

由于咱没有更多的数据支持,所以我们也无法确定,是元组可以随意组成任意组,然后差值相同?

一脸蒙圈~

然后,只能求助【评论】和【题解】的大佬看看了:

Go 实现

func dist(i,j []int) int {      // 两点间的距离
  return (i[0]-j[0])*(i[0]-j[0]) + (i[1]-j[1])*(i[1]-j[1])
}

func judge(i,j,k []int) int {   // 计算这三个点能构成几个“回旋镖”
  cnt := 0
  if dist(i,j) == dist(i,k) {
    cnt+=2
  }
  if dist(j,i) == dist(j,k) {
    cnt+=2
  }
  if dist(k,i) == dist(k,j) {
    cnt+=2
  }
  return cnt
}

func numberOfBoomerangs(points [][]int) int {   // 三层循环遍历每个三元组
  ans := 0
  for i:=0; i<len(points)-2; i++ {
    for j:=i+1; j<len(points)-1; j++ {
      for k:=j+1; k<len(points); k++ {
        ans += judge(points[i],points[j],points[k])
      }
    }
  }
  return ans
}

说实话我也不懂 Go 语言,但是我看到了,并且我懂一点后端语言,感觉可以理解,于是尝试转换成 JavaScript:

const dist = (i, j) => {
  return (i[0] - j[0]) * (i[0] - j[0]) + (i[1] - j[1]) * (i[1] - j[1]);
};

const judge = (i, j, k) => {
  let count = 0;
  if (dist(i, j) == dist(i, k)) {
    count += 2;
  }
  if (dist(j, i) == dist(j, k)) {
    count += 2;
  }
  if (dist(k, i) == dist(k, j)) {
    count += 2;
  }
  return count;
};

const numberOfBoomerangs = (points) => {
  let result = 0;
  for (let i = 0; i < points.length - 2; i++) {
    for (let j = i + 1; j < points.length - 1; j++) {
      for (let k = j + 1; k < points.length; k++) {
        result += judge(points[i], points[j], points[k]);
      }
    }
  }
  return result;
};

Submit 提交:

√ Accepted
  √ 31/31 cases passed (2048 ms)
  √ Your runtime beats 27.69 % of javascript submissions
  √ Your memory usage beats 93.75 % of javascript submissions (35 MB)

还真的过了,所以我们就啃下它!

接着jsliang 通过讲解上面代码,讲讲自己的理解:

1、计算两点之间的距离

const dist = (i, j) => {
  return (i[0] - j[0]) * (i[0] - j[0]) + (i[1] - j[1]) * (i[1] - j[1]);
};

计算两个点的距离,就是它们对应坐标的差的平方相加。

即:

  • x - [1, 2]
  • y - [2, 3]
  • dist(x, y) = (2 - 1)² + (3 - 2)²

2、计算这三个点能构成几个“回旋镖”

const judge = (i, j, k) => {
  let count = 0;
  if (dist(i, j) == dist(i, k)) {
    count += 2;
  }
  if (dist(j, i) == dist(j, k)) {
    count += 2;
  }
  if (dist(k, i) == dist(k, j)) {
    count += 2;
  }
  return count;
};

正如题目所言,i 到 j 的距离等于 i 到 k 的距离。

同样:

  • i - j === i - k
  • j - i === j - k
  • k - i === k - j

3、三层循环遍历每个三元组

const numberOfBoomerangs = (points) => {
  let result = 0;
  for (let i = 0; i < points.length - 2; i++) {
    for (let j = i + 1; j < points.length - 1; j++) {
      for (let k = j + 1; k < points.length; k++) {
        result += judge(points[i], points[j], points[k]);
      }
    }
  }
  return result;
};

三层遍历数组,获取到每种可能,通过 result 获取最终结果,并输出最终结果。

最后,我们解析了代码,虽然题意仍然不太清晰,但是我们可以了解到:

  1. 算法中两点距离的计算
  2. 构成一个立体物品的方法

相信后面我们会接触更多的这种题,从而逐渐明朗~

如果你有更好的理解,请留言~


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-30 09:43:03

results matching ""

    No results matching ""