X သည် Queue မှလူများအားပြောင်းလဲမှုရှိမရှိစစ်ဆေးပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ
ဆံပင်ကြိုး

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

X သည်ရေခဲမုန့်ရောင်းသူဖြစ်ပြီးလူတစ် ဦး ၌စောင့်နေသူများလည်းရှိသည် ဆံပင်ကြိုး ရေခဲမုန့်ဝယ်ဖို့။ Arr [i] သည်လူတန်းစားရှိလူတစ် ဦး ချင်း၏တန်ဖိုးကိုရည်ညွှန်းသည်။ denomination ၏ဖြစ်နိုင်သောတန်ဖိုးများသည် ၅၊ ၁၀ နှင့် ၂၀ ဖြစ်သည်။ အကယ်၍ X ၏ကန ဦး ဟန်ချက်သည် 5 ဖြစ်ပြီးရေခဲမုန့်၏ကုန်ကျစရိတ်သည် ၅ ဖြစ်ပါက၊ အဆိုပါတန်းစီ၌ရပ်နေသောလူအပေါင်းတို့အားပြောင်းလဲမှုပေးနိုင်မည်နည်း ထို့ကြောင့်ပြtheနာမှာ“ X သည် Queue မှလူတိုင်းကိုပြောင်းလဲမှုရှိမရှိစစ်ဆေးပါ” ဖြစ်သည်။

X သည် Queue မှလူများအားပြောင်းလဲမှုရှိမရှိစစ်ဆေးပါ

ဥပမာ

arr[] = {5, 5, 10, 20}
true
arr[] = {10, 5, 5, 5, 5, 5}
false
arr[] = {5, 5, 5, 20, 5, 10}
true

Queue သည်လူတိုင်းကိုပြောင်းလဲမှုရှိမရှိစစ်ဆေးရန် Algorithm ကိုစစ်ဆေးရန်

စိတ်ကူး

စိတ်ကူးသည် X ရှိသည့် ၅၊ ၁၀၊ ၂၀ တို့၏ဂိုဏ်းဂဏများကိုခြေရာခံရန်ဖြစ်သည်။ ၎င်းတို့ကို count5, count10 နှင့် count20 တို့ဖြင့်ကိုယ်စားပြုပါစေ။ အပြောင်းအလဲကိုတတ်နိုင်သလောက်မြင့်မားသောငွေကြေးဖြင့်ပြန်ပို့ခြင်းသည်အကောင်းဆုံးဖြစ်သည်။ အမှုပေါင်းသုံးခုရှိပါတယ်

  • ဆိုက်ရောက် [i] = ၅ ရက်
    5 အားဖြင့်နှစ်တိုး count1
  • ဆိုက်ရောက် [i] = ၅ ရက်
    count5> 0 ဖြစ်လျှင် count10 ကို 1 ဖြင့်တိုး။ countment 5 ကိုတိုးပါ
  • ဆိုက်ရောက် [i] = ၅ ရက်
    count10> 0 and count5> 0, count20 ကို 1 တိုးပြီး countment 10 နှင့် count5 ကို 1 ဖြင့်တိုးပါ။
    အခြားအရာများမှာ count5> 2၊ count20 ကို 1 ဖြင့်တိုးစေခြင်း၊

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

  1. သုံး variable ကို count5, count10 နှင့် count20 0 အဖြစ် XNUMX စတင်။
  2. ပေးထားသောဖြတ်သန်း အခင်းအကျင်း.
  3. အကယ်၍ arr [i] သည် ၅ ဖြစ်ပါက count5 ကို 5 တိုးပါ။
  4. သို့မဟုတ်လျှင် arr [i] သည် ၁၀ ဖြစ်လျှင်၊ count10> 5 ဟုတ်မဟုတ်စစ်ဆေးပါ၊ ဟုတ်လျှင်၊ အရေအတွက်တိုး။ ၁ ကို ၁ နှင့်အနိမ့်ဆုံး count0 ကို 10 ဖြင့်စစ်ဆေးပါ။ သို့မဟုတ်ပါက X သည်ဖောက်သည်များအားလုံးကိုပြောင်းလဲမှုမပေးနိုင်ပါ၊ မှားယွင်းပါ။
  5. သို့မဟုတ်လျှင် arr [i] သည် ၂၀ ဖြစ်ပါက count20 သည် ၀ ထက်ကြီး။ ၊ count10 သည်သုညထက်ကြီးပါကမှန်လျှင်မှန်လျှင် count0 ကို ၁ နှင့်နှစ်အရေအတွက် count5 နှင့် count0 ကိုတစ်အရေအတွက်တိုးမြှင့်ပါက count20 သည် ၂ ထက်ကြီးသည်ရှိမရှိစစ်ဆေးပါ။ ဟုတ်ကဲ့၊ အတိုး count1 ကို 5 နှင့်အနိမ့်ဆုံး count10 သည် 5 ဖြင့်တိုးသွားလျှင်၊ X သည်ဖောက်သည်များအားလုံးကိုပြောင်းလဲမှုမပေးနိုင်ပါ။
  6. အကယ်၍ X သည်ဖောက်သည်များအားလုံးကိုပြောင်းလဲမှုကိုပြန်ပေးနိုင်ခဲ့ပါက true ကိုပြန်သွားပါ။

ကုဒ်

Java Code သည် Queue မှလူများအားပြောင်းလဲမှုရှိမရှိစစ်ဆေးရန်

class CheckIfXCanGiveChangeToEveryPersonStandingInQueue {
    private static boolean checkIfPossible(int[] arr) {
        // initialize count0, counnt10 and count20 as 0
        int count5 = 0, count10 = 0, count20 = 0;
        
        // traverse in the array
        for (int i = 0; i < arr.length; i++) {
            // Case 1 : arr[i] = 5
            if (arr[i] == 5) {
                // increment count5 by 1
                count5++;
            }
            // Case 2 : arr[i] = 10
            else if (arr[i] == 10) {
                // if there are some 5 rs coins return 1
                if (count5 > 0) {
                    // decrement count5 by 1 and increment count10 by 1
                    count5--;
                    count10++;
                } else {
                    // if there are not, X cannot give change to everyone
                    return false;
                }
            }
            // Case 3 : arr[i] = 20
            else {
                // if there are some 10 rs coins and some 5 rs coin return one one each
                if (count10 > 0 && count5 > 0) {
                    count10--;
                    count5--;
                    count20++;
                } else if (count5 > 2) {
                    // else if there are 3 or more 5 rs coins return 3
                    count5 -= 3;
                    count20++;
                } else {
                    // X cannot give chnage to everyone
                    return false;
                }
            }
        }

        // X can give change to everyone
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 5, 10, 20};
        System.out.println(checkIfPossible(arr1));

        // Example 2
        int arr2[] = new int[] {10, 5, 5, 5, 5, 5};
        System.out.println(checkIfPossible(arr2));

        // Example 3
        int arr3[] = new int[]{5, 5, 5, 20, 5, 10};
        System.out.println(checkIfPossible(arr3));
    }
}
true
false
true

C ++ Code သည် Queue မှလူများအားပြောင်းလဲမှုရှိမရှိစစ်ဆေးရန်

#include<bits/stdc++.h> 
using namespace std; 

bool checkIfPossible(int *arr, int n) {
    // initialize count0, count10 and count20 as 0
    int count5 = 0, count10 = 0, count20 = 0;

    // traverse in the array
    for (int i = 0; i < n; i++) {
        // Case 1 : arr[i] = 5
        if (arr[i] == 5) {
            // increment count5 by 1
            count5++;
        }
        // Case 2 : arr[i] = 10
        else if (arr[i] == 10) {
            // if there are some 5 rs coins return 1
            if (count5 > 0) {
                // decrement count5 by 1 and increment count10 by 1
                count5--;
                count10++;
            } else {
                // if there are not, X cannot give change to everyone
                return false;
            }
        }
        // Case 3 : arr[i] = 20
        else {
            // if there are some 10 rs coins and some 5 rs coin return one one each
            if (count10 > 0 && count5 > 0) {
                count10--;
                count5--;
                count20++;
            } else if (count5 > 2) {
                // else if there are 3 or more 5 rs coins return 3
                count5 -= 3;
                count20++;
            } else {
                // X cannot give chnage to everyone
                return false;
            }
        }
    }

    // X can give change to everyone
    return true;
}

int main() {
    // Example 1
    int arr1[] = {5, 5, 10, 20};
    if (checkIfPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    int arr2[] = {10, 5, 5, 5, 5, 5};
    if (checkIfPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    int arr3[] = {5, 5, 5, 20, 5, 10};
    if (checkIfPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
}
true
false
true

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

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

အို ()) ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာ n element တွေရှိတဲ့ input array ကိုဖြတ်သန်းသွားလို့ပဲ။ ဒါက algorithm ကို linear time မှာ run ဖို့ပါ။

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

အို (၁)၊ ဘာလို့လဲဆိုတော့ငါတို့က array တစ်ခုမသုံးခဲ့ဘူး။ donly သုံးခုကိုအသုံးပြုပြီးစဉ်ဆက်မပြတ်နေရာယူသည်။ ဒီတော့စဉ်ဆက်မပြတ်အာကာသရှုပ်ထွေး။
ဘယ်မှာ n ဖောက်သည်စုစုပေါင်းအရေအတွက်သည်။