我们熟知的选择排序,其采用的就是贪心策略。它所采用的贪心策略即为每次从未排序的数据中选取最小值,并把最小值放在未排序数据的起始位置,直到未排序的数据为0,则结束排序。
voidswap(int*arr,inti,intj){inttmp=arr[i];arr[i]=arr[j];arr[j]=tmp;}voidselectSort(int*arr,intn){//降序for(inti=0;i=arr[maxIndex])maxIndex=j;}swap(arr,i,maxIndex);}}平衡字符串问题描述:
在一个平衡字符串中,‘L’和‘R’字符的数量是相同的。给你一个平衡字符串s,请你将它分割成尽可能多的平衡字符串。注意:分割得到的每个字符串都必须是平衡字符串,且分割得到的平衡字符串是原平衡字符串的连续子串。返回可以通过分割得到的平衡字符串的最大数量。
贪心策略:从左往右扫描,只要达到平衡,就立即分割,不要有嵌套的平衡。故可以定义一个变量balance,在遇到不同的字符时,向不同的方向变化,当balance为0时达到平衡,分割数更新。比如:从左往右扫描字符串s,遇到L,balance-1,遇到R,balance+1.当balance为0时,更新cnt++如果最终cnt==0,说明s只需要保持原样,返回1
代码实现:
classSolution{public:intbalancedStringSplit(strings){if(s.size()==1)return0;intcnt=0;intbalance=0;for(inti=0;i买股票的最佳时机问题描述:
给定一个数组prices,其中prices[i]是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
classSolution{public:intmaxProfit(vector&prices){intprofit=0;for(inti=0;i跳跃游戏问题描述:
给定一个非负整数数组nums,你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
贪心策略:根据题目描述,对于数组中的任意一个位置y,只要存在一个位置x,它本身可以到达,并且它跳跃的最大长度为x+nums[x],这个值大于等于y,即x+nums[x]>=y,那么位置y也可以到达。即对于每一个可以到达的位置x,它使得x+1,x+2,…,x+nums[x]>=y,那么位置y也可以到达。一次遍历数组中的每一个位置,并实时更新最远可以到达的位置。对于当前遍历到的位置x,如果它在最远可以到达的位置范围内,那么我们就可以从起点通过若干次跳跃达到该位置,因此我们可以用x+nums[x]更新最远可以到达的位置。在遍历的过程中,如果最远可以到达的位置大于等于数组中的最后一个位置,那就说明最后一个位置可到达,直接返回true。遍历结束后,最后一个位置仍不可达,返回false。例如:[2,3,1,1,4]一开始在位置0,可跳跃的最大长度为2,因此最远可以到达的位置倍更新为2;继续遍历到位置1,由于1<=2,因此位置1可达。用1加上它最大可跳跃的长度3,将最远可以到达的位置更新为4,4大于最后一个位置4,返回true代码实现:classSolution{public:boolcanJump(vector&nums){intmaxLen=nums[0];for(inti=0;i=nums.size()-1)returntrue;}}returnfalse;}};钱币找零问题描述:
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0,c1,c2,c3,c4,c5,c6张。现在要用这些钱来支付K元,至少要用多少张纸币?
贪心策略:显然,每一步尽可能用面值大的纸币即可。在日常生活中我们也是这么做的。
//按面值降序structcmp{booloperator()(vector&a1,vector&a2){returna1[0]>a2[0];}};intsolve(vector>&moneyCount,intmoney){intnum=0;sort(moneyCount.begin(),moneyCount.end(),cmp());//首先选择最大面值的纸币for(inti=0;i0)num=-1;returnnum;}多机调度问题问题描述:
structcmp{booloperator()(vector&s1,vector&s2){returns1[1]>&events){sort(events.begin(),events.end(),cmp());intnum=1;inti=0;for(intj=1;j=events[i][1]){++num;i=j;}}returnnum;}无重叠区间问题描述:
给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。注意:可以认为区间的终点总是大于它的起点。区间[1,2]和[2,3]的边界相互“接触”,但没有相互重叠。
structcmp{booloperator()(vector&s1,vector&s2){returns1[1]>&intervals){sort(intervals.begin(),intervals.end(),cmp());intnum=1;inti=0;for(intj=1;j=intervals[i][1]){i=j;num++;}}returnintervals.size()-num;}};