Βρείτε την πρώτη κυκλική περιήγηση που επισκέπτεται όλες τις αντλίες βενζίνης


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις αμαζόνα Γεγονότα Microsoft Morgan Stanley Zoho
Ουρά

Δήλωση προβλήματος

Το πρόβλημα «Βρείτε την πρώτη κυκλική περιήγηση που επισκέπτεται όλες τις αντλίες βενζίνης» δηλώνει ότι υπάρχουν βενζινοκίνητες αντλίες σε κυκλικό δρόμο. Λαμβάνοντας υπόψη τη βενζίνη που έχει κάθε αντλία βενζίνης και την ποσότητα βενζίνης που απαιτείται για να καλύψει την απόσταση μεταξύ δύο αντλιών βενζίνης. Επομένως, πρέπει να βρείτε την πρώτη αντλία βενζίνης από όπου ξεκινά ένα φορτηγό και μπορεί να ολοκληρώσει τον κύκλο.
Η μορφή εισόδου είναι, {x, y}, όπου x είναι η βενζίνη που έχει η αντλία βενζίνης και y είναι το καύσιμο που απαιτείται για να φτάσετε από αυτήν την αντλία βενζίνης στην επόμενη αντλία βενζίνης.
Εάν δεν υπάρχει πιθανή περιήγηση, έξοδος -1.

Παραδείγματα

{{5, 3}, {2, 7}, {11, 2}, {8, 9}}
3

 

Βρείτε την πρώτη κυκλική περιήγηση που επισκέπτεται όλες τις αντλίες βενζίνης

 

{{1, 1}, {2, 2}, {1, 2}, {3, 1}}
4
{{2, 3}, {4, 5}, {1, 1}, {3, 3}}
-1

Naive προσέγγιση

Ένα προς ένα θεωρεί κάθε αντλία βενζίνης ως αφετηρία. Εάν υπάρχει μια πιθανή έγκυρη περιοδεία. Επιστρέψτε τον τρέχοντα αριθμό αντλίας βενζίνης. Διαφορετικά, εάν δεν υπάρχει πιθανή περιήγηση από οποιαδήποτε αντλία βενζίνης, επιστροφή -1.

  1. Εκτελέστε έναν βρόχο από 1 έως n, αυτός ο βρόχος θεωρεί την αντλία βενζίνης ith ως σημείο εκκίνησης.
  2. Αρχικοποιήστε ένα μεταβλητό currFuel ως 0, το οποίο αντιπροσωπεύει την ποσότητα βενζίνης στο φορτηγό.
  3. Για να ταξιδέψετε από την αντλία βενζίνης jth στην (j + 1) η αντλία βενζίνης, (καύσιμο [j] - κόστος [j]) προστίθεται ποσότητα καυσίμου στο currFuel.
  4. Από την αντλία βενζίνης αρχίστε να ταξιδεύετε μπροστά στον κύκλο και προσθέστε το επιπλέον καύσιμο (καύσιμο [j] - κόστος [j]) σε κάθε βήμα, επαναλάβετε αυτήν τη διαδικασία ενώ το currFuel> = 0.
  5. Εάν το φορτηγό μπορεί να διασχίσει όλες τις αντλίες βενζίνης, επιστρέψτε i. Διαφορετικά συνεχίστε για το επόμενο i.
  6. Εάν δεν υπάρχει κανένα για το οποίο το φορτηγό μπορεί να διασχίσει ολόκληρο τον κύκλο, επιστρέψτε -1.

Κώδικας

Κωδικός JAVA για να βρείτε την πρώτη κυκλική περιήγηση που επισκέπτεται όλες τις αντλίες βενζίνης

class FindTheFirstCircularTourThatVisitsAllThePetrolPumps {
    private static int findPetrolPump(int[] fuel, int[] costs) {
        // Total number of petrol pumps
        int n = fuel.length;

        // one by one consider all the petrol pumps as starting point
        for (int i = 0; i < n; i++) {
            // initialize currPetrol as 0, it represents the amount of petrol in the truck
            int currPetrol = 0;
            // travelled represents the number of petrol pumps travelled by truck
            int travelled = 0;
            // while there is some petrol in the truck, travel to the next petrol pump
            while (currPetrol >= 0 && travelled < n) {
                // fuel added to the truck when it cross petrol pump
                // number j is (fuel[j] - cost[j])
                currPetrol += (fuel[(i + travelled) % n] - costs[(i + travelled) % n]);
                travelled++;
            }
            // if the truck has travelled all the petrol pumps
            // with some fuel left, return i
            if (travelled == n && currPetrol >= 0) {
                return (i + 1);
            }
        }
        
        // no possible way to travel the circle
        return -1;
    }

    public static void main(String[] args) {
        // Example 1
        int fuel1[] = new int[] {5, 2, 11, 8};
        int costs1[] = new int[] {3, 7, 2, 9};
        System.out.println(findPetrolPump(fuel1,costs1));

        // Example 2
        int fuel2[] = new int[] {1, 2, 1, 3};
        int costs2[] = new int[] {1, 2, 2, 1};
        System.out.println(findPetrolPump(fuel2, costs2));

        // Example 3
        int fuel3[] = new int[] {2, 4, 1, 3};
        int costs3[] = new int[] {3, 5, 1, 3};
        System.out.println(findPetrolPump(fuel3, costs3));
    }
}
3
4
-1

C ++ Code για να βρείτε την πρώτη κυκλική περιήγηση που επισκέπτεται όλες τις αντλίες βενζίνης

#include <iostream>
using namespace std;

int findPetrolPump(int *fuel, int *costs, int n) {
    // one by one consider all the petrol pumps as starting point
    for (int i = 0; i < n; i++) {
        // initialize currPetrol as 0, it represents the amount of petrol in the truck
        int currPetrol = 0;
        // travelled represents the number of petrol pumps travelled by truck
        int travelled = 0;
        // while there is some petrol in the truck, travel to the next petrol pump
        while (currPetrol >= 0 && travelled < n) {
            // fuel added to the truck when it cross petrol pump
            // number j is (fuel[j] - cost[j])
            currPetrol += (fuel[(i + travelled) % n] - costs[(i + travelled) % n]); 
            travelled++;
        }
        // if the truck has travelled all the petrol pumps
        // with some fuel left, return i
        if (travelled == n && currPetrol >= 0) {
            return (i + 1);
        }
    }
    
    // no possible way to travel the circle
    return -1;
}

int main() {
  // Example 1
    int fuel1[] = {5, 2, 11, 8};
    int costs1[] = {3, 7, 2, 9};
    cout<<findPetrolPump(fuel1, costs1, sizeof(fuel1) / sizeof(fuel1[0]))<<endl;

    // Example 2
    int fuel2[] = {1, 2, 1, 3};
    int costs2[] = {1, 2, 2, 1};
    cout<<findPetrolPump(fuel2, costs2, sizeof(fuel2) / sizeof(fuel2[0]))<<endl;

    // Example 3
    int fuel3[] = {2, 4, 1, 3};
    int costs3[] = {3, 5, 1, 3};
    cout<<findPetrolPump(fuel3, costs3, sizeof(fuel3) / sizeof(fuel3[0]))<<endl;
  
  return 0;
}
3
4
-1

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

Επί2), είναι η πολυπλοκότητα του χρόνου. Όπου N είναι ο αριθμός των αντλιών βενζίνης στη δεδομένη είσοδο. Εδώ έχουμε πολυωνυμική πολυπλοκότητα επειδή θεωρούμε κάθε αντλία βενζίνης ως αφετηρία. Αφού ξεκινήσαμε κάθε αντλία βενζίνης ξεκινήσαμε μια πλήρη περιοδεία. Και έλεγξε αν κατά τη διάρκεια της περιοδείας το ρεζερβουάρ βενζίνης αδειάζει. Είχαμε λοιπόν Ν σημεία εκκίνησης και έπειτα κάθε σημείο εκκίνησης διέθετε αντλίες βενζίνης Ν-1. Έτσι, η χρονική πολυπλοκότητα είναι O (N ^ 2).

Διαστημική πολυπλοκότητα

Ο (1), εδώ δεν έχουμε αποθηκεύσει πληροφορίες που απαιτούνται για κάθε στοιχείο ταυτόχρονα. Και έτσι δεν έχουμε χρησιμοποιήσει πολύ χώρο. Έχουμε χρησιμοποιήσει έναν σταθερό αριθμό μεταβλητών που καθιστούσαν σταθερή την πολυπλοκότητα του χώρου.

Βέλτιστη προσέγγιση

Η βέλτιστη ιδέα είναι να λυθεί αυτό το πρόβλημα είναι να χρησιμοποιήσετε ένα ουρά. Αρχικοποιήστε ένα μεταβλητό currFuel ως 0. Συνεχίστε να πιέζετε τις αντλίες βενζίνης στην ουρά ενώ το currFuel> = 0 και μετά πιέζετε μια αντλία βενζίνης για να ουρά το ρεύμα Το καύσιμο αυξάνεται κατά (καύσιμο [i] - κόστος [i]) Εάν οποιαδήποτε στιγμή το currFuel γίνει αρνητικό, βγάλτε τις αντλίες βενζίνης από την ουρά μία προς μία έως ότου το currFuel είναι αρνητικό. Εάν υπάρχουν όλες οι αντλίες βενζίνης στην ουρά, επιστρέψτε το σημείο εκκίνησης, αλλιώς εάν δεν υπάρχει τρόπος να μπορούν οι αντλίες βενζίνης να βρίσκονται στην ουρά, επιστρέψτε -1.

Ο χώρος που χρησιμοποιείται από την ουρά μπορεί να εξοικονομηθεί εάν σχηματίσουμε μια ουρά στην ίδια τη σειρά καυσίμων και κόστους. Μπορεί να επιτευχθεί χρησιμοποιώντας δείκτες έναρξης και λήξης στις συστοιχίες.

  1. Αρχικοποιήστε την εκκίνηση, το τέλος και το currFuel ως 0, όπου η εκκίνηση αντιπροσωπεύει το σημείο εκκίνησης του φορτηγού, το τέλος αντιπροσωπεύει την επόμενη αντλία βενζίνης για επίσκεψη και το
  2. Σπρώξτε την πρώτη αντλία βενζίνης στην ουρά και αυξήστε το ρεύμα Καύσιμο κατά (καύσιμο [0] - κόστος [0]) και τέλος αύξησης.
  3. Επαναλάβετε τα επόμενα βήματα μέχρι να μην προστεθούν όλες οι αντλίες βενζίνης στην ουρά ή να βρεθεί ότι δεν υπάρχει λύση.
  4. Εάν η τιμή του currFuel γίνει αρνητική, βγάλτε την αντλία βενζίνης στη θέση εκκίνησης από την ουρά και μειώστε το currFuel κατά (καύσιμο [εκκίνηση] - κόστος [εκκίνηση]) και αυξήστε την εκκίνηση. Εάν η εκκίνηση γίνει 0, δεν υπάρχει πιθανή λύση, επιστροφή -1.
  5. Διαφορετικά, προσθέστε την αντλία βενζίνης στην άκρη της θέσης στην ουρά, αυξήστε το ρεύμα Καύσιμο κατά (καύσιμο [τέλος] - κόστος [τέλος]) και τέλος άκρο.
  6. Εάν όλες οι αντλίες βενζίνης υπάρχουν στην ουρά, δηλαδή το τέλος είναι ίσο με την εκκίνηση, επιστροφή εκκίνησης.

Κώδικας

Κωδικός JAVA για να βρείτε την πρώτη κυκλική περιήγηση που επισκέπτεται όλες τις αντλίες βενζίνης

class FindTheFirstCircularTourThatVisitsAllThePetrolPumps {
    private static int findPetrolPump(int[] fuel, int[] costs) {
        // total number of petrol pumps
        int n = fuel.length;

        // initialize start and end as 0
        int start = 0, end = 0;
        // initialize currFuel as 0
        int currFuel = 0;
        // push the first petrol pump to queue
        currFuel += (fuel[end] - costs[end]);
        // increment end
        end = (end + 1) % n;

        while (end != start || currFuel < 0)  {
            // if currFuel becomes negative, one by one pop out
            // petrol pumps from queue
            while (currFuel < 0) {
                currFuel -= (fuel[start] - costs[start]);
                start = (start + 1) % n;
                // if start again becomes 0, there is no possible solution
                if (start == 0) {
                    return -1;
                }
            }

            // Push the current petrol pump to queue and update currFuel
            currFuel += (fuel[end] - costs[end]);
            end = (end + 1) % n;
        }

        // return the start point
        return (start + 1);
    }

    public static void main(String[] args) {
        // Example 1
        int fuel1[] = new int[] {5, 2, 11, 8};
        int costs1[] = new int[] {3, 7, 2, 9};
        System.out.println(findPetrolPump(fuel1,costs1));

        // Example 2
        int fuel2[] = new int[] {1, 2, 1, 3};
        int costs2[] = new int[] {1, 2, 2, 1};
        System.out.println(findPetrolPump(fuel2, costs2));

        // Example 3
        int fuel3[] = new int[] {2, 4, 1, 3};
        int costs3[] = new int[] {3, 5, 1, 3};
        System.out.println(findPetrolPump(fuel3, costs3));
    }
}
3
4
-1

C ++ Code για να βρείτε την πρώτη κυκλική περιήγηση που επισκέπτεται όλες τις αντλίες βενζίνης

#include <iostream>
using namespace std;

int findPetrolPump(int *fuel, int *costs, int n) {
    // initialize start and end as 0
    int start = 0, end = 0;
    // initialize currFuel as 0
    int currFuel = 0;
    // push the first petrol pump to queue
    currFuel += (fuel[end] - costs[end]);
    // increment end
    end = (end + 1) % n;
    
    while(end != start || currFuel < 0) {
        // if currFuel becomes negative, one by one pop out
        // petrol pumps from queue
        while (currFuel < 0) {
            currFuel -= (fuel[start] - costs[start]);
            start = (start + 1) % n;
            // if start again becomes 0, there is no possible solution
            if (start == 0) {
                return -1;
            }
        }
        
        // Push the current petrol pump to queue and update currFuel
        currFuel += (fuel[end] - costs[end]);
        end = (end + 1) % n;
    }
    
    // return the start point
    return (start + 1);
}

int main() {
  // Example 1
    int fuel1[] = {5, 2, 11, 8};
    int costs1[] = {3, 7, 2, 9};
    cout<<findPetrolPump(fuel1, costs1, sizeof(fuel1) / sizeof(fuel1[0]))<<endl;

    // Example 2
    int fuel2[] = {1, 2, 1, 3};
    int costs2[] = {1, 2, 2, 1};
    cout<<findPetrolPump(fuel2, costs2, sizeof(fuel2) / sizeof(fuel2[0]))<<endl;

    // Example 3
    int fuel3[] = {2, 4, 1, 3};
    int costs3[] = {3, 5, 1, 3};
    cout<<findPetrolPump(fuel3, costs3, sizeof(fuel3) / sizeof(fuel3[0]))<<endl;
  
  return 0;
}
3
4
-1

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας 

Επί), Η χρήση της ουράς μας έχει εξοικονομήσει χρόνο και είμαστε σε θέση να λύσουμε το πρόβλημα σε γραμμικό χρόνο.

Διαστημική πολυπλοκότητα

Ο (1), χρησιμοποιούσαμε μια ουρά και αυτό θα μας κόστιζε γραμμική πολυπλοκότητα χώρου. Αλλά αντί αυτού, χρησιμοποιήσαμε δείκτες για να χρησιμοποιήσουμε τους αρχικούς πίνακες εισόδου ως ουρές. Και εξοικονομώντας έτσι χώρο.