C#LeetCode刷题之#860-柠檬水找零(Lemonade Change)
问题
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/4036 访问。
在柠檬水摊上,每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。
每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。
注意,一开始你手头没有任何零钱。
如果你能给每位顾客正确找零,返回 true ,否则返回 false 。
输入:[5,5,5,10,20]
输出:true
解释:前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。由于所有客户都得到了正确的找零,所以我们输出 true。
输入:[5,5,10]
输出:true
输入:[10,10]
输出:false
输入:[5,5,10,10,20]
输出:false
解释:前 2 位顾客那里,我们按顺序收取 2 张 5 美元的钞票。对于接下来的 2 位顾客,我们收取一张 10 美元的钞票,然后返还 5 美元。对于最后一位顾客,我们无法退回 15 美元,因为我们现在只有两张 10 美元的钞票。由于不是每位顾客都得到了正确的找零,所以答案是 false。
提示:
- 0 <= bills.length <= 10000
- bills[i] 不是 5 就是 10 或是 20
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 don't have any change in hand at first.
Return true if and only if you can provide every customer with correct change.
Input: [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.
Input: [5,5,10]
Output: true
Input: [10,10]
Output: false
Input: [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't give change of $15 back because we only have two $10 bills.Since not every customer received correct change, the answer is false.
Note:
- 0 <= bills.length <= 10000
- bills[i] will be either 5, 10, or 20.
示例
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/4036 访问。
public class Program {
public static void Main(string[] args) {
var bills = new int[] { 5, 5, 5, 10, 20 };
var res = LemonadeChange(bills);
Console.WriteLine(res);
bills = new int[] { 5, 5, 10, 10, 20 };
res = LemonadeChange2(bills);
Console.WriteLine(res);
bills = new int[] { 5, 10 };
res = LemonadeChange3(bills);
Console.WriteLine(res);
Console.ReadKey();
}
public static bool LemonadeChange(int[] bills) {
//统计5美元和10美元的数量
var five = 0;
var ten = 0;
for(var i = 0; i < bills.Length; i++) {
if(bills[i] == 5) {
//5美元,则5美元+1
five++;
} else if(bills[i] == 10) {
//10美元,则10美元+1,找零5美元,5美元-1
ten++;
five--;
} else if(bills[i] == 20) {
//20美元时,尽量先找零10美元和5美元
//然后考虑找零3个5美元
if(ten > 0) {
ten--;
five--;
} else {
five -= 3;
}
}
//5美元或10美元小于0时,说明至少有1次找零是失败的
//直接返回 false
if(five < 0 || ten < 0) return false;
}
//最后返回 true
return true;
}
public static bool LemonadeChange2(int[] bills) {
//基本思路同 LemonadeChange,提供了一个不同的实现
var list = new List<int>();
for(var i = 0; i < bills.Length; i++) {
if(bills[i] == 5) {
list.Add(5);
} else if(bills[i] == 10) {
list.Add(10);
if(!list.Remove(5)) return false;
} else if(bills[i] == 20) {
if(list.Remove(10)) {
if(!list.Remove(5)) return false;
} else {
for(var j = 0; j < 3; j++) {
if(!list.Remove(5)) return false;
}
}
}
}
return true;
}
public static bool LemonadeChange3(int[] bills) {
//不建议的解法,仅提供思路
//基本思路同 LemonadeChange,提供了一个不同的实现
try {
var five = new Stack<int>();
var ten = new Stack<int>();
for(var i = 0; i < bills.Length; i++) {
if(bills[i] == 5) {
five.Push(5);//这个值是什么无所谓
} else if(bills[i] == 10) {
ten.Push(10);//这个值是什么无所谓
five.Pop();
} else if(bills[i] == 20) {
if(ten.Any()) {
ten.Pop();
five.Pop();
} else {
for(var j = 0; j < 3; j++) {
five.Pop();
}
}
}
}
return true;
} catch(Exception ex) {
return false;
}
}
}
以上给出3种算法实现,以下是这个案例的输出结果:
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/4036 访问。
True
False
True
分析:
显而易见,以上3种算法的时间复杂度均为: 。
最新文章
- 用Kotlin开发Android应用(III):扩展函数和默认值
- 【Excel】宏之初认识
- React(JSX语法)----动态UI
- Linux 环境变量配置
- GeoServer 常见问题总结
- 射手网字幕打包下载(73.16G)
- C++ 的template
- java按照集合中元素的属性进行排序示例代码
- getopt 分析命令行参数 -n -t 1
- Beforeunload打点丢失原因分析及解决方案
- 迭代 Iterate
- C# 获取当前应用程序的绝对路径支持asp.net
- mongodb迁移
- jquery(select)下拉框 选取选中的值
- C#使用Xamarin开发可移植移动应用终章(11.获取设备信息与常用组件,开源一个可开发模版.)
- android 实现倒影
- 前端页面展示MySQL数据并实现前后端互动
- Xilinx------BUFG,IBUFG,BUFGP,IBUFGDS等含义以及使用
- 可能比文档还详细--VueRouter完全指北
- IdentityServer4-EF动态配置Client和对Claims授权(二)