සියලුම ස්ථාන නැරඹීමේ අවම කාලය ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් බ්ලූම්බර්ග් ෆේස්බුක් මාධ්යවේදී
අරා ජ්යාමිතිය

සියලුම වේලාවන් නැරඹීමේ අවම කාලය ලීට්කෝඩ් විසඳුම අපට ලබා දෙයි අරාව හෝ ඛණ්ඩාංක අක්ෂවල ලක්ෂ්‍ය දෛශිකය. අපට ආදානය ලබා දීමෙන් පසු ඇති ගැටළුව, ආදානයේ දක්වා ඇති සියලුම කරුණු බැලීමට අවම කාලය සොයා ගැනීමට අපෙන් ඉල්ලා සිටී. ඔබ එක් ඒකකයක් x හෝ y දිශාවට ගෙන යන විට, ඔබට ඒකක 1 ක් ගතවේ. ඔබ විකර්ණ ලෙස චලනය වන විට ඒකකය දෙපැත්තටම එකවර ඒකක 1 ක් ගමන් කරයි. ඔබට ඒකක 1 ක කාලයක් හමු වේ. දැන්, ලබා දී ඇති සියලුම කරුණු බැලීමට ගතවන අවම කාලය සොයා ගන්න. තවත් කොන්දේසියක් තිබේ. කොන්දේසියෙහි දැක්වෙන්නේ ආදානයෙහි දක්වා ඇති ආකාරයට සියලුම කරුණු එකම අනුපිළිවෙලින් ගමන් කළ යුතු බවයි. එබැවින්, විසඳුම වෙත කෙලින්ම ගමන් නොකර, අපි උදාහරණ කිහිපයක් දෙස බලමු.

සියලුම ස්ථාන නැරඹීමේ අවම කාලය ලීට්කෝඩ් විසඳුම

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

පැහැදිලි කිරීම: රූපයේ පෙන්වා ඇති පරිදි, පළමු ස්ථානයේ සිට දෙවන ස්ථානයට යාමට අපට ඒකක 3 ක කාලයක් අවශ්‍ය වේ. දෙවන සිට අවසාන ස්ථානය දක්වා ගමන් කිරීමට ඒකක 4 ක කාලයක්. මේ අනුව, කාලය ඒකක 7 ක් අවශ්‍ය වේ.

සියළුම කරුණු නැරඹීම සඳහා අවම කාලයක් සඳහා ප්‍රවේශය ලීට්කෝඩ් විසඳුම

ගැටළුව සියලුම ස්ථාන නැරඹීමේ අවම කාලය ලීට්කෝඩ් විසඳුම අපෙන් විමසන්නේ ආදානයේ දක්වා ඇති සියලුම කරුණු බැලීමට අවම කාලය කුමක්ද යන්නයි. ආදානය තුළ ලබා දී ඇති ආකාරයටම ලකුණු අනුපිළිවෙලින් ගමන් කිරීමට ගැටළුව අපව බැඳී ඇත. එක් එක් පියවර සඳහා වන පිරිවැය ගැන ද අපට කියනු ලැබේ. අපට එක් දිශාවකටම ඒකක 1 ක් ගෙන යා හැකිය, නැතහොත් අපට එකවරම ඒකක 1 ක් චලනය කළ හැකිය. මෙම සියලු පියවරයන් සඳහා අපට කාලය ඒකක 1 ක් වැය වේ. එබැවින්, සාමාන්‍යයෙන් x හෝ y අගය වලින් එකක් ඊළඟ ලක්ෂ්‍යයේ x හෝ y අගයට සමාන වන තෙක් විකර්ණව ගමන් කිරීමට උත්සාහ කරයි. දැන්, x හෝ y වලින් එකක් වත්මන් ලක්ෂ්‍යයේ x හෝ y ට සමාන බව අපට විශ්වාසයි. දැන් අපට ගමන් කළ යුත්තේ සිරස් හෝ තිරස් අතට පමණි.

සිතීම ටිකක් දැඩි බව පෙනේ, නමුත් ගැටළුව ක්‍රියාත්මක කිරීම වඩා සරල ය. මෙන්න, ක්‍රියාවලිය වෙන වෙනම කරනවා වෙනුවට පළමුව අපි විකර්ණව හා පසුව තනි දිශාවකට ගමන් කරමු. වත්මන් හා ඊළඟ ලක්ෂ්‍යයේ x සහ y අගයන්හි උපරිම වෙනස අපි සරලවම සොයා ගනිමු. මෙය අපට එක් එක් පියවර සඳහා සරල සූත්‍රයක් ලබා දෙයි.

කේතය

සියලුම ලක්ෂ්‍යයන් බැලීමට අවම වේලාවක් සඳහා C ++ කේතය ලීට්කෝඩ් විසඳුම

#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

සියලුම වේලාවන් බැලීමට අවම කාලයක් සඳහා ජාවා කේතය ලීට්කෝඩ් විසඳුම

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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත), මක්නිසාද යත්, අපට මුළු ලැයිස්තුව හරහා ගමන් කළ යුතු අතර, එම නිසා කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), පිළිතුර ගබඩා කිරීම සඳහා අප භාවිතා කළේ එක් විචල්‍යයක් පමණක් බැවින් අවකාශයේ සංකීර්ණතාව නියත වේ.