Бүх бензиний насосоор зочилдог анхны дугуй аялалыг хайж олох


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Амазоны Factset Microsoft- Morgan Stanley Zoho
дараалал

Асуудлын мэдэгдэл

“Бензиний бүх насосоор зочилдог дугуй хэлбэртэй анхны аяллыг олоорой” гэсэн асуудалд дугуй зам дээр 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. Ачааны машин дахь бензиний хэмжээг илэрхийлдэг 0 гэж хувьсах гүйдлийг эхлүүлнэ.
  3. Jth бензиний насосоос (j + 1) -р шатахуун шахуурга руу явахын тулд (түлш [j] - зардал [j]) хэмжээний түлшийг currFuel дээр нэмнэ.
  4. Бензиний насосоос эхлээд тойрогтоо урагшаа алхаж, алхам тутамд нэмэлт түлш (түлш [j] - зардал [j]) нэмнэ үү, currFuel> = 0 байхад энэ үйлдлийг давт.
  5. Хэрэв ачааны машин бүх n бензиний насосоор дамжин өнгөрч чадвал 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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (n2), гэдэг нь цаг хугацааны нарийн төвөгтэй байдал юм. N бол өгөгдсөн оролт дахь бензиний шахуургын тоо. Бензиний насос бүрийг эхлэх цэг гэж үзсэн тул энд бид олон гишүүний нарийн төвөгтэй юм. Бензиний насос бүрийг хийж эхэлсний дараа бид бүтэн аялал хийлээ. Аяллын үеэр бензин сав хоосорч байгаа эсэхийг шалгасан. Тиймээс бид N гарааны цэгүүдтэй байсан бөгөөд дараа нь эхлэх цэгүүд бүрийг хамарсан N-1 шатахуун шахуургатай болсон. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь O (N ^ 2) болно.

Сансрын нарийн төвөгтэй байдал

O (1), Энд бид элемент тус бүрт шаардагдах мэдээллийг хадгалаагүй болно. Тиймээс бид маш их зай ашиглаагүй байна. Бид орон зайн нарийн төвөгтэй байдлыг тогтмолжуулсан тогтмол тооны хувьсагчийг ашигласан болно.

Оновчтой арга

Энэ асуудлыг шийдэх оновчтой санаа бол ашиглах явдал юм дараалал. Хувьсах гүйдлийг 0 гэж эхлүүл. Хэрэв ямар ч үед шатахуун сөрөг болж байвал шатахуун шахах шахуургыг дараалал дээрээс шатахуун хасах хүртэл гаргана. Хэрэв бүх n шатахуун шахуурга дараалалд байгаа бол эхлэх цэгийг буцааж өг, өөрөөр хэлбэл n шатахуун шахуурга дараалалд багтах ямар ч боломжгүй бол -0 буцах хэрэгтэй.

Хэрэв бид шатахуун болон зардлын массив дээр дараалал үүсгэсэн бол дарааллын ашигласан зайг хэмнэж болно. Массив дээрх эхлэх ба төгсгөлийн заагчийг ашиглан үүнийг хийж болно.

  1. Эхлэл, төгсгөл ба гүйдлийг эхлүүлнэ Шатахууныг 0 гэж эхлүүлэх бөгөөд эхлэл нь ачааны тэрэгний эхлэх цэгийг, төгсгөл нь зочлох дараагийн бензин насосыг илэрхийлж, шатахуун нь ачааны тэрэгний түлшний хэмжээг илэрхийлнэ.
  2. Эхний бензиний насосыг дараалалд оруулаад гүйдэл нэмнэ Түлш (шатахуун [0] - зардал [0]) ба өсөлтийн төгсгөл.
  3. Бүх шатахууны шахуургыг дараалалд нэмэхгүй эсвэл шийдэлгүй болох хүртэл дараагийн алхмуудыг давт.
  4. Хэрэв 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 ++ код

#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), бид дараалал ашиглаж байсан бөгөөд энэ нь бидэнд шугаман орон зайн нарийн төвөгтэй байдлыг шаарддаг. Гэхдээ үүний оронд бид эхний оролтын массивыг дараалал болгон ашиглахын тулд заагчийг ашигласан. Тиймээс бидэнд орон зай хэмнэх болно.