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)--- 用最小的时间访问所有的节点
来源: http://www.bubuko.com/infodetail-3360951.html