贪心算法=>我的眼前,就是整个世界

贪心基础(只看眼前)

贪心算法,是指在对问题求解时,总是做出再当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是某种意义上的局部最优解。

贪心算法没有固定算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。

  • 贪心算法的基本思路
  1. 建立数学模型来描述问题。

  2. 把求解的问题分成若干个子问题。

  3. 对每一子问题求解,得到子问题的局部最优解。

  4. 把子问题的解局部最优解合成原来解问题的一个解。

  • 贪心算法的实现框架
    从问题的某一初始解出发:

while (能朝给定总目标前进一步)

{ 利用可行的决策,求出可行解的一个解元素;}

由所有解元素组合成问题的一个可行解。

贪心习题集合

其他「贪心」相关内容

链接: link

题一 019. 最多删除一个字符得到回文

贪心算法=>我的眼前,就是整个世界_第1张图片

个人的暴力求解

class Solution {
    public boolean validPalindrome(String s) {
        if(judge(s))return true;

        StringBuilder res = new StringBuilder();
        int end = s.length();
        while(end >= 0){
            for (int i = 0; i < s.length(); i++) {
                if(i!=end){
                    res.append(s.charAt(i));
                }          
            }
            if(judge(res.toString()))return true;
            res.delete(0, res.length());
        }
        return false;
    }

    boolean judge(String s){
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)!=s.charAt(s.length()-i-1)){
                return false;
            }
        }
        return true;
    }
}
class Solution {
    public boolean validPalindrome(String s) {
        if(judge(s, 0, s.length()))return true;

        StringBuilder res = new StringBuilder();
        int end = s.length()-1;
        while(end >= 0){

            for (int i = 0; i < s.length(); i++) {
                if(i!=end){
                    res.append(s.charAt(i));
                }          
            }
            end--;
            if(judge(res.toString(), 0, s.length()-1 ))return true;
            res.delete(0, res.length());
        }
        return false;
    }

    public boolean judge(String s, int low, int high) {
        for (int i = low, j = high-1; i < j; ++i, --j) {
            char c1 = s.charAt(i), c2 = s.charAt(j);
            if (c1 != c2) {
                return false;
            }
        }
        return true;
    }
}

贪心算法

贪心算法=>我的眼前,就是整个世界_第2张图片
贪心算法=>我的眼前,就是整个世界_第3张图片

class Solution {
    public boolean validPalindrome(String s) {
        int low = 0, high = s.length() - 1;
        while (low < high) {
            char c1 = s.charAt(low), c2 = s.charAt(high);
            if (c1 == c2) {
                ++low;
                --high;
            } else {
                return validPalindrome(s, low, high - 1) || validPalindrome(s, low + 1, high);
            }
        }
        return true;
    }

    public boolean validPalindrome(String s, int low, int high) {
        for (int i = low, j = high; i < j; ++i, --j) {
            char c1 = s.charAt(i), c2 = s.charAt(j);
            if (c1 != c2) {
                return false;
            }
        }
        return true;
    }
}

你可能感兴趣的