Loading...
墨滴

泓丞

2021/03/27  阅读:41  主题:前端之巅同款

leetcode题解--访问所有点的最小时间

这道题一到手,感觉高大上,第一反应是觉得好难,其实是个典型的扮猪吃老虎的题目,找对方法就很简单。

来!看题~

题目1266. 访问所有点的最小时间

平面上有 n 个点,点的位置用整数坐标表示 points[i] = [xi, yi] 。请你计算访问所有这些点需要的 最小时间(以秒为单位)。

你需要按照下面的规则在平面上移动:

每一秒内,你可以: 沿水平方向移动一个单位长度,或者 沿竖直方向移动一个单位长度,或者 跨过对角线移动 sqrt(2) 个单位长度(可以看作在一秒内向水平和竖直方向各移动一个单位长度)。 必须按照数组中出现的顺序来访问这些点。 在访问某个点时,可以经过该点后面出现的点,但经过的那些点不算作有效访问。

示例 1:

image.png
image.png
输入:points = [[1,1],[3,4],[-1,0]]
输出:7
解释:一条最佳的访问路径是: [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
从 [1,1] 到 [3,4] 需要 3 秒 
从 [3,4] 到 [-1,0] 需要 4 秒
一共需要 7 秒

示例 2:

输入:points = [[3,2],[-2,2]]
输出:5

提示:

  • points.length == n
  • 1 <= n <= 100
  • points[i].length == 2
  • -1000 <= points[i][0], points[i][1] <= 1000

题解:

我们来一步步吃掉它吧。

第一步

这道题的实际上是一道几何数学题,正确解法的第一步是要先画出直角坐标系,给坐标轴上所有坐标点画相对于坐标轴的平行线,就会形成一个个小正方形,然后按示例标好各点位置,自己试着走两步,接着就能发现其中奥秘。

第二步

在最小正方形上,从一个点到另一个相临点算一个时间单位,走最小正方形的对角线也是一个时间单位。两个点在坐标系上,总共只会有两种位置关系:在一条线上(包括相同点)、在矩形对角线上,而对角线又分为正方形和长方形这两种。

第三步

在一条线上,这个距离怎么算,从图上看就是线段长度;从数学上算,就是差值的绝对值;在正方形对角线上,因为最小正方形对角线算一个单位长度,所以这个时间值也可以按边长,也就是xy值任意一轴的差值绝对值;在长方形对角线上,这个时间值的算法可以先走一个长方形内最大正方形,走完后就在一条线上了,再走剩下的直线;你会发现,长方形内最大正方形的边长就是长方形最短边长,所以走到对角线上的点可以总结为最长边长;

第四步

经过上面分析,走完两点所有情况下的时间值,都可以总结为两点间形成的长方形(一条线上可以假设一条边为0)的最长边长值。按这种思路走完所有的点,再把每一段加起来就能得到最终结果了。

最后,上答案:

var minTimeToVisitAllPoints = function(points{
  let res = 0
  for(let i = 0; i < points.length-1; i++){
    let next = points[i + 1]
    let cur = points[i]
    let diff = Math.max(Math.abs(cur[0] - next[0]), Math.abs(cur[1] - next[1]))
    res += diff
  }
  return res
}

这个解法还可以再优化下,每次循环少了一步points的长度-1的计算,能节省点时间

var minTimeToVisitAllPoints = function(points{
  let res = 0
  for(let i = 1; i < points.length; i++){
    let last = points[i - 1]
    let cur = points[i]
    let diff = Math.max(Math.abs(cur[0] - last[0]), Math.abs(cur[1] - last[1]))
    res += diff
  }
  return res
}

复杂度

时间复杂度O(n),其中 NN 是数组的长度。; 空间复杂度O(1);

题目链接:https://leetcode-cn.com/problems/minimum-time-visiting-all-points

泓丞

2021/03/27  阅读:41  主题:前端之巅同款

作者介绍

泓丞