ლიმონათის შეცვლა Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Atlassian
ხარბ LeetCode

ეს პოსტი მოცემულია ლიმონათის შეცვლის შესახებ Leetcode Solution

პრობლემის განცხადება

პრობლემში ”ლიმონათის შეცვლა” არის ა მდგომ მომხმარებელთა. მათ სურთ ჩვენგან ლიმონათის ყიდვა, რომელიც 5 მანეთი ღირს. მომხმარებელს შეუძლია მოგვცეს 5 მანეთი, 10 მანეთი ან 20 მანეთი. ჩვენ გვინდა, რომ მომხმარებელს დაუბრუნოთ ცვლილების სწორი ოდენობა. თავდაპირველად, ჩვენ არანაირი ცვლილება არ გვაქვს. ჩვენ უნდა ვუპასუხოთ, შეგვიძლია თუ არა წარმატებით დაუბრუნოთ თითოეულ მომხმარებელს ცვლილების სწორი ოდენობა, თუ არა.

მაგალითი

 bills = [5,5,5,10,20]
true

განმარტება:

ლიმონათის შეცვლა Leetcode Solution

დაწყებული სამი გარიგების დროს, ჩვენ არ უნდა შეიტანოთ რაიმე ცვლილება. სამი ტრანსაქციის შემდეგ გვაქვს 5 მანეთიანი სამი მონეტა. მეოთხე ტრანსაქციის დროს უნდა დავაბრუნოთ 5 მანეთი. მეოთხე ტრანზაქციის შემდეგ, ჩვენ გვაქვს 2 მანეთი 5 მანეთიდან და ერთი მონეტა 10 მანეთიდან. მეხუთე ტრანზაქციაში ჩვენ უნდა დავაბრუნოთ 15 მანეთი. ჩვენ შეგვიძლია დავუბრუნოთ ერთი ათი მანეთი და ერთი ხუთი მანეთი. რადგან ყველა ოპერაცია დასრულებულია, პასუხი სიმართლეა.

მიდგომა

ეს არის განხორციელების პრობლემა ხარბი ალგორითმის გამოყენებით. მას შემდეგ, რაც მასივში მოცემული მნიშვნელობები წარმოადგენს მომხმარებელთა რიგს, ამიტომ როდესაც მასივს გადავხედავთ, ჩვენ ასევე ვაწარმოებთ ოპერაციებს. თავდაპირველად, ჩვენ არანაირი ცვლილება არ გვაქვს, ამიტომ ხუთი, ათი და ოცი მანეთიანი მონეტების რაოდენობა ნულის ტოლია.

მოდით თითოეულ სცენარს სათითაოდ ვეძებთ:

  1. თუ მომხმარებელი გადაიხდის ხუთ მანეთს, მაშინ ჩვენ არ უნდა შევცვალოთ იგი და ხუთი მანეთის რაოდენობა ჩვენთან ერთით გაიზრდება.
  2. ვთქვათ, მომხმარებელი იხდის ათი მანეთი, მაშინ უნდა გვქონდეს მინიმუმ ერთი ხუთი მანეთი, რომ მას ცვლილება მივცეთ. თუ ამას ვერ მოვახერხებთ, ყალბი დავბრუნდებით, რადგან შეუძლებელია ყველას შეცვალოთ სწორი ოდენობა.
  3. თუ მომხმარებელი გადაიხდის ოცი მანეთიდან, მაშინ მას შეგვიძლია შევცვალოთ ორი განსხვავებული გზით:
    1. იმ შემთხვევაში, თუ ჩვენ გვაქვს ათი მანეთი და ხუთი მანეთი, მაშინ ჩვენ შეგვიძლია დავუბრუნოთ მას სულ თხუთმეტი მანეთი. თუ ვერ შევძელით, ჩვენ ვეძებთ მეორე მეთოდს.
    2. რადგან სულ თხუთმეტი მანეთი უნდა დავბრუნოთ, მას შეგვიძლია მივცეთ სამი მონეტა თითო ხუთი მანეთიდან. ამისთვის უნდა გვქონდეს მინიმუმ 3 მონეტა ხუთიანი მანეთიდან. თუ ამას ვერ მოვახერხებთ, ყალბი დავბრუნდებით, რადგან შეუძლებელია ყველას შეცვალოთ სწორი ოდენობა.

თუ ჩვენ ყველა მომხმარებელს მივაწოდეთ ცვლილების სწორი ოდენობა, ჩვენ უბრალოდ ვუბრუნდებით ჭეშმარიტებას.

კოდი

C ++ კოდი ლიმონათის შესაცვლელად Leetcode Solution

#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

ლიმონათის შეცვლის Leetcode Solution- ის ჯავას კოდი

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

ლიმონათის ცვლილების Leetcode ხსნარის სირთულის ანალიზი

დროის სირთულე

ზემოთ მოცემული კოდის სირთულეა O (n) რადგან ჩვენ მხოლოდ ერთხელ გადავხედავთ გადასახადების მასივს. აქ n არის გადასახადების მასივის სიგრძე.

კოსმოსური სირთულის

ზემოთ მოცემული კოდის სივრცის სირთულეა O (1) რადგან პასუხების შესანახად ვიყენებთ მხოლოდ ცვლადს.

ლიტერატურა