ស្វែងរកដំណើរទេសចរណ៍រាងជារង្វង់ដំបូងដែលទស្សនាម៉ាស៊ីនបូមសាំងទាំងអស់


កម្រិតលំបាក រឹង
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon រោងចក្រ ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Morgan Stanley Zoho
ជួរ

តារាង​មាតិកា

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ ស្វែងរកដំណើរទេសចរណ៍រាងជារង្វង់ដំបូងដែលទស្សនាម៉ាស៊ីនបូមសាំងទាំងអស់” ចែងថាមានម៉ាស៊ីនបូមសាំង N នៅលើផ្លូវរាងជារង្វង់។ បានផ្តល់ឱ្យប្រេងឥន្ធនៈដែលរាល់ម៉ាស៊ីនបូមសាំងមាននិងបរិមាណប្រេងឥន្ធនៈដែលត្រូវការដើម្បីគ្របដណ្ដប់ចម្ងាយរវាងម៉ាស៊ីនបូមសាំងពីរ។ ដូច្នេះអ្នកត្រូវរកម៉ាស៊ីនបូមសាំងដំបូងគេដែលឡានដឹកទំនិញចាប់ផ្តើមហើយអាចបញ្ចប់រង្វង់។
ទ្រង់ទ្រាយបញ្ចូលគឺដូចជា {x, y} ដែល x គឺជាសាំងដែលម៉ាស៊ីនបូមសាំងមានហើយ y គឺជាឥន្ធនៈដែលត្រូវការដើម្បីបូមចេញពីម៉ាស៊ីនបូមសាំងនេះទៅម៉ាស៊ីនបូមសាំងបន្ទាប់។
ប្រសិនបើមិនមានដំណើរទស្សនកិច្ចដែលអាចធ្វើបានទេលទ្ធផល -១ ។

ឧទាហរណ៍

{{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. ដំណើរការរង្វិលជុំចាប់ពីលេខ ១ ដល់លេខ ១ រង្វិលជុំនេះចាត់ទុកម៉ាស៊ីនបូមសាំងជាចំណុចចាប់ផ្តើម។
  2. ផ្តួចផ្តើមការផ្លាស់ប្តូរអថេរមួយដូចជា ០ ដែលតំណាងឱ្យបរិមាណប្រេងសាំងនៅក្នុងឡានដឹកទំនិញ។
  3. ដើម្បីធ្វើដំណើរពីម៉ាស៊ីនបូមសាំងទី ៥ ទៅ (ជ។ ជ។ ១) ម៉ាស៊ីនបូមសាំងទី ៣ (ឥន្ធនៈ [ច] - ថ្លៃ [ច]) បរិមាណប្រេងឥន្ធនៈត្រូវបានបន្ថែមទៅប្រូហ្វាល។
  4. ពីម៉ាស៊ីនបូមសាំងចាប់ផ្តើមធ្វើដំណើរទៅមុខក្នុងរង្វង់ហើយបញ្ចូលឥន្ធនៈបន្ថែម (ឥន្ធនៈ [ច] - ថ្លៃ [ច]) នៅគ្រប់ជំហានធ្វើម្តងទៀតដំណើរការនេះខណៈពេលដែលក្រេហ្វហ្វួរ> = ០ ។
  5. ប្រសិនបើឡានដឹកទំនិញអាចឆ្លងកាត់ម៉ាស៊ីនបូមទឹក n ទាំងអស់សូមត្រលប់មកខ្ញុំវិញ។ បន្តទៀតសំរាប់ខ្ញុំបន្ទាប់។
  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 ++ ដើម្បីស្វែងរកដំណើរទេសចរណ៍រាងជារង្វង់ដំបូងដែលទស្សនាម៉ាស៊ីនបូមសាំងទាំងអស់

#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) ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), នៅទីនេះយើងមិនបានរក្សាទុកព័ត៌មានដែលត្រូវការសម្រាប់ធាតុនីមួយៗក្នុងពេលដំណាលគ្នាទេ។ ដូច្នេះហើយយើងមិនបានប្រើប្រាស់កន្លែងទំនេរច្រើនទេ។ យើងបានប្រើចំនួនថេរនៃអថេរដែលធ្វើអោយភាពស្មុគស្មាញនៃលំហថេរ។

វិធីសាស្រ្តល្អបំផុត

គំនិតដែលប្រសើរបំផុតគឺត្រូវដោះស្រាយបញ្ហានេះគឺប្រើក ជួរ។ បន្តជំរុញម៉ាស៊ីនបូមសាំងទៅជួរខណៈពេលដែលប្រេងម៉ាស៊ូត> = ០ ហើយបន្ទាប់ពីរុញម៉ាស៊ីនបូមសាំងទៅជួរ currFuel ត្រូវបានបង្កើនដោយ (ប្រេងឥន្ធនៈ [i] - ថ្លៃដើម [ខ្ញុំ]) ។ ប្រសិនបើនៅពេលណាមួយ currFuel ក្លាយជាអវិជ្ជមានលេចឡើងលេចបូមប្រេងពីជួរមួយទៅមួយរហូតដល់ currFuel គឺអវិជ្ជមាន។ ប្រសិនបើម៉ាស៊ីនបូមសាំង n ទាំងអស់មាននៅក្នុងជួរសូមត្រឡប់ចំណុចចាប់ផ្តើមបើមិនមានវិធីណាម៉ាស៊ីនបូមសាំង n អាចស្ថិតនៅក្នុងជួរទេត្រឡប់ -0 ។

ចន្លោះដែលបានប្រើដោយជួរអាចត្រូវបានរក្សាទុកប្រសិនបើយើងបង្កើតជួរក្នុងជួរឥន្ធនៈនិងថ្លៃដើម។ វាអាចត្រូវបានសម្រេចដោយប្រើចង្អុលនិងចាប់ផ្តើមនៅលើអារេ។

  1. ចាប់ផ្តើមការចាប់ផ្តើមបញ្ចប់និង currFuel ជា 0 ដែលការចាប់ផ្តើមតំណាងឱ្យចំណុចចាប់ផ្តើមនៃឡានដឹកទំនិញបញ្ចប់តំណាងឱ្យម៉ាស៊ីនបូមសាំងបន្ទាប់ដើម្បីទស្សនាហើយ currFuel តំណាងឱ្យបរិមាណប្រេងឥន្ធនៈនៅក្នុងឡានដឹកទំនិញ។
  2. រុញម៉ាស៊ីនបូមសាំងដំបូងចូលទៅក្នុងជួរនិងបង្កើនចំណុះប្រេងឥន្ធនៈដោយ (ឥន្ធនៈ [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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា 

អូ (n), ការប្រើជួរបានជួយសន្សំសំចៃពេលវេលាហើយយើងអាចដោះស្រាយបញ្ហាបានតាមពេលវេលា។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), យើងបានប្រើជួរហើយនោះនឹង ធ្វើឲ្យ យើងខាតបង់ទំហំស្មុគស្មាញ។ ប៉ុន្តែជំនួសមកវិញយើងបានប្រើចង្អុលដើម្បីប្រើជួរបញ្ចូលដំបូងដែលដាក់ជាជួរ។ ហើយដូច្នេះការសន្សំទំហំរបស់យើង។