算法篇六贪心算法

贪心算法概念

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，

它所做出的仅是在某种意义上的局部最优解。用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的

目标，以尽可能快的求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。

利用贪心算法解决问题时需要解决以下两个问题：

（1）该问题是否适合贪心策略求解。

（2）如何选择贪心标准，以得到问题的最优/较优解。

贪心算法存在如下问题：

（1）不能保证解释最佳的。因为贪心算法总是从局部出发，并没有从整体考虑。

（2）贪心算法一般用来解决求最大或最小解。

（3）贪心算法只能确定某些问题的可行性范围。 ————————————————

LeetCode 402 题:

力扣

https://leetcode-cn.com/problems/remove-k-digits/


class Solution {
    public String removeKdigits(String num, int k) {
        if ("0".equals(num)) return "0";
        if (k == num.length()) return "0";
        Deque<Character> deque = new LinkedList<>();
        int n = num.length();
        for (int i = 0; i < n; i++) {
            // 如果栈里面的元素比当前大, 则删除栈里的元素
            while (!deque.isEmpty() && k != 0 && deque.peekLast() > num.charAt(i)) {
                deque.pollLast();
                k--;
            }
            deque.offerLast(num.charAt(i));
        }
        // 剩下的数直接从后面开始删(即从大的数开始删)
        while (k != 0) {
            deque.pollLast();
            k--;
        }
        // 合并数字
        String r = "";
        while (!deque.isEmpty()) {
            r += deque.pollFirst();
        }
        // 去除前导0
        while (r.charAt(0) == '0' && r.length() != 1) {
            r = r.substring(1);
        }
        return r;
    }
}

算法篇六 贪心算法

贪心算法概念

算法篇六贪心算法