ಎಲ್ಲಾ ಪಾಯಿಂಟ್‌ಗಳನ್ನು ಭೇಟಿ ಮಾಡುವ ಕನಿಷ್ಠ ಸಮಯ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಫೇಸ್ಬುಕ್ 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), ಏಕೆಂದರೆ ಉತ್ತರವನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ಒಂದೇ ವೇರಿಯೇಬಲ್ ಅನ್ನು ಮಾತ್ರ ಬಳಸಿದ್ದೇವೆ, ಹೀಗಾಗಿ ಜಾಗದ ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ.