算法训练营Day27

2023-12-30 14:56:54

#Java #贪心

开源学习资料

Feeling and experiences:

这周来到了贪心算法,简要概述:

贪心算法是一种在每个步骤中都采取最优解(即,在当前看来最好的解)的算法设计策略。它通常用于求解优化问题。这种方法不总是能得到全局最优解,但在很多情况下能产生接近最优的解决方案。

这里是一些贪心算法的关键特点和应用实例:

1. 局部最优选择:在每个决策点,算法选择当前情况下的最佳选项,而不考虑未来的结果。

2. 无回溯:一旦做出选择,算法就不会撤销或重新考虑这个决策。

3. 应用领域:贪心算法适用于任务调度、图算法(如最小生成树和最短路径问题)、压缩编码(如霍夫曼编码)等。

4. 效率和简单性:通常,贪心算法比其他更复杂的算法更快、更简单。

5. 局限性:不是所有问题都可以用贪心算法有效解决。在某些情况下,贪心选择可能阻止达到全局最优解。

6. 实例:一个典型的例子是找零问题,即用最少的硬币数量找零。在美国货币系统中,使用贪心策略(总是选择可能的最大面值硬币)可以得到最优解。

要有效地应用贪心算法,关键是正确识别问题是否适合使用这种策略,并理解它可能只提供近似解而不是最优解。
?

分发饼干:力扣题目链接

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值?g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j]?。如果 s[j]?>= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

如果没有想到贪心的思想,正常解答也很容易解出来:

class Solution {
    public int findContentChildren(int[] g, int[] s) {
    //贪心,先满足胃口最大的孩子
    //先排序
    Arrays.sort(g);
    Arrays.sort(s); //都是从小到大升序排列

    int endg = g.length -1;
    int ends = s.length -1;
    int count = 0;


    while(ends>=0 && endg>=0){
    if(s[ends] >= g[endg]){
    count++;
    ends--;
    endg--;
    }
    else{
    endg--;
    }
    }
    return count;
        }
}

官解用的是for循环,我认为while循环更容易理解

思路都是一样的,只要就是把这两个数组进行排序,这样我们从最后开始遍历比较,以我们的饼干数组为准。

从最大的满足度和饼干大小开始,逐一向下遍历。用两个指针endg和ends分别指向g数组和s数组的末尾元素(最大值)。
如果当前最大的饼干ends可以满足当前最大的满足度endg(即s[ends]?>=?g[endg]),则意味着这个孩子可以被满足。此时,将计数器count增加1,并将两个指针都向前移动一位,以检查下一个孩子和饼干。
如果当前饼干不能满足当前孩子(即s[ends]?<?g[endg]),则只将endg指针向前移动一位,检查下一个较小的满足度,因为当前饼干无论如何都无法满足当前孩子。

摆动序列:力扣题目链接

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如,?[1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3)?是正负交替出现的。

  • 相反,[1, 4, 7, 2, 5]?和?[1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。

给你一个整数数组 nums ,返回 nums 中作为 摆动序列 最长子序列的长度

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }

        int maxCount = 1;
        Integer prevDiff = null; // 使用Integer以便能存储null

        for (int i = 1; i < nums.length; i++) {
            int diff = nums[i] - nums[i - 1];
            if (diff != 0) {
                // 只在差值符号变化时增加maxCount
                if (prevDiff == null || (diff > 0 && prevDiff < 0) || (diff < 0 && prevDiff > 0)) {
                    maxCount++;
                    prevDiff = diff;
                }
            }
        }

        return maxCount;
    }
}

?最开始的一个想法是,把nums遍历计算,把得到的差放到另一个数组或者集合中,再用该数组或者集合进行遍历求解。

最大子序和:力扣题目链接

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

这道题利用前缀和来计算,非常简单:

class Solution {
    public int maxSubArray(int[] nums) {
        //初始化为数组的第一个元素
        int maxSum = nums[0];
        int sum = 0;
    for(int i = 0;i<nums.length;i++){
    sum += nums[i];
    sum = Math.max(sum,nums[i]);
    maxSum = Math.max(maxSum,sum);
    }
    return maxSum;
    }
}

?

力扣评论:

?走完这一生?如果我和你在一起会变得更好,那我们就在一起,否则我就丢下你。?我回顾我最光辉的时刻就是和不同人在一起,变得更好的最长连续时刻~~

Fighting!

文章来源:https://blog.csdn.net/momolinshaomo/article/details/135299570
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。