At a lemonade stand, each lemonade costs $5
. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5
, $10
, or $20
bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5
.
Note that you do not have any change in hand at first.
Given an integer array bills
where bills[i]
is the bill the ith
customer pays, return true
if you can provide every customer with the correct change, or false
otherwise.
Example 1:
Input: bills = [5,5,5,10,20] Output: true Explanation: From the first 3 customers, we collect three $5 bills in order. From the fourth customer, we collect a $10 bill and give back a $5. From the fifth customer, we give a $10 bill and a $5 bill. Since all customers got correct change, we output true.
Example 2:
Input: bills = [5,5,10,10,20] Output: false Explanation: From the first two customers in order, we collect two $5 bills. For the next two customers in order, we collect a $10 bill and give back a $5 bill. For the last customer, we can not give the change of $15 back because we only have two $10 bills. Since not every customer received the correct change, the answer is false.
Constraints:
1 <= bills.length <= 105
bills[i]
is either 5
, 10
, or 20
.program main
implicit none
integer, parameter :: n = 5
integer, dimension(n) :: bills
logical :: result
bills = [5, 5, 5, 10, 20]
result = lemonade(bills)
write (*, '(L1)') result
bills = [5, 5, 10, 10, 20]
result = lemonade(bills)
write (*, '(L1)') result
contains
function lemonade(bills) result(result)
implicit none
integer, intent(in) :: bills(:)
logical :: result
integer :: i, j, k, l, m, n, o
integer :: total
result = .true.
! Initialize variables
total = 0
i = 1
j = 1
k = 1
l = 1
m = 1
n = 1
o = 1
! Loop through the bills
do while (i <= ubound(bills, 1))
select case (bills(i))
case (5)
total = total + 5
i = i + 1
case (10)
if (total >= 5) then
total = total - 5
i = i + 1
else
result = .false.
exit
end if
case (20)
if (total >= 10) then
total = total - 10
i = i + 1
else
result = .false.
exit
end if
end select
end do
! Check if there is enough money for the change
if (total /= 0) then
result = .false.
end if
end function lemonade
end program main
T F
module lemonade_stand
implicit none
contains
function solve(bills) result(success)
integer, intent(in) :: bills(:)
logical :: success
integer :: i, bill, change
! Initialize variables
success = .true.
i = 1
bill = 0
change = 0
! Process each bill
do while (i <= size(bills))
! Check if the bill is valid
if (bills(i) /= 5 .and. bills(i) /= 10 .and. bills(i) /= 20) then
success = .false.
exit
end if
! Update the bill and change
bill = bills(i)
change = bill - 5
! Check if we have enough change
if (change < 0) then
success = .false.
exit
end if
! Update the change
change = change - 5
! Increment the index
i = i + 1
end do
end function solve
end module
program test
use lemonade_stand
implicit none
! Test case 1:
print *, solve([5, 5, 5, 10, 20])
! Test case 2:
print *, solve([5, 5, 10, 10, 20])
! Test case 3:
print *, solve([5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
temp.f95:55:132: 55 | print *, solve([5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, | 1 Error: Line truncated at (1) [-Werror=line-truncation] temp.f95:55:132: 55 | print *, solve([5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, | 1 Error: Syntax error in array constructor at (1) f951: Error: Unexpected end of file in βtemp.f95β f951: some warnings being treated as errors
class MyCircularQueue:
def __init__(self, k: int):
self.data = [0] * k
self.head = 0
self.tail = -1
self.size = 0
self.capacity = k
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
self.tail = (self.tail + 1) % self.capacity
self.data[self.tail] = value
self.size += 1
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
self.head = (self.head + 1) % self.capacity
self.size -= 1
return True
def Front(self) -> int:
if self.isEmpty():
return -1
return self.data[self.head]
def Rear(self) -> int:
if self.isEmpty():
return -1
return self.data[self.tail]
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.capacity
The circular queue is implemented using an array with fixed capacity. The operations are performed based on FIFO principle, and the last position is connected back to the first position to make a circle. We keep a head and tail pointer, as well as the current size of the queue. Whenever an element is enqueued, we move the tail pointer forward (circulating back to the start of the array when necessary) and increase the size. When an element is dequeued, we move the head pointer forward and decrease the size. We can check if the queue is empty by comparing the size to 0 and check if the queue is full by comparing the size to the capacity. All operations have O(1) time complexity.
class MyCircularQueue {
public:
MyCircularQueue(int k) {
data.resize(k);
head = 0;
tail = -1;
size = 0;
capacity = k;
}
bool enQueue(int value) {
if (isFull()) {
return false;
}
tail = (tail + 1) % capacity;
data[tail] = value;
size++;
return true;
}
bool deQueue() {
if (isEmpty()) {
return false;
}
head = (head + 1) % capacity;
size--;
return true;
}
int Front() {
if (isEmpty()) {
return -1;
}
return data[head];
}
int Rear() {
if (isEmpty()) {
return -1;
}
return data[tail];
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == capacity;
}
private:
vector<int> data;
int head, tail, size, capacity;
};
The circular queue is implemented using an array with fixed capacity. The operations are performed based on FIFO principle, and the last position is connected back to the first position to make a circle. We keep a head and tail pointer, as well as the current size of the queue. Whenever an element is enqueued, we move the tail pointer forward (circulating back to the start of the array when necessary) and increase the size. When an element is dequeued, we move the head pointer forward and decrease the size. We can check if the queue is empty by comparing the size to 0 and check if the queue is full by comparing the size to the capacity. All operations have O(1) time complexity.