Lemonade Change Leetcode Solution


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα Atlassian
Άπληστος LeetCode

Αυτή η ανάρτηση βρίσκεται στο Lemonade Change Leetcode Solution

Δήλωση προβλήματος

Στο πρόβλημα "Lemonade Change" υπάρχει ένα ουρά πελατών. Θέλουν να αγοράσουν λεμονάδα από εμάς που κοστίζει 5 ρουπίες. Οι πελάτες μπορούν να μας δώσουν 5 ρουπίες, 10 ρουπίες ή 20 ρουπίες. Θέλουμε να επιστρέψουμε το σωστό ποσό αλλαγής στους πελάτες. Αρχικά, δεν έχουμε καμία αλλαγή. Πρέπει να απαντήσουμε εάν μπορούμε να επιστρέψουμε με επιτυχία το σωστό ποσό αλλαγής σε κάθε πελάτη ή όχι.

Παράδειγμα

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

Επεξήγηση:

Lemonade Change Leetcode Solution

Στις τρεις πρώτες συναλλαγές, δεν χρειάζεται να κάνουμε καμία αλλαγή. Μετά από τρεις συναλλαγές έχουμε τρία νομίσματα των 5 ρουπιών. Κατά την τέταρτη συναλλαγή, πρέπει να επιστρέψουμε 5 ρουπίες. Έτσι, μετά την τέταρτη συναλλαγή, έχουμε 2 νομίσματα των 5 ρουπιών και ένα νόμισμα των 10 ρουπιών. Στην πέμπτη συναλλαγή, πρέπει να επιστρέψουμε 15 ρουπίες. Μπορούμε να επιστρέψουμε ένα νόμισμα δέκα ρουπιών και ένα νόμισμα πέντε ρουπιών. Καθώς όλες οι συναλλαγές έχουν ολοκληρωθεί, η απάντηση είναι αλήθεια.

Προσέγγιση

Αυτό είναι ένα πρόβλημα εφαρμογής χρησιμοποιώντας έναν άπληστο αλγόριθμο. Καθώς οι τιμές που δίνονται στον πίνακα αντιπροσωπεύουν μια ουρά πελατών, οπότε όταν θα διασχίσουμε τον πίνακα ταυτόχρονα θα κάνουμε και συναλλαγές. Αρχικά, δεν έχουμε καμία αλλαγή, οπότε ο αριθμός των νομισμάτων των πέντε, δέκα και είκοσι ρουπιών είναι μηδέν.

Ας αναζητήσουμε ένα από τα σενάρια ένα προς ένα:

  1. Εάν ο πελάτης πληρώσει πέντε ρουπίες, τότε δεν χρειάζεται να του δώσουμε καμία αλλαγή και ο αριθμός των κερμάτων πέντε ρουπιών μαζί μας θα αυξηθεί κατά ένα.
  2. Ας υποθέσουμε ότι ο πελάτης πληρώνει δέκα ρουπίες, τότε πρέπει να έχουμε τουλάχιστον ένα κέρμα πέντε ρουπιών για να του δώσουμε την αλλαγή. Εάν δεν το κάνουμε αυτό, θα επιστρέψουμε ψευδείς καθώς δεν είναι δυνατόν να δώσουμε τη σωστή αλλαγή σε όλους.
  3. Εάν ο πελάτης πληρώνει είκοσι ρουπίες τότε μπορούμε να του δώσουμε αλλαγή με δύο διαφορετικούς τρόπους:
    1. Σε περίπτωση που έχουμε κέρμα δέκα ρουπιών και κέρμα πέντε ρουπιών τότε μπορούμε να του επιστρέψουμε συνολικά δεκαπέντε ρουπίες. Εάν αποτύχουμε τότε θα αναζητήσουμε τη δεύτερη μέθοδο.
    2. Καθώς πρέπει να επιστρέψουμε συνολικά δεκαπέντε ρουπίες, μπορούμε να του δώσουμε τρία νομίσματα των πέντε ρουπιών το καθένα. Για αυτό, πρέπει να έχουμε τουλάχιστον 3 νομίσματα πενήντα ρουπιών. Εάν δεν το κάνουμε αυτό, θα επιστρέψουμε ψευδείς καθώς δεν είναι δυνατόν να δώσουμε τη σωστή αλλαγή σε όλους.

Εάν παρέχουμε το σωστό ποσό αλλαγής σε όλους τους πελάτες, τότε θα επιστρέψουμε αληθινά.

Κώδικας

Κωδικός C ++ για Lemonade Change 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

Κωδικός Java για Lemonade Αλλαγή Λύσης κωδικού Leetcode

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 Solution

Χρόνος πολυπλοκότητας

Η χρονική πολυπλοκότητα του παραπάνω κώδικα είναι O (n) γιατί διασχίζουμε τη σειρά λογαριασμών μόνο μία φορά. Εδώ είναι το μήκος του πίνακα λογαριασμών.

Διαστημικότητα

Η πολυπλοκότητα του παραπάνω κώδικα είναι Ο (1) γιατί χρησιμοποιούμε μόνο μια μεταβλητή για την αποθήκευση απαντήσεων.

αναφορές