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，所以注意不要越界，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/41051.html
標籤：其他
上一篇：2020新年愿望
下一篇：leetcode菜雞斗智斗勇系列（8）--- Find N Unique Integers Sum up to Zero