静态html网址网站导航源码,wordpress获取文章图片,郴州做网站的公司,设计网站免费大全贪心算法三 1.买卖股票的最佳时机2.买卖股票的最佳时机 II3.K 次取反后最大化的数组和4.按身高排序5.优势洗牌#xff08;田忌赛马#xff09; 点赞#x1f44d;#x1f44d;收藏#x1f31f;#x1f31f;关注#x1f496;#x1f496; 你的支持是对我最大的鼓励#… 贪心算法三 1.买卖股票的最佳时机2.买卖股票的最佳时机 II3.K 次取反后最大化的数组和4.按身高排序5.优势洗牌田忌赛马 点赞收藏关注 你的支持是对我最大的鼓励我们一起努力吧! 1.买卖股票的最佳时机
题目链接 121. 买卖股票的最佳时机
题目分析 买卖股票的最佳时机既可以用贪心也可以用动规其中所有的股票问题都可以只用动规来解但是有些题用贪心来解思路和写法是更优的。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。这句话的意思是买卖股票只能执行一次。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。
算法原理
我们用圆圈代表数组中一个个元素。
如果我们把题意搞清楚我们很容易想到一个暴力策略我们要最大利润的话无非就是在数组中挑出两个位置一个位置是买入一个位置是卖出使这两个位置的值的差是最大的。此时我们有一个暴力解法可以把所有的二元组枚举出来也就是两次for循环第一层for依次从左往右固定一个卖出位置第二层for依次枚举买入位置每到一个位置就用卖出位置 - 买入位置把所有情况的差求一个最大值。当固定完一个卖出位置之后卖入位置往后走一步然后买入位置继续从头开始枚举。
解法一暴力解法两层 for 循环的暴力枚举
但是时间复杂度是O(N^2) 有了这两层 for 循环的暴力枚举我们可以想到一个优化方式固定卖出位置的时候我们想找到这一段的最大利润我们之前是从头开始枚举。我们买入点其实就是在找以该卖出点位置的最大利润此时贪心就来了我们其实进行找到卖入位置之前买入的最小值就行了然后拿卖出减去前面买入的最小值就是这个点卖出的最大利润。所以我们仅需知道卖出之前所有买入位置的最小值就可以了。
我们求最小值如果从前往后遍历时间复杂度是O(N)如果固定完一个卖出位置就已经知道前面买入位置的最小值时间复杂度就是O(1)那整体时间复杂度就是O(N) 当我们把这个卖出位置的最大利润知道之后接下来要求下一个卖出位置的最大利润我们可以在去下一个卖出位置之前拿之前的 prevMin 和 该卖出位置 做比较 求一个最小值就知道 下一个卖出位置之前所有买入位置的最小值。 解法二 贪心 一个变量标记 “前缀最小值” 时间复杂度O(N)
我们这个贪心策略其实适合暴力解法结果是一样的依旧把所有情况都枚举到所以暴力是对的贪心也是对的。
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();int ret 0, prevmin INT_MAX;for(int i 0; i n; i){ret max(ret, prices[i] - prevmin);// 先更新结果prevmin min(prevmin, prices[i]); // 在更新最⼩值}return ret;}
};动态规划
因为这个动态规划思想其实就和上面贪心几乎是一模一样的都是找前 i 天 的最低价格所以我们直接给代码。
class Solution {
public:int maxProfit(vectorint prices) {// int n prices.size();// int ret 0, prevmin INT_MAX;// for(int i 0; i n; i)// {// ret max(ret, prices[i] - prevmin);// 先更新结果// prevmin min(prevmin, prices[i]); // 在更新最⼩值// }// return ret;// 动态规划//dp[i] 表示: 前 i 天 价格最低点int n prices.size(), ret 0;vectorint dp(n 1);dp[0] INT_MAX;for(int i 1; i n; i){ret max(ret, prices[i - 1] - dp[i - 1]);dp[i] min(dp[i - 1], prices[i - 1]);}return ret;}
};2.买卖股票的最佳时机 II
题目链接 122. 买卖股票的最佳时机 II
题目分析 在每一天你可以决定是否购买和/或出售股票这句话的意思就决定了买卖股票是没有限制的。你在任何时候 最多 只能持有 一股 股票。这句话的意思是这一天你手里有股票是不能够在买的。要想这一天把股票买走你必须把手里股票卖出之后才能在买。你也可以先购买然后在 同一天 出售这句话的意思是你可以今天买今天就卖我们是可以进行这样操作的。
返回 你能获得的 最大 利润 。
算法原理
我们把数组中的数放在一个二维平面能够很清楚看见股票的增减关系还能得到我们的策略。 这道题我们是可以执行任意多笔交易也就是可以选任意点买入股票任意点卖出股票。此时我们要获得最大利润看这个图是否有这样的想法你会选择在下降趋势买卖股票吗肯定不会的。只要是下降趋势我们都不会买卖股票。
所以说我们的贪心策略非常简单在这个图像中只要是股票价格是上升趋势的我就买和卖在上升最低点买入在上升最高点卖出。那么我就可以获得最大利润。 水平和下降我们都不会买卖股票。
贪心策略只要能获得正收益我就交易。
如何实现实现方式有两种
双指针
我们要在数组中找增加的区域所以我们可以先定义一个指针 i 指向初始位置同时定义一个指针 j 从指针 i 位置开始往后遍历只要当前位置的值小于后面位置的值j 就往后走。如果发现后面的值小于或者等于 j 位置的值说明 i 到 j 增长的区域已经被找到此时搞一个全局的retret p[j] - p[i]当计算完这一段的时候更新 i 到 j 位置 或者 j 1位置然后 j 进行从 i 位置开始。如果发现后面的值比 j 小没关系j 是不移动的此时ret p[j] - p[i] 是等于 0 的。 2. 拆分交易把一段交易拆分成一天一天
我们求前面这段上升区域在双指针哪里其实是 p[3] - p[1]此时我们发现求这一整段的利润时可以拆分成两段利润。我们会发现 p[3] - p[1] 正好等于 p[3] - p[2] p[2] - p[1] 然后p[2]一抵消两边就是相等的。左边是整体计算右边是分开计算它们的利润是一样的。所以只要是一段上升区域我们都可以拆分成一天一天。 class Solution {
public:int maxProfit(vectorint prices) {// 实现方式一: 双指针// int ret 0, n prices.size();// for(int i 0; i n; )// {// int j i;// while(j 1 n prices[j] prices[j 1]) j;//找上升的末端// ret prices[j] - prices[i];// i j 1;// }// return ret;// 实现⽅式⼆: 拆分成⼀天⼀天int ret 0, n prices.size();for(int i 0; i n - 1; i){if(prices[i] prices[i 1])ret prices[i 1] - prices[i];}return ret;}
};3.K 次取反后最大化的数组和
题目链接 1005. K 次取反后最大化的数组和
题目分析 对数组中的数取k次取反操作注意可以多次选择同一个数进行进行取反操作。以这种方式修改数组后返回数组 可能的最大和。
算法原理
如果想对数组执行取反操作让数组和是最大的我们下意识就会先挑选负数变成正数而且是挑选最小的那个负数。
然后根据 k 和 数组中负数的个数的关系我们进行分类讨论
设整个数组中负数的个数是 m 个。
m k
负数的个数比取反k次要多 2. m k
负数个数和k的个数一样其实可以归类到第一类情况直接把所有负数转化为整数。 m k
负数个数小于k的个数 此时在对 k - m 的奇偶性分析。如果整个数组是正数的话我们非常不希望把里面的数变成负数。
当 k - m 是偶数的时候那我们就疯狂的对一个数进行取反操作对一个数进行偶数次取反操作这个数是不变的。
当 k - m 是奇数的时候我们必须会让一个数变成负数此时我们会让数组中最小的数变成负数。损失是最小的。 class Solution {
public:int largestSumAfterKNegations(vectorint nums, int k) {int m 0, minElem INT_MAX, n nums.size();for(auto x : nums){if(x 0) m;minElem min(minElem, abs(x));// 求绝对值最⼩的那个数}// 分类讨论int ret 0;if(m k){sort(nums.begin(), nums.end());for(int i 0; i k; i)// 前 k ⼩个负数变成正数ret abs(nums[i]);for(int i k; i n; i)// 后⾯的数不变ret nums[i];}else{// 把所有的负数变成正数for(auto x : nums) ret abs(x);if((k - m) % 2)// 判断是否处理最⼩的正数{ret - minElem * 2;}}return ret;}
};4.按身高排序
题目链接 2418. 按身高排序
题目分析 这道题并不是一道贪心题它只是一道排序题。但是这道题里面的排序思想会用到下到题里面。
给你一个字符串数组 names 和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。对于每个下标 inames[i] 和 heights[i] 表示第 i 个人的名字和身高也就是说这两个数组是绑定的。按身高 降序 顺序返回对应的名字数组 names。
算法原理
这道题主要就是排序接下来我们就想如何排序就可以了。
我们要对身高进行降序排序但是不能直接排如果不管名字直接拿升高排序排完序之后身高和姓名就可能不是对应的了。 我们必须要保证排完序后姓名和升高映射关系要能对应上。
此时我们有三种解决方式
解法一创建二元组
创建一个新的数组pairintstring把原始身高和姓名绑定重新放在pair数组里面对新的数组按照第一个元素排序按照顺序把名字提取出来即可 解法二 利用哈希表存下映射关系
先用哈希表存下映射关系 身高名字对身高数组排序根据排序后的结果往哈希表里找名字即可 虽然这两种方法都能解决问题但是都是有缺陷的。统一的缺陷就是既要存身高也要存名字第二个缺陷就是解法二的缺陷有可能身高时重复的但是我们的hash里key是不能相同的此时解决方法就是把string改成string数组。
解法三对下标排序非常常用的一个技巧
在排序的时候虽然想排序但是并不想改变元素原始的位置。也就是说排序之前元素在那个位置排序后该元素还在那个位置。刚好我们这道题就符合这样排序排序后身高和姓名还是和之前一一对应。
创建一个下标数组仅需对下标数组排序根据下标数组排序后的结果找到原数组的信息
假如有下面的姓名数组和身高数组我们的策略就是创建一个下标数组下标数组保存对应的信息的下标。然后仅需对下标数组排序排序的时候就按照要求来排这里下标数组排序按照身高的降序来排所以我们要重写一个排序比较方法。排序我们也是也是对下标数组排序原始的数组我们可没动接下来通过下标就可以找到对应的身高和姓名。 class Solution {
public:vectorstring sortPeople(vectorstring names, vectorint heights) {// 解法一 // // 1. 创建一个pairint,string数组// int n heights.size();// vectorpairint,string x(n);// for(int i 0; i n; i)// x[i] make_pair(heights[i],names[i]);// // 2. 对数组元素进行排序// sort(x.begin(), x.end(), [](const pairint,string p1, const pairint,string p2)// {// return p1.first p2.first;// });// // 3. 提取结果// vectorstring ret;// for(auto p : x)// {// ret.push_back(p.second);// }// return ret;// 解法二// // 1.创建一个hash表// unordered_mapint,string hash;// int n heights.size();// for(int i 0; i n; i)// hash[heights[i]] names[i];// // 2. 对身高数组进行排序// sort(heights.begin(), heights.end(), greaterint());// // 3.提取结果// vectorstring ret;// for(auto x: heights)// {// ret.push_back(hash[x]);// }// return ret;// 解法三// 1. 创建一个下标数组int n heights.size();vectorint index(n);for(int i 0; i n; i) index[i] i;// 2. 对下标进行排序sort(index.begin(), index.end(), [heights](const int i, const int j){return heights[i] heights[j];});// 3. 提取结果vectorstring ret;for(auto i : index){ret.push_back(names[i]);}return ret;}
};5.优势洗牌田忌赛马
题目链接 870. 优势洗牌
题目分析 给定两个长度相等的数组 nums1 和 nums2nums1 相对于 nums2 的优势可以用满足 nums1[i] nums2[i] 的数目来描述。也就是说相同位置只要nums1数组的数比nums2数组的数大就存在一个优势。
返回 nums1 的任意排列使其相对于 nums2 的优势最大化。也就是想办法对第一个数组进行排序使排序后的优势使最大的。 算法原理
我们先回忆田忌赛马的故事当把这道题题意搞清楚后你会发现它和田忌赛马的故事是一模一样的。田忌赛马无非就三匹马在比我们这里是有很多马在比。但是它的策略和田忌赛马的策略是一样的。我们从田忌赛马的故事提取最优策略。
田忌赛马故事很简单齐威王和田忌在赛马按照等级把马划分为上、中、下三匹马它们每次都按照上、中、下的顺序比较但是同级别下齐威王的马比田忌的好所以结果都每次都是齐威王赢。这个时候来了一个孙膑它给田忌出了一个策略让田忌更改一下马的出场顺序改成 下、上、中。此时田忌在和齐威王比较虽然他的下等马对齐威王的上等马是惨败的但是他的上等马是胜于齐威王的中等马中等马胜于齐威王的下等马。此时田忌获得胜利。 接下来我们从这个故事中提取孙膑的最优策略为了方便叙述我们将他俩的马从小到大排序。刚开始拿着田忌的下等马去比齐威王的下等马你会发现是干不过的如果比不过就相当于齐威王所有的马田忌的下等马都比不过。因为我们已经按照从小到大排序了如果田忌的下等马连齐威王最差的那匹马都比不过那它所有的马都比不过。这里我们的第一个贪心策略如果连最差的比不过那就去拖累掉最强的那匹马废物利用最大化。接下来考虑田忌的中等马发现中等马能打过齐威王的下等马上等马也能打过齐威王的下等马此时第二个贪心策略当前最差的马就已经能比掉齐威王最差的马绝对不会浪费更优秀的马。 总结一下最优策略
排序如果比不过就去拖累掉对面最强的那一个如果能比过那就直接比
接下来我们模拟一下
先对数组进行排序我们是要把nums1数组修改成ret 8比不过11我们的策略是废物利用最大化直接去匹配最强的32 12比的过11直接放 24比的过13直接放 32比的过25直接放 这个ret就是我们最优的策略但是这个结果和答案给的不一样 原因是答案是按照未排序之前的num2的顺序来匹配最终结果的。意思就是如果是11对12应该是原始的nums2数组的11的位置放12而不是在排完序后的第一个位置放12. 同理其他都是如此然后这个数组才是我们要的最终结果 原因就在于我们排完序之后是要按照之前排序之前的数组来还原的所以就出现了虽然想排序但是原来的顺序我还要知道。那如何实现这一点呢《身高排序》 这到题我们正好用了这个技巧又想让数组排序又想找到之前的相对位置我们的策略是直接排序下标数组。不排原始数组对下标数组进行排序然后通过下标数组找到原始的数最终就能把ret对应到原始的位置。
接下来我们在模拟一下这个过程。
先对下标数组排序如何排序之前已经说过改变排序规则这里我们还需要两个指针left指向num2下标数组排序后的第一个元素的下标right指向nums2下标数组排序后的最后一个元素的下标。 依次遍历nums1每次和left所指向的下标对应nums2中的元素做比较nums2[index2[left]]
8比不过11把8放在最后一个位置此时并不是把8放在ret最后一个位置而是把8放在nums2排完序之后的最后一个位置所对应的下标的位置。也ret下标为2的位置。然后right–代表之前的数已经匹配过了此时最后一个位置的就是下标1。 12比的过left所指向下标对应的数11就放在第一个位置第一个位置下标是3然后left 24比的过left所指向下标对应的数13就放在0位置然后left 32比的过left所指向下标对应的数25放在下标1的位置此时nums1遍历完就结束了。 class Solution {
public:vectorint advantageCount(vectorint nums1, vectorint nums2) {int n nums1.size();// 1. 排序sort(nums1.begin(), nums1.end());vectorint index2(n);for(int i 0; i n; i) index2[i] i;sort(index2.begin(), index2.end(), [](const int i, const int j){//所有下标按照nums2里面升序形式排序return nums2[i] nums2[j];});// 2. 田忌赛马vectorint ret(n);int left 0, right n - 1;for(int i 0; i n; i){if(nums1[i] nums2[index2[left]]){ret[index2[left]] nums1[i];left;}else{ret[index2[right]] nums1[i];--right;}}return ret;}
};证明
证明方法交换论证法
nums1表示排序后升序的样子nums2也表示排序后的样子并且nums1表示的贪心解 在来一个nums1表示最优解的情况 交换论证法就是在最优解不失去最优性的情况下调整成贪心解的话那我们就说贪心解就是最优解。
从左往右扫描贪心解和最优解的匹配情况当遇到第一个它们俩匹配不同的情况就考虑这个点。
我们要分两种情况讨论
贪心解比的过
贪心解比得过那就去匹配第一个最优解和贪心解不一样最优解就去匹配后面的。然后最优解后面的在和第一个匹配 接下来就看最优解调整成贪心解会不会变差。
如何调整就是调的和贪心解一样就可以了这里我们设一些变量然后在贪心解比得过我们有一个不等式 b a x1 a x1b x1这两条线可以抵消 剩下两条线我们不容易得出胜负情况 我们仅知道 b a x1我们并不知道a是否大于x2也并不知道b是否大于x2。但是我们可以粗略估计一下用b来比较x2是更优的原因是最优解之前拿的是较小的a都能和x2匹配调整完之后拿较大的b和x2匹配所以绝对是更优的。a能胜过x2b一定能胜过a打不过x2但是b比a大是有可能打得过x2的。 所以我们第一种情况是可以的。
贪心解比不过
如果比不过贪心选择的策略就是和最后一个抵消最优解肯定不是最后一个接下来我们继续调整。依旧是调整后的别比之前的差就可以。 我们的谈贪心解是比不过第一个才会抵消最后一个也就是比nums2最小的还要小。调整之前拿最优解的a和nums2前面的匹配调整后和nums2最后一个匹配反正都不会得分所以可以抵消。 剩下还有两条线你会发现调整最优解b之后是更优的b是固定的之前b是去匹配较大的的x2现在是匹配较小的x1b能打过x1一定能打过x2b打不过x2可能会打过x1。 因为我们最优解调整后是更优的所以最优解肯定能在不失去最优性的前提下调整到贪心解。 文章转载自： http://www.morning.2d1bl5.cn.gov.cn.2d1bl5.cn http://www.morning.fkflc.cn.gov.cn.fkflc.cn http://www.morning.gwjqq.cn.gov.cn.gwjqq.cn http://www.morning.wkrkb.cn.gov.cn.wkrkb.cn http://www.morning.ydxg.cn.gov.cn.ydxg.cn http://www.morning.bzqnp.cn.gov.cn.bzqnp.cn http://www.morning.bfsqz.cn.gov.cn.bfsqz.cn http://www.morning.mzpd.cn.gov.cn.mzpd.cn http://www.morning.nsyzm.cn.gov.cn.nsyzm.cn http://www.morning.qbrs.cn.gov.cn.qbrs.cn http://www.morning.hmwjk.cn.gov.cn.hmwjk.cn http://www.morning.bpmfr.cn.gov.cn.bpmfr.cn http://www.morning.youprogrammer.cn.gov.cn.youprogrammer.cn http://www.morning.sgtq.cn.gov.cn.sgtq.cn http://www.morning.knpbr.cn.gov.cn.knpbr.cn http://www.morning.clqpj.cn.gov.cn.clqpj.cn http://www.morning.bpmdn.cn.gov.cn.bpmdn.cn http://www.morning.wmqrn.cn.gov.cn.wmqrn.cn http://www.morning.tjsxx.cn.gov.cn.tjsxx.cn http://www.morning.fkmrj.cn.gov.cn.fkmrj.cn http://www.morning.jtfcd.cn.gov.cn.jtfcd.cn http://www.morning.czxrg.cn.gov.cn.czxrg.cn http://www.morning.c7629.cn.gov.cn.c7629.cn http://www.morning.kztpn.cn.gov.cn.kztpn.cn http://www.morning.bylzr.cn.gov.cn.bylzr.cn http://www.morning.frpb.cn.gov.cn.frpb.cn http://www.morning.pfnlc.cn.gov.cn.pfnlc.cn http://www.morning.gychx.cn.gov.cn.gychx.cn http://www.morning.pzrpz.cn.gov.cn.pzrpz.cn http://www.morning.gcqdp.cn.gov.cn.gcqdp.cn http://www.morning.xysdy.cn.gov.cn.xysdy.cn http://www.morning.trhlb.cn.gov.cn.trhlb.cn http://www.morning.rrrrsr.com.gov.cn.rrrrsr.com http://www.morning.rgmd.cn.gov.cn.rgmd.cn http://www.morning.fmrwl.cn.gov.cn.fmrwl.cn http://www.morning.nytqy.cn.gov.cn.nytqy.cn http://www.morning.knzdt.cn.gov.cn.knzdt.cn http://www.morning.qlpyn.cn.gov.cn.qlpyn.cn http://www.morning.qcdtzk.cn.gov.cn.qcdtzk.cn http://www.morning.xhhqd.cn.gov.cn.xhhqd.cn http://www.morning.nwfpl.cn.gov.cn.nwfpl.cn http://www.morning.5-73.com.gov.cn.5-73.com http://www.morning.bpmnj.cn.gov.cn.bpmnj.cn http://www.morning.xnpj.cn.gov.cn.xnpj.cn http://www.morning.dfndz.cn.gov.cn.dfndz.cn http://www.morning.nylbb.cn.gov.cn.nylbb.cn http://www.morning.lskrg.cn.gov.cn.lskrg.cn http://www.morning.npbkx.cn.gov.cn.npbkx.cn http://www.morning.dbqg.cn.gov.cn.dbqg.cn http://www.morning.rftk.cn.gov.cn.rftk.cn http://www.morning.jcrlx.cn.gov.cn.jcrlx.cn http://www.morning.lqpzb.cn.gov.cn.lqpzb.cn http://www.morning.gqjwz.cn.gov.cn.gqjwz.cn http://www.morning.bmts.cn.gov.cn.bmts.cn http://www.morning.fbzyc.cn.gov.cn.fbzyc.cn http://www.morning.rwyd.cn.gov.cn.rwyd.cn http://www.morning.syglx.cn.gov.cn.syglx.cn http://www.morning.pcrzf.cn.gov.cn.pcrzf.cn http://www.morning.yzxlkj.com.gov.cn.yzxlkj.com http://www.morning.jrplk.cn.gov.cn.jrplk.cn http://www.morning.bmncq.cn.gov.cn.bmncq.cn http://www.morning.bjjrtcsl.com.gov.cn.bjjrtcsl.com http://www.morning.tfkqc.cn.gov.cn.tfkqc.cn http://www.morning.lsmnn.cn.gov.cn.lsmnn.cn http://www.morning.yodajy.cn.gov.cn.yodajy.cn http://www.morning.pggkr.cn.gov.cn.pggkr.cn http://www.morning.hsflq.cn.gov.cn.hsflq.cn http://www.morning.vvdifactory.com.gov.cn.vvdifactory.com http://www.morning.bnfjh.cn.gov.cn.bnfjh.cn http://www.morning.znrlg.cn.gov.cn.znrlg.cn http://www.morning.rnlx.cn.gov.cn.rnlx.cn http://www.morning.kxrld.cn.gov.cn.kxrld.cn http://www.morning.zzgtdz.cn.gov.cn.zzgtdz.cn http://www.morning.zhengdaotang.cn.gov.cn.zhengdaotang.cn http://www.morning.jxjrm.cn.gov.cn.jxjrm.cn http://www.morning.rwfp.cn.gov.cn.rwfp.cn http://www.morning.bhrbr.cn.gov.cn.bhrbr.cn http://www.morning.myhpj.cn.gov.cn.myhpj.cn http://www.morning.gtwtk.cn.gov.cn.gtwtk.cn http://www.morning.dsgdt.cn.gov.cn.dsgdt.cn
