美文网首页LeetCode题解及面试
【LeetCode】1266. Minimum Time Vis

【LeetCode】1266. Minimum Time Vis

作者: LeetPub | 来源:发表于2019-11-30 20:18 被阅读0次

    题意

    在2D平面上给出n个整数点pointspoints[i] = [xi, yi]xiyi都是整数,访问所有points需要多少秒?
    其中:

    • 水平移动一个单元、垂直移动一个单元、对角移动一个单元(水平移动一次、垂直移动一次)都认为只耗时1秒;
    • 只能顺序访问points;

    解法

    拿到题目后核心需要解决从A点到B点需要多少秒,知道AB两点需要多少秒后,后面只需要遍历points重复计算即可。
    A、B点可以形成两种类型的矩形,瘦矩形和胖矩形,由于对角移动只耗时1秒(相当于移动了两次一次水平一次垂直,优于直接进行水平移动和垂直移动),所以A到B点优先对角移动,使对角移动最大化,然后再水平或者垂直移动。

    • 针对瘦矩形 (|x2-x1| < |y2-y1|)

    从A点(1,1)到B点(3,6)最优耗时计算:先对角移动在垂直移动(1,1)->(3,3)->(3,6)
    瘦矩阵移动耗时移动路径(x1,y1)->(x2,x2)->(x2,y2)
    通用计算:|x2-x1|+(|y2-y1|-|x2-x1|)

    • 针对胖矩形 (|x2-x1|>|y2-y1|)

    从A点(1,1)到B点(6,3)最优耗时计算:先对角移动在垂直移动(1,1)->(3,3)->(6,3)
    瘦矩阵移动耗时移动路径(x1,y1)->(y2,y2)->(x2,y2)
    通用计算:|y2-y1|+(|x2-x1|-|y2-y1|)

    结合胖矩阵和瘦矩阵,最后A(x1, y1)点到B(x2, y2)点的耗时为:
    \begin{equation} sum = \left\{ \begin{array}{cc} |x2-x1| + (|y2-y1|-|x2-x1|) & 当|x2-x1| < |y2-y1|时 \\ |y2-y1| + (|x2-x1|-|y2-y1|) & 当|x2-x1| >= |y2-y1|时 \end{array} \right. \end{equation}

    综合得sum=min(|x2-x1|, |y2-y1|)+abs(|y2-y1|-|x2-x1|)

    代码

    class Solution {
    public:
        int minTimeToVisitAllPoints(vector<vector<int>>& points) {
            int sum = 0;
            for (size_t i = 1; i < points.size(); ++ i) {
                int xt = abs(points[i][0]-points[i-1][0]);
                int yt = abs(points[i][1]-points[i-1][1]);
                sum += min(xt, yt) + abs(yt-xt);
            }
            return sum;
        }
    };
    

    相关文章

      网友评论

        本文标题:【LeetCode】1266. Minimum Time Vis

        本文链接:https://www.haomeiwen.com/subject/uszowctx.html