让人做网站需要注意什,仓库管理 erp,电子商务网站软件建设的核心是,外贸公司网站制作价格目录 一、贪心
二、题目与题解
题目一#xff1a;455.分发饼干
题目链接
题解#xff1a;排序双指针贪心
题目二#xff1a;376. 摆动序列
题目链接
题解#xff1a;贪心
题目三#xff1a;53. 最大子序和
题目链接
题解1#xff1a;暴力#xff08;失败455.分发饼干
题目链接
题解排序双指针贪心
题目二376. 摆动序列
题目链接
题解贪心
题目三53. 最大子序和
题目链接
题解1暴力失败
题解2贪心
三、小结 一、贪心
个人感觉贪心是一个对初学者不太友好的章节这一类型的题没有固定的做法更感觉像是凭借做题经验和不断的积累以及个人的思考得来。贪心算法的核心思想是在每一步都采取当前状态下最优的选择而不考虑未来可能产生的影响。虽然贪心算法不能保证总是得到最优解但在很多情况下它可以获得很好的结果。
由于贪心更侧重于对于不同的题的变通这里直接开始今天的题从题中去感受贪心的思想。
二、题目与题解
题目一455.分发饼干
题目链接
455. 分发饼干 - 力扣LeetCode 假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。 对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子并输出这个最大数值。 示例 1: 输入: g [1,2,3], s [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干3个孩子的胃口值分别是1,2,3。
虽然你有两块小饼干由于他们的尺寸都是1你只能让胃口值是1的孩子满足。
所以你应该输出1。示例 2: 输入: g [1,2], s [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.提示 1 g.length 3 * 1040 s.length 3 * 1041 g[i], s[j] 231 - 1 题解排序双指针贪心
这道题相对来说还是比较简单的。
首先就是得先对两个数组排序--为什么要排序呢因为题目要求我们尽可能满足多的孩子那么就肯定是小饼干配胃口小的小孩大饼干配胃口大的小孩排序之后我们就可以通过循环遍历来实现这个问题。
思路一尽可能先配给胃口小的孩子小的饼干
采用双指针i,j分别从两个数组起始位置开始遍历如果满足饼干大小大于胃口两个指针同时后移如果饼干大小小于胃口就只将指向饼干的j指针后移实现从小到大为小孩配饼干。 思路二尽可能先配给胃口大的孩子大的饼干其实和思路一差不多只是顺序不同
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {int ans 0;sort(g.begin(), g.end()); //先排序sort(s.begin(), s.end());int j s.size() - 1; //遍历饼干的指针j for (int i g.size() - 1; i 0; i--) { //遍历胃口的指针i从大到小遍历i--if (j 0 s[j] g[i]) { //遍历饼干当存在满足当前胃口饼干时ans;j--; //j指针左移}}return ans;}
};
题目二376. 摆动序列
题目链接
376. 摆动序列 - 力扣LeetCode 如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 。第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如 [1, 7, 4, 9, 2, 5] 是一个 摆动序列 因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。 相反[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。 子序列 可以通过从原始序列中删除一些也可以不删除元素来获得剩下的元素保持其原始顺序。 给你一个整数数组 nums 返回 nums 中作为 摆动序列 的 最长子序列的长度 。 示例 1 输入nums [1,7,4,9,2,5]
输出6
解释整个序列均为摆动序列各元素之间的差值为 (6, -3, 5, -7, 3) 。示例 2 输入nums [1,17,5,10,13,15,10,5,16,8]
输出7
解释这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] 各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。示例 3 输入nums [1,2,3,4,5,6,7,8,9]
输出2提示 1 nums.length 10000 nums[i] 1000 题解贪心
个人感觉这道题第一次接触的话还是挺有难度的。
这里考察到了摆动序列我们可以将每一个元素的的下标作为横坐标值作为纵坐标大致画在图上那么就会得到一个波形图其中每次出现的摆动都是一个峰值类似于波峰或者波谷我们需要得到的摆动序列的长度其实就是峰值数1。由于默认序列至少一个元素所有我们初始化摆动序列长度为1
然后这道题的重点就变成了如何实现找到峰值的数目峰值数。我们定义两个变量一个表示当前一对元素的差值一个表示前一对元素的差值通过判断两差值是否异号实现对峰值部分的判断。
这个题还有一个关键的点就是对于平坡的处理需要注意的是遇到平坡表示前一对元素的差值不变因为平坡不在序列长度的考虑部分。
class Solution {
public:int wiggleMaxLength(vectorint nums) {int n nums.size();if (n 1) { //仅有一个元素时直接返回即可return n;}int curDiff 0; //当前一对差值后一个元素和当前元素nums[i 1] - nums[i]int preDiff 0; //前一对差值用于和当前一对差值比较以检测是否发生摆动int ans 1; //表示摆动序列长度由于默认序列至少一个元素初始化为1摆动序列长度 峰值数 1for (int i 0; i n - 1; i) {curDiff nums[i 1] - nums[i];if ((preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)) { //如果发生了摆动出现了峰值波峰或波谷 ans;preDiff curDiff; //注意这里只在摆动变化的时候更新prediff这样就能考虑到平坡的情况--出现平坡时不改变前一对差值}}return ans;}
};
题目三53. 最大子序和
题目链接
53. 最大子数组和 - 力扣LeetCode 给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 子数组 是数组中的一个连续部分。 示例 1 输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6 。示例 2 输入nums [1]
输出1示例 3 输入nums [5,4,-1,7,8]
输出23提示 1 nums.length 105-104 nums[i] 104 题解1暴力失败
先看看暴力解法未能通过全部案例
暴力解法的思路很简单这里就不做过多解释毕竟是个失败的做法。 题解2贪心
这个题其实我感觉贪心用的还是比较巧妙就是当你前面所有元素之和为负数的时候就可以直接跳过从下一个元素重新开始寻找新的子序列。但是这个时候你必须要记录下前面那些元素所拥有的最大子序和和后面新开的子序列做比较当然如果没有存在前面元素和为负数情况的话就只需要不断遍历比较得出最大值即可。
代码如下
class Solution {
public:int maxSubArray(vectorint nums) {int ans INT_MIN; //类似寻找最大最小值的题目初始值一定要定义成理论上的最小最大值int n nums.size();int sum 0; //记录当前子数组元素的和for (int i 0; i n; i) {sum nums[i]; //不断添加元素改变当前子数组的和每次添加完元素求和都与原最大值比较并判断是否小于0ans max(ans, sum); //不断更新结果取较大值if (sum 0) { //关键前面元素求和为负数直接跳过从下一个元素重新开始记录新的子数组加上负数肯定变小sum 0;}}return ans;}
};
三、小结
贪心还是得多做题很多东西是不好描述出来的只有通过不断做题看代码才能慢慢感到有收获。
最后我是算法小白但也希望终有所获。
