ค้นหาทัวร์รอบแรกที่เยี่ยมชมปั๊มน้ำมันทั้งหมด


ระดับความยาก ยาก
ถามบ่อยใน อเมซอน ข้อเท็จจริง ไมโครซอฟท์ สแตนลี่ย์มอร์แกน 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. เริ่มต้นตัวแปร currFuel เป็น 0 ซึ่งแสดงถึงปริมาณน้ำมันในรถบรรทุก
  3. ในการเดินทางจากปั๊มน้ำมัน jth ไปยัง (j + 1) ปั๊มน้ำมัน (น้ำมันเชื้อเพลิง [j] - ราคา [j]) จำนวนเชื้อเพลิงจะถูกเติมลงใน currFuel
  4. จากปั๊มน้ำมัน ith เริ่มเดินทางไปข้างหน้าในวงกลมและเติมเชื้อเพลิงพิเศษ (น้ำมันเชื้อเพลิง [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

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

บน2), คือความซับซ้อนของเวลา โดยที่ N คือจำนวนปั๊มน้ำมันในอินพุตที่ระบุ ที่นี่เรามีความซับซ้อนของพหุนามเพราะเราถือว่าปั๊มน้ำมันแต่ละแห่งเป็นจุดเริ่มต้น หลังจากทำปั๊มน้ำมันแต่ละครั้งเมื่อเริ่มต้นเราก็ได้ทำการทัวร์ที่สมบูรณ์ และตรวจสอบว่าในระหว่างการท่องเที่ยวถังน้ำมันว่างหรือไม่ ดังนั้นเราจึงมี N จุดเริ่มต้นและจากนั้นแต่ละจุดเริ่มต้นก็มีปั๊มน้ำมัน N-1 ที่จะครอบคลุม ดังนั้นความซับซ้อนของเวลาจึงเป็น O (N ^ 2)

ความซับซ้อนของอวกาศ

O (1), ที่นี่เราไม่ได้บันทึกข้อมูลใด ๆ ที่จำเป็นสำหรับแต่ละองค์ประกอบพร้อมกัน ดังนั้นเราจึงไม่ได้ใช้พื้นที่มากนัก เราได้ใช้ตัวแปรจำนวนคงที่ซึ่งทำให้ความซับซ้อนของปริภูมิคงที่

แนวทางที่เหมาะสมที่สุด

แนวคิดที่ดีที่สุดคือการแก้ปัญหานี้คือการใช้ไฟล์ คิว. เริ่มต้นตัวแปร currFuel เป็น 0 กดปั๊มน้ำมันให้เข้าคิวต่อไปในขณะที่ currFuel> = 0 และหลังจากผลักปั๊มน้ำมันไปยังคิว currFuel จะเพิ่มขึ้นโดย (fuel [i] - cost [i]) หากเมื่อใดก็ตามที่ currFuel กลายเป็นค่าลบให้เปิดปั๊มน้ำมันออกจากคิวทีละคิวจนกว่า currFuel จะเป็นลบ หากปั๊มน้ำมัน n ทั้งหมดอยู่ในคิวให้ส่งคืนจุดเริ่มต้นมิฉะนั้นหากไม่มีวิธีที่ปั๊มน้ำมัน n สามารถอยู่ในคิวได้ให้ส่งกลับ -1

พื้นที่ที่ใช้โดยคิวสามารถบันทึกได้หากเราสร้างคิวในอาร์เรย์เชื้อเพลิงและต้นทุนเอง สามารถทำได้โดยใช้ตัวชี้จุดเริ่มต้นและจุดสิ้นสุดบนอาร์เรย์

  1. เริ่มต้น start, end และ currFuel เป็น 0 โดยที่ start แทนจุดเริ่มต้นของรถบรรทุกส่วนท้ายหมายถึงปั๊มน้ำมันตัวถัดไปที่จะไปเยี่ยมชมและ currFuel หมายถึงปริมาณเชื้อเพลิงในรถบรรทุก
  2. ดันปั้มน้ำมันตัวแรกเข้าไปในคิวและเพิ่ม currFuel โดย (fuel [0] - cost [0]) และส่วนเพิ่ม
  3. ทำซ้ำขั้นตอนถัดไปจนกว่าปั๊มน้ำมันทั้งหมดจะไม่ถูกเพิ่มลงในคิวหรือพบว่าไม่มีวิธีแก้ไข
  4. หากค่าของ currFuel กลายเป็นลบให้เปิดปั๊มน้ำมันขึ้นที่ตำแหน่งเริ่มต้นจากคิวและ currFuel ที่ลดลงโดย (เชื้อเพลิง [เริ่มต้น] - ต้นทุน [เริ่ม]) และการเริ่มต้นที่เพิ่มขึ้น หากค่าเริ่มต้นกลายเป็น 0 ไม่มีทางแก้ไขที่เป็นไปได้ให้ส่งกลับ -1
  5. อื่นให้เพิ่มปั๊มน้ำมันที่ตำแหน่งท้ายไปยังคิวเพิ่ม currFuel โดย (เชื้อเพลิง [สิ้นสุด] - ต้นทุน [สิ้นสุด]) และส่วนที่เพิ่มขึ้น
  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 (1), เราใช้คิวและนั่นจะทำให้เราเสียความซับซ้อนของสเปซเชิงเส้น แต่แทนที่จะเป็นเช่นนั้นเราใช้พอยน์เตอร์เพื่อใช้อาร์เรย์อินพุตเริ่มต้นเป็นคิว และทำให้เราประหยัดพื้นที่