Petrol Pumps အားလုံးသို့လည်ပတ်မည့်ပထမဆုံးမြို့ပတ်ခရီးစဉ်ကိုရှာပါ


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် အမေဇုံ အချက်အလက် Microsoft က မော်ဂန်စတန်လေ Zoho
ဆံပင်ကြိုး

ပြProbleနာဖော်ပြချက်

“ Petrol Pumps အားလုံးကိုလည်ပတ်သည့်ပထမ ဦး ဆုံးမြို့ပတ်ခရီးစဉ်ကိုရှာပါ” ပြTheနာကမြို့ပတ်လမ်းတစ်လျှောက် N ဓာတ်ဆီပန့်များရှိသည်ဟုဖော်ပြသည်။ ဓာတ်ဆီစုပ်စက်တိုင်းတွင်ရှိသည့်ဓာတ်ဆီနှင့်ဓာတ်ဆီပန့်နှစ်ခုကြားအကွာအဝေးကိုဖုံးလွှမ်းရန်လိုအပ်သောဓာတ်ဆီပမာဏတို့ကြောင့်ဖြစ်သည်။ ဒါကြောင့်သင်ထရပ်ကားတစ်စင်းစတင်ပြီးစက်ဝိုင်းကိုအပြီးသတ်နိုင်တဲ့ပထမဆုံးဓာတ်ဆီပန့်ကိုရှာဖို့လိုတယ်။
input ပုံစံသည် {x, y}၊ x သည်ဓာတ်ဆီစုပ်စက်တွင်ရှိသည်။ y သည်ဤဓာတ်ဆီ pump မှနောက်ဓာတ်ဆီ pump သို့ရောက်ရှိရန်လိုအပ်သောလောင်စာဖြစ်သည်။
ဖြစ်နိုင်သောခရီးစဉ်မရှိပါက output -1 ။

ဥပမာ

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

 

Petrol Pumps အားလုံးသို့လည်ပတ်မည့်ပထမဆုံးမြို့ပတ်ခရီးစဉ်ကိုရှာပါ

 

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

နုံချဉ်းကပ်နည်း

တစ်ခုချင်းစီကိုတစ် ဦး ချင်းစီဓာတ်ဆီစုပ်စက်ကိုစတင်အမှတ်အဖြစ်စဉ်းစားပါ။ ဖြစ်နိုင်ဖွယ်ခိုင်လုံသောခရီးစဉ်ရှိလျှင်။ လက်ရှိဓာတ်ဆီ pump ကိုနံပါတ်ပြန်ပေးပါ မည်သည့်ဓာတ်ဆီစုပ်စက်မှမဆိုခရီးသွားခွင့်မရှိပါက -1 သို့ပြန်သွားပါ။

  1. 1 မှ n သို့ကွင်းဆက်တစ်ခုလည်ပတ်ပါ။ ဤကွင်းဆက်သည် i-petrol pump ကိုအစမှတ်ဖြစ်သည်။
  2. ထရပ်ကားထဲတွင်ဓာတ်ဆီပမာဏကိုကိုယ်စားပြုသော currFuel ကို 0 အဖြစ်ပြောင်းလဲပါ။
  3. jth petrol pump မှ (j + 1) th petrol pump သို့သွားရန် (fuel [j] - cost [j]) လောင်စာပမာဏကို currFuel သို့ထည့်သည်။
  4. ith petrol pump မှ စ၍ စက်ဝိုင်းရှေ့တွင် စတင်၍ အဆင့်တိုင်းတွင်အပိုလောင်စာ (လောင်စာ [ည] - ကုန်ကျစရိတ် [ည]) ကိုထည့်ပါ။ currFuel> = 0 စဉ်ဤလုပ်ငန်းစဉ်ကိုပြန်လုပ်ပါ။
  5. အကယ်၍ ထရပ်ကားသည် n ဓာတ်ဆီပန့်များအားလုံးကို ဖြတ်၍ ဖြတ်သွားနိုင်လျှင် i ။ သို့ပြန်သွားပါ။ ကျန်သည်နောက်တစ်ခုအတွက်ဆက်လုပ်သည်။
  6. အကယ်၍ ထရပ်ကားသည်စက်ဝိုင်းတစ်ခုလုံးကိုဖြတ်သန်းနိုင်သော i မရှိပါက -1 ကိုပြန်သွားပါ။

ကုဒ်

JAVA ကုဒ်နံပါတ်သည်ပထမဆုံးသောလည်ပတ်လည်ပတ်မှုခရီးစဉ်အား Petrol Pumps အားလုံးသို့လည်ပတ်သည်

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 ++ ကုဒ်နံပါတ်သည် Petrol Pumps များအားလုံးသို့လည်ပတ်သည်

#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 သည်ပေးထားသောသွင်းအားစုရှိဓာတ်ဆီပန့်အရေအတွက်ဖြစ်သည်။ ဤနေရာတွင်ကျွန်ုပ်တို့သည် polynomial ရှုပ်ထွေးမှုရှိသည်။ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည်တစ် ဦး ချင်းစီဓာတ်ဆီစုပ်စက်ကိုစတင်မှတ်အဖြစ်သတ်မှတ်ခဲ့ခြင်းကြောင့်ဖြစ်သည်။ တစ် ဦး ချင်းစီဓာတ်ဆီ pump ကိုစတင်အဖြစ်စတင်ပြီးနောက်ကျနော်တို့ပြီးပြည့်စုံသောခရီးစဉ်ကိုဖန်ဆင်းတော်မူ၏။ နှင့်ခရီးစဉ်အတွင်းဓာတ်ဆီအကြံပေးအဖွဲ့ဗလာရရှိခြင်းရှိမရှိစစ်ဆေးခဲ့သည်။ ဒါကြောင့်ကျွန်မတို့မှာ N စမှတ်တွေရှိတယ်၊ ပြီးတော့စမှတ်တစ်ခုစီမှာဖုံးအုပ်ဖို့ N-1 ဓာတ်ဆီပန့်တွေရှိတယ်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးအို (N ^ 2) ဖြစ်ပါတယ်။

အာကာသရှုပ်ထွေးမှု

အို (၁)၊ ဒီနေရာမှာ element တစ်ခုချင်းစီအတွက်လိုအပ်သောမည်သည့်သတင်းအချက်အလက်ကိုမျှမသိမ်းဆည်းပါ။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်နေရာများစွာကိုအသုံးမပြုခဲ့ကြပါ။ အာကာသရှုပ်ထွေးမှုကိုစဉ်ဆက်မပြတ်ဖြစ်စေသောစဉ်ဆက်မပြတ်ပြောင်းလဲနိုင်သောကိန်းဂဏန်းများကိုကျွန်ုပ်တို့အသုံးပြုခဲ့သည်။

အကောင်းဆုံးချဉ်းကပ်နည်း

အကောင်းဆုံးအယူအဆမှာဤပြproblemနာကိုဖြေရှင်းရန်ဖြစ်သည် ဆံပင်ကြိုး။ currFuel ကို variable အဖြစ် 0 အဖြစ်စတင်ပါ။ currFuel> = 0 စဉ်တွင်တန်းစီရန်ဓာတ်ဆီ pumps များကို ဆက်၍ တွန်းအားပေးပါ။ petrol pump ကိုတန်းစီရန်တွန်းအားပေးပြီးနောက် currFuel သည် (လောင်စာ [i] - ကုန်ကျစရိတ် [i]) အားဖြင့်တိုးလာသည်။ အကယ်၍ မည်သည့်အချိန်တွင် currFuel သည်အနုတ်လက္ခဏာဖြစ်လာသည်ဆိုလျှင်၊ လူတန်းမှတစ်ဆင့် currFuel သည်အနုတ်လက္ခဏာမရောက်မှီတိုင်အောင် petrol pumps ကိုထုတ်ပစ်ပါ။ n ဓာတ်ဆီပန့်များအားလုံးတန်းစီတွင်ရှိနေပါက n အမှတ်တံဆိပ်ထဲတွင် n ဓာတ်ဆီပန့်များရှိနိုင်သည့်လမ်းမရှိလျှင်အခြားအစကိုပြန်ပို့ပါ -1 သို့ပြန်သွားပါ။

အကယ်၍ ကျွန်ုပ်တို့သည်လောင်စာနှင့်ကုန်ကျစရိတ်ခင်းကျင်းမှုတွင်တန်းစီထားလျှင်တန်းစီအသုံးပြုသောနေရာလွတ်ကိုသိမ်းဆည်းနိုင်သည်။ ၎င်းကို Array တွင် start နှင့် end pointers အသုံးပြု၍ ရရှိနိုင်သည်။

  1. start, end နှင့် currFuel ကို 0 အဖြစ်စတင်ပါ၊ start သည်ထရပ်ကား၏အစကိုကိုယ်စားပြုသည်၊ အဆုံးသည်လာမည့်နောက်ဆီဓာတ်ဆီစည်ကိုကိုယ်စားပြုပြီး currFuel သည်ထရပ်ကားထဲတွင်လောင်စာပမာဏကိုကိုယ်စားပြုသည်။
  2. ပထမ ဦး ဆုံးဓာတ်ဆီ pump ကိုတန်းစီ။ currFuel အားတိုးမြှင့်ခြင်း (ကုန်ကျမှု [0] - ကုန်ကျမှု [0]) နှင့် increment end သို့တွန်းပါ။
  3. နောက်ထပ်အဆင့်များကိုဓာတ်ဆီပန့်များအားလုံးတန်းစီရန်မထည့်မခြင်းသို့မဟုတ်ဖြေရှင်းနည်းမရှိကြောင်းမတွေ့ရှိမှီနောက်တစ်ခါထပ်လုပ်ပါ။
  4. အကယ်၍ currFuel ၏တန်ဖိုးသည်အနုတ်လက္ခဏာဖြစ်လာလျှင်၊ အနေအထား မှစတင်၍ ဓာတ်ဆီစုပ်စက်မှထွက်ရန်နှင့် currFuel အားလောင်ကျွမ်းမှု (လောင်စာ [start] - cost - start]) နှင့်စတင်တိုးခြင်းဖြင့်ထွက်ပေါ်လာပါ။ အကယ်၍ start သည် 0 ဖြစ်လာလျှင်ဖြစ်နိုင်သောဖြေရှင်းချက်မရှိပါ။ -1 ကိုပြန်သွားပါ။
  5. ကျန်အနေအထားကိုအနေအထားအဆုံးမှာဓာတ်ဆီစုပ်စက်ကိုထည့်ပြီး၊ currFuel အားတိုးမြှင့်ခြင်း (ကုန်ကျစရိတ် [အဆုံး] - လောင်စာ]) နှင့်အဆုံးတိုးခြင်းတို့ကိုထည့်ပါ။
  6. အကယ်၍ ဓာတ်ဆီပန့်အားလုံးတန်းစီတွင်ရှိနေလျှင်အဆုံးသတ်သည်ညီမျှသည်။

ကုဒ်

JAVA ကုဒ်နံပါတ်သည်ပထမဆုံးသောလည်ပတ်လည်ပတ်မှုခရီးစဉ်အား Petrol Pumps အားလုံးသို့လည်ပတ်သည်

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 ++ ကုဒ်နံပါတ်သည် Petrol Pumps များအားလုံးသို့လည်ပတ်သည်

#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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး 

အို ()) queue ကိုသုံးခြင်းကကျွန်တော်တို့ကိုအချိန်သက်သာစေပြီးပြlinearနာကို linear အချိန်မှာဖြေရှင်းနိုင်သည်။

အာကာသရှုပ်ထွေးမှု

အို (၁)၊ ကျနော်တို့တန်းစီသုံးပြီးကျွန်တော်တို့ကို linear အာကာသရှုပ်ထွေးကုန်ကျကြလိမ့်မယ်။ ဒါပေမယ့်အစားအဲဒီအစားကျနော်တို့ကန ဦး input Array ကို Queue တွေအဖြစ်သုံးဖို့ pointers တွေသုံးခဲ့တယ်။ ဒီလိုနဲ့ကျွန်တော်တို့ကိုနေရာချတာ။