鄂尔多斯市建设网站,wordpress修改成中文,济南商城网站建设,建筑英才网首页#Java #贪心
开源学习资料
Feeling and experiences#xff1a;
这周来到了贪心算法#xff0c;简要概述#xff1a;
贪心算法是一种在每个步骤中都采取最优解#xff08;即#xff0c;在当前看来最好的解#xff09;的算法设计策略。它通常用于求解优化问题。这种方…#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(ends0 endg0){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以便能存储nullfor (int i 1; i nums.length; i) {int diff nums[i] - nums[i - 1];if (diff ! 0) {// 只在差值符号变化时增加maxCountif (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;inums.length;i){sum nums[i];sum Math.max(sum,nums[i]);maxSum Math.max(maxSum,sum);}return maxSum;}
} 力扣评论 走完这一生 如果我和你在一起会变得更好那我们就在一起否则我就丢下你。 我回顾我最光辉的时刻就是和不同人在一起变得更好的最长连续时刻~~
Fighting
