იპოვნეთ პირველი წრიული ტური, რომელიც ეწვევა ყველა ბენზინის ტუმბოს


Რთული ტური Hard
ხშირად ეკითხებიან Amazon ფაქტები microsoft Morgan Stanley Zoho
Queue

პრობლემის განცხადება

პრობლემა ”იპოვნეთ პირველი წრიული ტური, რომელიც ყველა ბენზინის ტუმბოს სტუმრობს” აღნიშნავს, რომ წრიულ გზაზე არის N ბენზინის ტუმბოები. იმის გათვალისწინებით, რომ ბენზინი არის ყველა ბენზინის ტუმბო და ბენზინის რაოდენობა, რომელიც საჭიროა ორ ბენზინის ტუმბოს შორის მანძილის დასაფარავად. ასე რომ, თქვენ უნდა იპოვოთ პირველი ბენზინის ტუმბო, სადაც სატვირთო მანქანა იწყებს და შეუძლია შეავსოს წრე.
შეყვანის ფორმატია, როგორც, {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

გულუბრყვილო მიდგომა

თითოეული ბენზინის ტუმბო სათითაოდ ჩათვალეთ. თუ არსებობს შესაძლო ტური. დააბრუნეთ ბენზინის ტუმბოს ამჟამინდელი ნომერი. სხვა, თუ ბენზინის ტუმბოდან შეუძლებელია ტური, დაბრუნდი -1.

  1. აწარმოეთ მარყუჟი 1-დან n- მდე, ამ მარყუჟი განიხილავს მეორე ბენზინის ტუმბოს ამოსავალ წერტილად.
  2. ინიცირებადი ცვლადი currFuel როგორც 0, რაც წარმოადგენს ბენზინის რაოდენობას სატვირთო მანქანაში.
  3. J- ის ბენზინის ტუმბოდან (j + 1) მე -XNUMX ბენზინის ტუმბოში გადასასვლელად (საწვავი [j] - ღირებულება [j]) საწვავზე ემატება საწვავის რაოდენობა.
  4. მეორე ბენზინის ტუმბოდან დაიწყეთ წრეზე მოძრაობა და დაამატეთ დამატებითი საწვავი (საწვავი [j] - ღირებულება [j]) ყოველ ნაბიჯზე, გაიმეორეთ ეს პროცესი, სანამ currFuel> = 0.
  5. თუ სატვირთო მანქანას შეუძლია გადაადგილდეს ბენზინის ყველა ტუმბოში, დაბრუნდით i. სხვა გაგრძელება შემდეგ i.
  6. თუ არ არსებობს i, რომლისთვისაც სატვირთო მანქანას შეუძლია გადალახოს მთელი წრე, დაბრუნდით -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 ++ კოდი პირველი ცირკულარული ტურის მოსაძებნად, რომელიც ყველა ბენზინის ტუმბოს ეწვია

#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 არის ბენზინის ტუმბოების რაოდენობა მოცემულ შეყვანაში. აქ ჩვენ მრავალხმიანობის სირთულე გვაქვს, რადგან თითოეული ბენზინის ტუმბო ამოსავალ წერტილად განვიხილეთ. ყოველი ბენზინის ტუმბოს გაკეთების შემდეგ, ჩვენ სრული ტური მოვიარეთ. და შეამოწმა, ტურის დროს ხდება თუ არა ცარიელი ბენზინის ავზი. ასე რომ, ჩვენ გვქონდა N საწყისი წერტილები და შემდეგ თითოეულ საწყის წერტილს ჰქონდა N-1 ბენზინის ტუმბოები დასაფარავად. ამრიგად, დროის სირთულეა O (N ^ 2).

სივრცის სირთულე

O (1), აქ ჩვენ არ შენახული გვაქვს ინფორმაცია, რომელიც ერთდროულად საჭირო იყო თითოეული ელემენტისთვის. ამრიგად, ჩვენ დიდი ადგილი არ გამოვიყენეთ. ჩვენ გამოვიყენეთ ცვლადების მუდმივი რაოდენობა, რამაც სივრცის სირთულე მუდმივი გახადა.

ოპტიმალური მიდგომა

ოპტიმალური იდეაა ამ პრობლემის გადაჭრა არის a მდგომ. ცვლადი საწვავის ინიციალიზაცია 0. გააგრძელეთ ბენზინის ტუმბოების რიგისკენ, ხოლო currFuel> = 0, ხოლო ბენზინის ტუმბოს რიგში curr საწვავის გაზრდა ხდება (საწვავი [i] - ღირებულება [i]). თუ რომელიმე მომენტში currFuel უარყოფითი ხდება, გამოდით ბენზინის ტუმბოები რიგიდან სათითაოდ, სანამ currFuel ნეგატიურია. თუ ყველა n ბენზინის ტუმბო რიგშია, დააბრუნეთ საწყისი წერტილი, წინააღმდეგ შემთხვევაში, თუ n ბენზინის ტუმბოები რიგში დგას, დაბრუნდით -1.

სივრცის მიერ გამოყენებული სივრცის დაზოგვა შესაძლებელია, თუ საწვავის რიგში დავდგამთ რიგს და თვითღირებულების მასივს. მისი მიღწევა შესაძლებელია მასივებზე საწყისი და დასასრული მაჩვენებლების გამოყენებით.

  1. დაიწყეთ დაწყება, დასასრული და მოწვის საწვავი 0 – ს სახით, სადაც დაწყება წარმოადგენს სატვირთო მანქანის საწყის წერტილს, დასასრული წარმოადგენს შემდეგი ბენზინის ტუმბოს, რომელიც უნდა მოინახულოთ, ხოლო currFuel წარმოადგენს საწვავის რაოდენობას სატვირთო მანქანაში.
  2. პირველი ბენზინის ტუმბო მოათავსეთ რიგში და ზრდადი საწვავით საწვავი (საწვავი [0] - ღირებულება [0]) და ნამატის დასასრული.
  3. გაიმეორეთ შემდეგი ნაბიჯები მანამ, სანამ ან ბენზინის ყველა ტუმბო არ დაემატება რიგს ან აღმოჩნდება, რომ გამოსავალი არ არის.
  4. თუ currFuel– ის მნიშვნელობა უარყოფითი ხდება, გამოდით ბენზინის ტუმბო პოზიციაზე, დაიწყეთ რიგიდან და შემცირეთ currFuel (საწვავი [დაწყება] - ღირებულება [დაწყება]) და ნამატის დაწყება. თუ დაწყება 0 გახდა, შეუძლებელი გამოსავალია, დაბრუნდით -1.
  5. სხვა რიგში დაამატეთ ბენზინის ტუმბო რიგში, ნამატი currFuel by (საწვავი [ბოლო] - ღირებულება [დასასრული]) და ნამატის დასასრული.
  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 ++ კოდი პირველი ცირკულარული ტურის მოსაძებნად, რომელიც ყველა ბენზინის ტუმბოს ეწვია

#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

სირთულის ანალიზი

დროის სირთულე 

O (n), რიგის გამოყენებამ დაგვიზოგა დრო და ჩვენ შეგვიძლია პრობლემის გადაჭრა წრფივ დროში.

სივრცის სირთულე

O (1), ჩვენ რიგს ვიყენებდით და ეს დაგვჯეროდა ხაზოვანი სივრცის სირთულე. ამის ნაცვლად, ჩვენ გამოვიყენეთ მითითებები, რომ რიგებად გამოვიყენოთ საწყისი შეყვანის მასივები. და ამით ზოგავს ჩვენს სივრცეს.