leetcode菜鸡斗智斗勇系列（7）--- 用最小的时间访问所有的节点

1.原题：

https://leetcode.com/problems/minimum-time-visiting-all-points/

On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
You have to visit the points in the same order as they appear in the arra

翻译：给定一个平面，有n个点，坐标表示为 [xi,yi]，你需要求出一个最小的访问时间，你的访问方式必须是以顺序去访问所有的点。每一秒钟你可以水平或者垂直移动一步或者对角移动一步。

此图就是原题的一个示例：

Input : points = [[1,1],[3,4],[-1,0]]

output :7

因为：[1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]

2.解题思路：

这种简单的最小路径的算法题，思路有很多，最简单的就是贪心算法，因为最无脑。

我们都知道，对角的一步比水平或者垂直移动的一步都要远，所以我们要尽量先走对角，然后实在没有办法的时候再普通的走一步。

那么算法就很明了了：

class Solution {
public:
int minTimeToVisitAllPoints(vector<vector<int>>& points) {
int ans = 0; //距离的绝对值
for(int i = 1; i < points.size(); i++) {
ans += max(abs(points[i][1] - points[i - 1][1]), abs(points[i][0] - points[i - 1][0])); //求出发点和目的点的xy值的差，比如例子里，x为3-1=2,y为4-1=3。这两个值相同的部分（2) 就是对角的步数，多出来的（1）就是水平或者垂直的移动，因此我们取两者的最大值3，是本次的距离。
}
return ans;
}
};

sub:这里要注意就是 “points.size()” 这个是vector的一个成员函数 .size()其返回的是unsighed int，所以注意不要越界。

巴特西

leetcode菜鸡斗智斗勇系列（7）--- 用最小的时间访问所有的节点

1.原题：

2.解题思路：

最新文章

热门文章