அனைத்து புள்ளிகளையும் பார்வையிட குறைந்தபட்ச நேரம் லீட்கோட் தீர்வு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் ப்ளூம்பெர்க் பேஸ்புக் Media.net
அணி வடிவியல்

அனைத்து புள்ளிகளையும் பார்வையிடும் குறைந்தபட்ச நேரம் லீட்கோட் தீர்வு எங்களுக்கு ஒரு வழங்குகிறது வரிசை அல்லது ஒருங்கிணைப்பு அச்சுகளில் புள்ளிகளின் திசையன். உள்ளீட்டை எங்களுக்கு வழங்கிய பின் உள்ளீடு, உள்ளீட்டில் கொடுக்கப்பட்ட அனைத்து புள்ளிகளையும் பார்வையிட குறைந்தபட்ச நேரத்தைக் கண்டுபிடிக்கும்படி கேட்கிறது. நீங்கள் ஒரு அலகு 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 மதிப்புகளின் அதிகபட்ச வேறுபாட்டைக் காணலாம். இது ஒவ்வொரு நகர்வுக்கும் ஒரு எளிய சூத்திரத்தை நமக்கு வழங்குகிறது.

குறியீடு

அனைத்து புள்ளிகளையும் பார்வையிட குறைந்தபட்ச நேரத்திற்கான சி ++ குறியீடு லீட்கோட் தீர்வு

#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), ஏனெனில் பதிலைச் சேமிக்க ஒரே ஒரு மாறியை மட்டுமே பயன்படுத்தினோம், இதனால் விண்வெளி சிக்கலானது நிலையானது.