LeetCode刷题之贪心算法

柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

题解：

class Solution {
    /**
     * 思路：只管5、10元够不够找零，20元不用管，因为20元不能找
     * 那么记录5、10元的张数，如果是5，则直接存储,如果是10，则5元-1张，10元+1张
     * 如果是20元，那么先找5、10元各减一张，如果不能，则5元减3张，如果还不行，则返回false
     */
    public boolean lemonadeChange(int[] bills) {
        int fiveNum = 0, tenNum = 0;
        for (int i=0;i=1) {
                        fiveNum--;
                        tenNum++;
                    } else {
                        return false;
                    }
                    break;
                case 20:
                    if (fiveNum>=1 && tenNum>=1) {
                        //5、10元各减一张
                        fiveNum--;
                        tenNum--;
                    } else if (fiveNum >=3) {
                        fiveNum -= 3;
                    } else {
                        return false;
                    }
                    break;
            }
        }
        return true;
    }
}

去除重复字母

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

题解：

class Solution {
    /**
     * 解题思路：
     * 1.第一个条件：去重字母
     * 2.第二个条件：保证字典序从小到大
     * 3.第三个条件：保证字母存在至少一个
     * @param s
     * @return
     */
    public String removeDuplicateLetters(String s) {
        //第三个条件：保证字母存在至少一个
        //做法：给每一种字母维护一个计数器，先遍历获取其数量，如果数量为1，则在第二个条件中不要弹出栈，否则可以弹出栈
        int[] charCount = new int[256];
        for (int i=0;i stk = new Stack<>();
        boolean[] inStack = new boolean[256]; //用于存储这个字符是否已经记录过
        // 第一个条件：去重字母
        for(char c : s.toCharArray()) {
            // 每遍历过一个字符，都将对应的计数减一
            charCount[c]--;

            if (inStack[c]) {
                continue;
            }

            //第二个条件：保证字典序从小到大，在插入字母之前，判断与前一个字母的字典序，
            // 如果比前一个小，则循环将字符弹出栈顶，清除在栈中的记录
            while(!stk.empty() && stk.peek() > c) {
                if (charCount[stk.peek()] == 0) {
                    break;
                }
                inStack[stk.pop()] = false;
            }
            stk.push(c);
            inStack[c] = true;
        }
        StringBuilder sb = new StringBuilder();
        while (!stk.empty()) {
            sb.append(stk.pop());
        }
        return sb.reverse().toString();
    }
}