LeetCode30刷-贪心算法柠檬水找零

贪心算法-柠檬水找零

题目

题目要求如下图

思想

思路：本题采用贪心的思想，主要是将每一步都采取最优解来处理，本题分为三种情况：---------------------------------------------------------------------------------------①用户给你5块，此时你不用找-------------------------------------------------------------②用户给你10块，此时你只能找5块-------------------------------------------------------③用户给你20，此时你可以找3个5块，或者一个10块，一张5块，因为贪心的思想，你应该找一个10块和一个5块，这样你可以少找一个5块，因为5块在本题中用处很大

代码

package Leetcode;

public class 贪心_柠檬水找零 {
    public static void main(String[] args) {
        int[] arr = new int[]{5,5,10};
        System.out.println(change(arr));
    }
    public static boolean change(int[] arr) {
        int five = 0;
        int ten = 0;
        for (int i : arr) {
            if (i == 5) {
                five++;
            } else if (i == 10) {
                if (five == 0) {
                    return false;
                } else {
                    five--;
                    ten++;
                }
            } else if (i == 20) {
                if (five != 0 && ten != 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five = five - 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

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

结尾

如果对文章内容有异议，欢迎在评论区发言，共同学习