Bu yazı Lemonade Change Leetcode Solution-da
Mündəricat
Problem bəyanat
Problemdə ”Limonad Dəyişikliyi” var queue müştərilərin. 5 rupiyə olan limonad bizdən almaq istəyirlər. Müştərilər bizə 5 rupi, 10 rupi və ya 20 rupi verə bilərlər. Müştərilərə doğru miqdarda dəyişikliyi qaytarmaq istəyirik. Əvvəlcə heç bir dəyişikliyimiz yoxdur. Müvafiq miqdarda dəyişikliyi hər bir müştəriyə uğurla qaytara biləriksə, cavab verməliyik.
misal
bills = [5,5,5,10,20]
true
Explanation:
Başlanğıc üç əməliyyatda heç bir dəyişiklik etməyimiz lazım deyil. Üç əməliyyatdan sonra 5 rupi olan üç sikkəmiz var. Dördüncü əməliyyat zamanı 5 rupi qaytarmalıyıq. Yəni dördüncü əməliyyatdan sonra 2 rupi 5 sikkə və 10 rupi bir sikkə var. Beşinci əməliyyatda 15 rupi qaytarmalıyıq. Bir on rupi sikkə və bir beş rupi sikkə qaytara bilərik. Bütün əməliyyatlar başa çatdıqca cavab doğrudur.
Yanaşma
Bu, acgöz alqoritmdən istifadə edərək tətbiqetmə problemidir. Massivdə verilən dəyərlər müştərilərin növbəsini təmsil etdiyi üçün, eyni zamanda dizini keçdiyimiz zaman əməliyyatlar da edəcəyik. Başlanğıcda heç bir dəyişikliyimiz yoxdur, ona görə beş, on və iyirmi rupi sikkələrin sayı sıfırdır.
Ssenarilərin hər birini tək-tək axtaraq:
- Müştəri beş rupi ödəyərsə, ona heç bir dəyişiklik etməyimiz lazım deyil və yanımızda olan beş rupi sikkənin sayı bir dəfəyə qədər artacaq.
- Deyək ki, müştəri on rupi ödəyir, onda dəyişikliyi vermək üçün ən azı bir beş rupi sikkəmiz olmalıdır. Bunu edə bilməsək, hər kəsə düzgün miqdarda dəyişiklik vermək mümkün olmadığına görə yalnış cavab verəcəyik.
- Müştəri iyirmi rupi ödəyərsə, ona iki fərqli şəkildə dəyişiklik verə bilərik:
- On rupi sikkəmiz və beş rupi sikkəmiz varsa, ona cəmi on beş rupi qaytara bilərik. Uğursuz olsaq, ikinci üsulu axtaracağıq.
- Cəmi on beş rupi qaytarmaq məcburiyyətində olduğumuz üçün hər birinə beş rupi olan üç sikkə verə bilərik. Bunun üçün ən azı 3 sikkə beş rupiyə sahib olmalıyıq. Bunu edə bilməsək, hər kəsə düzgün miqdarda dəyişiklik vermək mümkün olmadığına görə yalan qayıdırıq.
Bütün müştərilərə doğru miqdarda dəyişiklik təmin etsəydik, gerçək qayıdacağıq.
Kodu
Lemonade Change Leetcode Solution üçün C ++ kodu
#include <bits/stdc++.h>
using namespace std;
bool lemonadeChange(vector<int>& bills) {
int n=bills.size();
int five=0,ten=0,twenty=0;
for(int i=0;i<n;i++)
{
if(bills[i]==5)five++;
else if(bills[i]==10)
{
ten++;
if(five>0)five--;
else return false;
}
else
{
twenty++;
if(ten>0&&five>0){ten--;five--;}
else if(five>2)five=five-3;
else return false;
}
}
return true;
}
int main()
{
vector<int> arr = {5,5,5,10,20};
cout <<boolalpha;
cout<<lemonadeChange(arr)<<endl;
return 0;
}
true
Lemonade Change Leetcode Solution üçün Java kodu
import java.util.Arrays;
public class Tutorialcup {
public static boolean lemonadeChange(int[] bills) {
int n=bills.length;
int five=0,ten=0,twenty=0;
for(int i=0;i<n;i++)
{
if(bills[i]==5)five++;
else if(bills[i]==10)
{
ten++;
if(five>0)five--;
else return false;
}
else
{
twenty++;
if(ten>0&&five>0){ten--;five--;}
else if(five>2)five=five-3;
else return false;
}
}
return true;
}
public static void main(String[] args) {
int [] arr = {5,5,5,10,20};
boolean ans= lemonadeChange(arr);
System.out.println(ans);
}
true
Limonad Dəyişdirmə Leetcode Solüsyonunun Mürəkkəblik Analizi
Zaman mürəkkəbliyi
Yuxarıdakı kodun zaman mürəkkəbliyi O (n) çünki vərəqələr seriyasından yalnız bir dəfə keçirik. Burada n hesablar massivinin uzunluğu.
Kosmik mürəkkəblik
Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki cavabları saxlamaq üçün yalnız dəyişəndən istifadə edirik.
