贪心算法二

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：了解什么是贪心算法，并且掌握贪心算法。

> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!

> 专栏选自：贪心算法_დ旧言~的博客-CSDN博客

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

一、算法讲解

贪心算法的定义：

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

解题的一般步骤是：

1. 建立数学模型来描述问题；
2. 把求解的问题分成若干个子问题；
3. 对每一子问题求解，得到子问题的局部最优解；
4. 把子问题的局部最优解合成原来问题的一个解。

如果大家比较了解动态规划，就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。

动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。

二、算法习题

2.1、第一题

题目链接：409. 最长回文串 - 力扣（LeetCode）

题目描述：

算法思路：⽤尽可能多的字符去构造回⽂串

1. 如果字符出现偶数个，那么全部都可以⽤来构造回⽂串；
2. 如果字符出现奇数个，减去⼀个之后，剩下的字符能够全部⽤来构造回⽂串；
3. 最后再判断⼀下，如果有字符出现奇数个，就把它单独拿出来放在中间。 

代码呈现：

class Solution {
public:
    int longestPalindrome(string s) 
    {
        // 1. 计数 - ⽤数组模拟哈希表
        int hash[127] = {0};
        for (char ch : s)
            hash[ch]++;
        // 2. 统计结果
        int ret = 0;
        for (int x : hash) {
            ret += x / 2 * 2;
        }
        return ret < s.size() ? ret + 1 : ret;
    }
};

2.2、第二题

题目链接：942. 增减字符串匹配 - 力扣（LeetCode）

题目描述：

算法思路： 

• 当遇到 'I' 的时候，为了让下⼀个上升的数可选择的「范围更多」，当前选择「最⼩」的那个数；
• 当遇到 'D' 的时候，为了让下⼀个下降的数可选择的「范围更多」，选择当前「最⼤」的那个数。

代码呈现：

class Solution {
public:
    vector<int> diStringMatch(string s) 
    {
        int left = 0, right = s.size(); // ⽤ left，right 标记最⼩值和最⼤值
        vector<int> ret;
        for (auto ch : s) {
            if (ch == 'I')
                ret.push_back(left++);
            else
                ret.push_back(right--);
        }
        ret.push_back(left); // 把最后⼀个数放进去
        return ret;
    }
};

2.3、第三题

题目链接：455. 分发饼干 - 力扣（LeetCode）

题目描述：

算法思路： 

先将两个数组排序。针对胃⼝较⼩的孩⼦，从⼩到⼤挑选饼⼲：

1. 如果当前饼⼲能满⾜，直接喂（最⼩的饼⼲都能满⾜，不要浪费⼤饼⼲）；
2. 如果当前饼⼲不能满⾜，放弃这个饼⼲，去检测下⼀个饼⼲（这个饼⼲连最⼩胃⼝的孩⼦都⽆法满⾜，更别提那些胃⼝⼤的孩⼦了）。

代码呈现：

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // 先排序
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        // 利⽤双指针找答案
        int ret = 0, n = s.size();
        for (int i = 0, j = 0; i < g.size() && j < n; i++, j++) {
            while (j < n && s[j] < g[i])
                j++; // 找饼⼲
            if (j < n)
                ret++;
        }
        return ret;
    }
};

2.4、第四题

题目链接：553. 最优除法 - 力扣（LeetCode）

题目描述：

算法思路： 

• 在最终的结果中，前两个数的位置是⽆法改变的。
• 因为每⼀个数的都是⼤于等于 2 的，为了让结果更⼤，我们应该尽可能的把剩下的数全都放在「分⼦」上。

代码呈现：

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        int n = nums.size();
        // 先处理两个边界情况
        if (n == 1) {
            return to_string(nums[0]);
        }
        if (n == 2) {
            return to_string(nums[0]) + "/" + to_string(nums[1]);
        }
        string ret = to_string(nums[0]) + "/(" + to_string(nums[1]);
        for (int i = 2; i < n; i++) {
            ret += "/" + to_string(nums[i]);
        }
        ret += ")";
        return ret;
    }
};

2.4、第五题

题目链接：45. 跳跃游戏 II - 力扣（LeetCode）

题目描述：

算法思路： 

• ⽤类似层序遍历的过程，将第 i 次跳跃的「起始位置」和「结束位置」找出来，⽤这次跳跃的情况，更新出下⼀次跳跃的「起始位置」和「终⽌位置」。
• 这样「循环往复」，就能更新出到达 n - 1 位置的最⼩跳跃步数。

代码呈现：

class Solution {
public:
    int jump(vector<int>& nums) 
    {
        int left = 0, right = 0, maxPos = 0, ret = 0, n = nums.size();
        while (left <= right) // 保险的写法，以防跳不到 n - 1 的位置
        {
            if (maxPos >= n - 1) // 先判断⼀下是否已经能跳到最后⼀个位置
            {
                return ret;
            }
            // 遍历当成层，更新下⼀层的最右端点
            for (int i = left; i <= right; i++) {
                maxPos = max(maxPos, nums[i] + i);
            }
            left = right + 1;
            right = maxPos;
            ret++;
        }
        return -1; // 跳不到的情况
    }
};

2.6、第六题

题目链接：55. 跳跃游戏 - 力扣（LeetCode）

题目描述：

算法思路：

和 跳跃游戏II ⼀样，仅需修改⼀下返回值即可。

代码呈现：

class Solution {
public:
    bool canJump(vector<int>& nums) 
    {
        int left = 0, right = 0, maxPos = 0, n = nums.size();
        while (left <= right) 
        {
            if (maxPos >= n - 1) {
                return true;
            }
            for (int i = left; i <= right; i++) {
                maxPos = max(maxPos, nums[i] + i);
            }
            left = right + 1;
            right = maxPos;
        }
        return false;
    }
};

三、结束语 

今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。