Bütün nöqtələri ziyarət etmək üçün minimum vaxt Leetcode həll

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Bloomberg Facebook Media.net
alqoritmlər Geyim kodlaşdırma həndəsə müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 47

Problem Bütün nöqtələri ziyarət minimum vaxt Leetcode Həll bizə bir təmin edir array və ya koordinat oxlarındakı nöqtələrin vektoru. Bizə giriş təmin etdikdən sonra problem, girişdə verilmiş bütün nöqtələri ziyarət etmək üçün minimum vaxt tapmağımızı xahiş edir. Bir vahid x və ya y istiqamətində hərəkət etdikdə, 1 vahid vaxt alırsınız. Çapraz hərəkət etdikdə, eyni zamanda hər iki istiqamətdə 1 vahid hərəkət edin. 1 vahid vaxtla qarşılaşırsınız. İndi verilən bütün məqamları ziyarət etmək üçün tələb olunan minimum vaxtı öyrənin. Başqa bir şərt var. Şərt qeyd edir ki, bütün nöqtələri girişdə verildiyi qaydada səyahət etməliyik. Beləliklə, birbaşa həll yolu keçmədən bəzi nümunələrə nəzər salaq.

Bütün nöqtələri ziyarət etmək üçün minimum vaxt Leetcode həllPin

[[1,1],[3,4],[-1,0]]
7

İzahat: Şəkildə də göstərildiyi kimi, birinci nöqtədən ikinciyə keçmək üçün 3 vahid vaxt lazımdır. Sonra saniyədən son nöqtəyə keçmək üçün 4 vahid vaxt. Beləliklə, cəmi 7 vahid vaxt tələb olunur.

Bütün nöqtələri ziyarət etmək üçün minimum vaxt üçün yanaşma lekodu həll

Problem Bütün nöqtələri ziyarət minimum vaxt Leetcode Həlli girişdə verilmiş bütün nöqtələri ziyarət etmək üçün minimum vaxtın nə olduğunu soruşur. Problem, nöqtələri girişdə göstərildiyi qaydada eyni qaydada səyahət etməyimizi də məhdudlaşdırır. Hər hərəkətin dəyəri barədə də bizə məlumat verilir. Ya iki istiqamətin hər birində 1 vahid hərəkət edə bilərik, ya da hər iki istiqamətdə eyni vaxtda 1 vahid hərəkət edə bilərik. Bütün bu hərəkətlər bizə 1 vahid vaxta başa gəlir. Beləliklə, ümumiyyətlə, x və ya y dəyərlərindən biri növbəti nöqtənin x və ya y dəyərinə bərabər olana qədər çapraz hərəkət etməyə çalışacağıq. İndi x və ya y-dən birinin cari nöqtənin x və ya y-ə bərabər olduğuna əminik. Və indi yalnız şaquli və ya üfüqi hərəkət etməliyik.

düşüncə bir az sərt görünür, amma problemin tətbiqi daha sadə olur. Burada əvvəlcə çapraz, daha sonra tək bir istiqamətdə hərəkət etdiyimiz prosesi ayrıca yerinə yetirmək yerinə. Sadəcə cari və növbəti nöqtənin x və y dəyərlərinin maksimum fərqini tapırıq. Bu, bizə hər bir hərəkət üçün sadə bir düstur verir.

Kodu

Bütün Nöqtələri Ziyarət Edən Minimum Vaxt Leetcode Həlli üçün C ++ kodu

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

int minTimeToVisitAllPoints(vector<vector<int>>& points) {
    int ans = 0;
    int n = points.size();
    for(int i=1;i<n;i++){
        vector<int> cur = points[i], prev = points[i-1];
        int curVal = max(abs(cur[0] - prev[0]), abs(cur[1] - prev[1]));
        ans += curVal;
    }
    return ans;
}

int main(){
    vector<vector<int>> points({{1,1},{3,4},{-1,0}});
    cout<<minTimeToVisitAllPoints(points);
}
7

Bütün Nöqtələri Ziyarət etmə Minimum Vaxt üçün Java kodu Leetcode Həlli

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int minTimeToVisitAllPoints(int[][] points) {
        int ans = 0;
        int n = points.length;
        for(int i=1;i<n;i++){
            int[] cur = points[i];
            int[] prev = points[i-1];
            int curVal = Math.max(Math.abs(cur[0] - prev[0]), Math.abs(cur[1] - prev[1]));
            ans += curVal;
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception {
    int[][] points = {{1,1},{3,4},{-1,0}};
    System.out.println(minTimeToVisitAllPoints(points));
  }
}
7

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki siyahının hamısını keçməliyik və beləliklə zamanın mürəkkəbliyi xəttlidir.

Kosmik Mürəkkəblik

O (1), çünki cavabı saxlamaq üçün yalnız bir dəyişən istifadə etdik, beləliklə kosmik mürəkkəblik sabitdir.

Şərh yaz

Translate »
1