Limonad dəyişdirmə Leetcode həll

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Atlassian
alqoritmlər kodlaşdırma Görməmiş müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 29

Bu yazı Lemonade Change Leetcode Solution-da

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:

Limonad dəyişdirmə Leetcode həllPin

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:

  1. 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.
  2. 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.
  3. Müştəri iyirmi rupi ödəyərsə, ona iki fərqli şəkildə dəyişiklik verə bilərik:
    1. 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.
    2. 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.

References

Şərh yaz

Translate »