算法题四-贪心算法类型

可以直接点击去看题目

已知一个水儿是5元，而且没有零钱；

可得当第一个客户是非5元那么返回false

然后 20元和10元需要找零

10元只要找5元

20元需要找一个5 一个10 或者3个5

贪心算法体现在这里 优先使用1个5一个10的找零方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static boolean lemonadeChange(int[] bills) {

     int count5=0;
     //第一张必须是5
     int count10=0;
     if(bills[0]/5!=1)
         return false;
     else
         count5++;


     for(int i=1;i<bills.length;i++)
     {
                 if(bills[i]==5) {  //5元

                     count5++;
                 }else if(bills[i]==10) //10元
                 {
                     if (count5==0) return false;
                     count5--;
                     count10++;

                 }else if(bills[i]==20){ //20元
                     if (count5>0&&count10>0) {//贪心算法 优先使用10+5的方式找零
                         count5--;
                         count10--;
                     }  else if (3<=count5) {

                         count5 = count5 - 3;
                     } else {
                         return false;
                     }
                 }

     }

     return true;

 }

上代码

直接使用foreach将会减少百分之5的内存损耗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int count5=0;
    //第一张必须是5
    int count10=0;

    for(int bill : bills)
    {
        if(bill==5) {  //5元

            count5++;
        }else if(bill==10) //10元
        {
            if (count5==0) return false;
            count5--;
            count10++;

        }else if(bill==20){ //20元
            if (count5>0&&count10>0) {//贪心算法 优先使用10+5的方式找零
                count5--;
                count10--;
            }  else if (3<=count5) {

                count5 = count5 - 3;
            } else {
                return false;
            }
        }

    }

    return true;

别的题目很难体现所谓贪心

这个就很经典了，

当你先去使用3张5元的找零时，效益不是最大化！