前言
前两天号内《坐标最短路径计算》一文引起了部分读者的关注,对于该文的问题描述以及解题思路大家都有疑问。所以小编写此文章来详细介绍一下。该题来自于leetcode网站上的一道题目,题目名字见本文标题。大家也可以到官网去搜索看一下原题。
问题描述
平面上有 n 个点,点的位置用整数坐标表示 points[i] =[xi, yi]。请你计算访问所有这些点需要的最小时间(以秒为单位)。
你可以按照下面的规则在平面上移动:
·每一秒沿水平或者竖直方向移动一个单位长度,或者跨过对角线(可以看作在一秒内向水平和竖直方向各移动一个单位长度)。
·必须按照数组中出现的顺序来访问这些点。
示例1:
图2.1示例1
解决方案
拿到题目后,首先提取出题目的关键信息,“最小”和“顺序”,既然是按坐标点的顺序,那么访问所有点的最短路径(最小时间)就为每对相邻点的最短路径之和。
3.1假设第i对相邻点的距离为Xi,坐标点的个数为L,那么总共就有L-1对相邻点,所以总的最短路径就为:
如果求出了Xi,这个S就可以用一个for循环累加Xi,所以现在关键就是Xi怎么求。
3.2由上文可知Xi为相邻两点的距离,本来数学中的两个平面坐标点的距离应该是两点横纵坐标之差的平方和再开方,也就是通过勾股定理计算而来。但是在这道题中则不需要,因为题目说了一个方格的对角线可以看作是在一秒内向水平和竖直方向各移动一个单位长度,所以在这种情况下无论什么样的两个点都可以看作是处于同一水平线或是竖直线上。而它的长度即为两点的横坐标或是纵坐标之差,因为差值大的那一边是必须要走完的,而差值小的则可以通过斜线来补齐。所以最后得出两点的距离即为两点横纵坐标差值大的值。
结语
经过以上的分析,这个问题也算是解决了,至于代码,可以用很多种方式写出来,这不是最关键的,也不是唯一的答案。代码仅供参考。