贪心算法入门（三）

相关文章

贪心算法入门（一）-CSDN博客

贪心算法入门（二）-CSDN博客

1.什么是贪心算法？

        贪心算法是一种解决问题的策略，它将复杂的问题分解为若干个步骤，并在每一步都选择当前最优的解决方案，最终希望能得到全局最优解。这种策略的核心在于“最优”二字，意味着我们追求的是以最少的时间和精力，快速获得正确的结果。

        然而，“希望得到全局最优解”就表示贪心算法并不意味着一定能得到全局最优解。实际上，并不是所有问题都可以通过贪心策略解决。为了确保贪心策略的有效性，需要对其进行严格的证明。而且，不同的问题往往需要采用不同的贪心策略。

        如果你觉得这一点仍然比较抽象，接下来我将通过5道具体的例题来详细说明贪心算法的应用及其背后的思路。

2. 按身高排序

2418. 按身高排序 - 力扣（LeetCode）

这道题要求很简单，根据身高排序，但是输出的是名字。对身高排序很简单，可以直接用sort，但是真正需要排序的数组是name姓名数组。但是比较方法又是根据身高比较的，所以想一个办法绑定这两个数组。可以使用一个中间数组index下标数组，里面存放每个下标，然后对index数组排序，比较的规则可以自己写入用身高大小排序。排序之后的index数组就是按照身高下标来排序的了，比如index[0]的值为2就表示身高最高的人的下标为2，那么应该先输出name[2]的值。

2.1 代码实现

class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        Integer[] index = new Integer[n];
        for(int i = 0; i < n; i++) index[i] = i;
        Arrays.sort(index, (a, b) -> heights[b] - heights[a]);
        String[] ret = new String[n];
        for(int i = 0; i < n; i++) ret[i] = names[index[i]];
        return ret;
    }
}

3. 优势洗牌

870. 优势洗牌 - 力扣（LeetCode）

题目解析：可以任意重组nums1的顺序，并且该顺序可以让nums1和nums2依次比较大小时，nums1优胜的次数更多。

该题的贪心策略跟田忌赛马很像，可以对nums1和nums2数组都按从小到大排序。然后再依次比较如果第一个位置nums1就小于nums2，相当于两个数组最小的值比较nums1都输了，此时把这个最小的数去匹配nums2最大的数，然后nums1再用下一个数继续比较nums2的数。依次类推。这样做的好处就是知道nums1最小的数已经对于nums2中的任何数字都取得不了优胜了，那么就不要选择匹配当前nums2最小的数，选择匹配最大的数，这样就可以留着nums1最大的数去匹配nums2前面的数，增大优胜的概率。

上图为整个逻辑流程图，依次扫描nums1数组的每个数，每次扫描都可以确定扫描的数匹配nums2的哪一个数。匹配规则为当前nums1扫描的数小于等于nums2[left]的数就让其匹配nums2[right]的数，否则匹配nums2[left]的数。

还需要注意的一点，这样的做法并不是最终答案，因为我们只能改变nums1的顺序不能改变nums2的，要根据原有的nums2的顺序，去填入nums1的值。所以该题依然需要一个中间变量下标数组去绑定两个数组下标的对应关系。

3.1 代码实现

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
       int n = nums1.length;
       Integer[] index = new Integer[n];
       for(int i = 0; i < n; i++) index[i] = i;
       Arrays.sort(index, (i, j) -> nums2[i] - nums2[j]);
       Arrays.sort(nums1);
       int[] ret = new int[n];
       int right = n - 1, left = 0;
       for(int x : nums1){
         if(x  > nums2[index[left]]) ret[index[left++]] = x; // index[left]表示当前nums2最小值的下标
         else ret[index[right--]] = x; // index[right]表示当前nums2最大值的下标
       }
       return ret;
    }
}

4. 最长回文串

409. 最长回文串 - 力扣（LeetCode）

这道题要构造回文串，构成回文串有两种可能，一种是回文串中每个字母都是偶数，这样可以对称的分为两边构成回文，还有一种是偶数对称之后，中间单夹一个任意字母。

故这道题的贪心思路很简单，首先就需要统计字符串中每个字母的个数，这里可以有一个优化的小tip就是不适用map表来统计，而是使用数组来代替map表，因为大小字母的asc码值最大也不超过126，所以新建一个大小为126的int数组就可以将所有字母的个数统计完整。

继续优化：可以在循环字符串时一边统计字母个数时一边更新长度，因为只要统计到当前字母的个数等于2了，就可以把它往回文串里面加，让ret长度加2，然后再让hash表中该字母的个数重置为0。现在还有一个问题，当循环完成之后就是最终答案了吗？其实不是，因为循环里面统计长度的规则只考虑了偶数回文串的情况，这时需要判断ret的值是否小于字符串s的长度，如果小于说明还可以有单的字母加进去，这个字母可以是字符串中剩下字母中的任何一个。那么此时更新ret加1，否则直接返回ret。

4.1 代码实现

class Solution {
    public int longestPalindrome(String s) {
        int[] hash = new int[126];
        char[] ss = s.toCharArray();
        int ret = 0;
        for(char ch : ss){
            hash[ch] += 1;
            if(hash[ch] == 2){
                ret += 2;
                hash[ch] = 0;
            }
        }
        return ret < s.length() ? ret + 1 : ret;
    }
}

5. 增减字符串

942. 增减字符串匹配 - 力扣，然后（LeetCode）

 题目解析：输出的int数组中每个位置的值都是由0-n组成的，n为s字符串的长度。每个位置的值要根据s字符串的字母确定，例如示例1中，s字符串的长度为4，所以最终返回的int数组长度为n + 1。s字符串中第一个字母是I表示，int数组要进行上升，比如0到4就是一个上升。第二个字母是D表示要下降，4到1就是下降。以此类推。

贪心策略，遇到字母是I上升趋势的时候，确定当前int数组的数字为0-n中剩下可以挑选的数字中的最小的一个，因为选择最小的一个下一个位置的数字就只用受下一个字母的条件限制，而不用管上一个字母的限制，因为此时的任何数字都会比最小的数字大。拿示例1举例，第一个字母是I，如果此时int数组不选择0选择其他数字比如1。第二个字母是D，选择的数字不能是0和1,1被选过了，也不能选0因为0比1小，不满足第一个字母的I。但是如果第一次选择0，第二次选择数字的时候就不用考虑前一个字母的条件，因为剩下的数字1-n都比0大，所以只用考虑第二个字母D下降，同理此时应该选择最大的数字n,因为下一个选择的数字都可以从剩下的数中任意挑选，并且肯定满足条件。

5.1 代码实现

class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int[] ret = new int[n + 1];
        int left = 0, right = n;
        for(int i = 0; i < n; i++){
            if(s.charAt(i) == 'I') ret[i] = left++;
            else ret[i] = right--;
        }
        ret[n] = left;
        return ret;
    }
}

6. 分发饼干

455. 分发饼干 - 力扣（LeetCode）

 这道题跟优势洗牌思路一样，就是对两个数组进行排序，然后依次比较，如果不满足当前孩子的胃口就让饼干数组往后一位继续比较知道满足为止。贪心的策略就是尽量用小的饼干尺寸去满足孩子胃口。

6.1 代码实现

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g); Arrays.sort(s);
        int ret = 0;
        for(int i = 0, j = 0; i < g.length && j < s.length; j++){
            if(s[j] >= g[i]){
                i++; ret++;
            }
        }
        return ret;
    }
}