1266. Minimum Time Visiting All Points

leetcode easy

#array#csharp#easy#leetcode#math

Task

На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.

Пример:

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

Output: 7

C# solution

matched/original

public class Solution {
    public int MinTimeToVisitAllPoints(int[][] points) {
        int time = 0;
        for (int i = 0; i < points.Length - 1; i++) {
            time += Distance(points[i], points[i + 1]);
        }
        return time;
    }
    private int Distance(int[] p1, int[] p2) {
        return Math.Max(Math.Abs(p1[0] - p2[0]), Math.Abs(p1[1] - p2[1]));
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinTimeToVisitAllPoints(int[][] points) {
        int time = 0;
        for (int i = 0; i < points.size() - 1; i++) {
            time += Distance(points[i], points[i + 1]);
        }
        return time;
    }
    private int Distance(vector<int>& p1, vector<int>& p2) {
        return max(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]));
    }
}

Java solution

matched/original

public class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int time = 0;
        for (int i = 0; i < points.length - 1; i++) {
            time += distance(points[i], points[i + 1]);
        }
        return time;
    }

    private int distance(int[] p1, int[] p2) {
        return Math.max(Math.abs(p1[0] - p2[0]), Math.abs(p1[1] - p2[1]));
    }
}

Python solution

matched/original

def minTimeToVisitAllPoints(points):
    def distance(p1, p2):
        return max(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))

    time = 0
    for i in range(len(points) - 1):
        time += distance(points[i], points[i + 1])
    return time

Go solution

matched/original

func minTimeToVisitAllPoints(points [][]int) int {
    time := 0
    for i := 0; i < len(points)-1; i++ {
        time += distance(points[i], points[i+1])
    }
    return time
}

func distance(p1, p2 []int) int {
    return max(abs(p1[0]-p2[0]), abs(p1[1]-p2[1]))
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

Explanation

Algorithm

1⃣Инициализируйте переменную для хранения минимального времени.

2⃣Последовательно проходите по всем точкам и вычисляйте минимальное время для перехода от текущей точки к следующей.

3⃣Суммируйте время переходов для получения общего минимального времени.

😎