860-柠檬水找零（Lemonade Change）

秒速五厘米 2022-01-22 06:59 200阅读 0赞

**题目描述**  
**中文**

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
    顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
    每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
    注意，一开始你手头没有任何零钱。
    如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

**英文**

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.

**示例**

输入：[5,5,5,10,20]
    输出：true
    解释：
    前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
    第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
    第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
    由于所有客户都得到了正确的找零，所以我们输出 true。

**解题思路**

*  找零问题，第一反应贪婪算法，如果能拿十元的找就用十元的找，否则用五元。而经过分析，第一位顾客只能用五元，否则的话就找不开，第二位顾客最多用十元否则找不开。
 *  有了思路以后就要贴一下代码了。

class Solution {
        public static boolean findMoney(List<Integer> change, int money){			//找零的方法
    		if(money == 5){		//如果是五元，不用找零，直接放到钱柜chang
    			change.add(money);
    			return true;
    		}
            if(money == 10 && change.indexOf(5) != -1){			//如果是十元并且钱柜有五元，就删掉一个五元，并把十元添加到钱柜
            	change.add(money);
            	change.remove(change.indexOf(5));
            	return true;
            }
            if(money == 20){					//如果是20元就有两种情况
            	if(change.indexOf(5) != -1 && change.indexOf(10)!= -1){			//如果有五元和十元，就可以找开
            		change.add(money);
            		change.remove(change.indexOf(5));
            		change.remove(change.indexOf(10));
            		return true;
            	}
            	else{				//否则有三张五元，也可以召开
            		int five = 0;
            		int[] five_location = new int[3];
            		for(int i = 0;i < change.size() && five < 3;i++){
            			if(change.get(i) == 5){
            				five_location[five++] = i;
            			}
            		}
            		if(five == 3){
            			for(int i = 0;i<five_location.length;i++){
            				change.remove(five_location[i] - i);
            			}
            			change.add(money);
            			return true;
            		}
            		
            	}
            }
            return false;			//剩下的情况都为false
        }
        public static boolean lemonadeChange(int[] bills) {
            List<Integer> change = new ArrayList<Integer>();
            if(bills[0] != 5)		//如果第一张不是五元，直接false
                return false;
            if(bills.length > 2 && bills[1] > 10)		//如果第二张是20，直接false
                return false;
            for(int i = 0;i < bills.length;i++){
            	if(!findMoney(change, bills[i]))
            		return false;					//中间有任何一次找不开，都返回false
            }
            return true;
            
        }
    }

*  因为增加了一个List用来放零钱和判断，所以效率十分低下。所以是不是有一种方法优化。
 *  emmm,同为贪心为何你这么优秀，下面是一位别人的思路：整体思路差不多，但是只用了一个长度为三的数组来计数即可。

class Solution {
        public boolean lemonadeChange(int[] bills) {
            if(bills[0] != 5)
                return false;
            if(bills.length > 2 && bills[1] > 10)
                return false;
            int[] change = new int[3]; //用来标记5、10、20的张数
            for(int i = 0;i < bills.length;i++){
                switch(bills[i]){
                case 5:
                	change[0]++;
                	break;
                case 10:
                	if(--change[0] < 0)
                		return false;
                	change[1]++;
                	break;
                case 20:
                	if(change[0] <= 0)
                		return false;
                	else if(change[0] > 0 && change[1] > 0){
                		change[0]--;
                		change[1]--;
                	}
                	else if(change[0] >= 3){
    					change[0] -= 3;
    				}
                    else {
    					return false;
    				}
                	change[2]++;
                	break;
                }
            }
            return true;
        }
    }