LeetCode：贪心算法

目录

一、分发饼干

二、摆动序列

三、最大子数组和

四、买卖股票的最佳时机II

五、跳跃游戏

六、跳跃游戏II

七、K次取反后最大化的数组和

八、加油站

九、分发糖果

十、柠檬水找零

十一、根据身高重建队列

十二、用最少数量的箭引爆气球

十三、无重叠区间

十四、划分字母区间

十五、合并区间

十六、单调递增的数字

---

一、分发饼干

455. 分发饼干 - 力扣（LeetCode）

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(s);Arrays.sort(g);int index=s.length-1;//饼干下标int result=0;//可满足的孩子数量for(int i=g.length-1;i>=0;i--){if(index>=0&&s[index]>=g[i]){//饼干的尺寸大于等于孩子的胃口result++;//满足的孩子+1index--;//下标左移}}return result;}
}

二、摆动序列

376. 摆动序列 - 力扣（LeetCode）

class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length<=1)return nums.length;int cur=0;int pre=0;int result=1;for(int i=0;i<nums.length-1;i++){cur=nums[i+1]-nums[i];if((cur>0&&pre<=0)||(cur<0&&pre>=0)){result++;pre=cur;}}return result;}
}

三、最大子数组和

53. 最大子数组和 - 力扣（LeetCode）

class Solution {public int maxSubArray(int[] nums) {int result=Integer.MIN_VALUE;int count=0;for(int i=0;i<nums.length;i++){count+=nums[i];result=Math.max(count,result);if(count<=0)count=0;//相当于重置最大子序列起始位置，因为遇到负数一定是拉低总和}return result;}
}

四、买卖股票的最佳时机II

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

class Solution {public int maxProfit(int[] prices) {int res=0;for(int i=1;i<prices.length;i++){res+=Math.max(prices[i]-prices[i-1],0);//找每日的正利润}return res;}
}

五、跳跃游戏

55. 跳跃游戏 - 力扣（LeetCode）

class Solution {public boolean canJump(int[] nums) {int cover=0;if(nums.length==1)return true;for(int i=0;i<=cover;i++){cover=Math.max(i+nums[i],cover);if(cover>=nums.length-1)return true;}return false;}
}

六、跳跃游戏II

45. 跳跃游戏 II - 力扣（LeetCode）

class Solution {public int jump(int[] nums) {int curcover=0;int nextcover=0;int count=0;if(nums.length==1)return count;for(int i=0;i<=curcover;i++){nextcover=Math.max(i+nums[i],nextcover);if(i==curcover){count++;curcover=nextcover;if(nextcover>=nums.length-1)break;}}return count;}
}

七、K次取反后最大化的数组和

1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);int sum=0;for(int i=0;i<nums.length&&k>0;i++){if(nums[i]<0){//找到排序后小于0的值，将它们改为相反数nums[i]=-nums[i];k--;}}if(k%2==1){//若k依旧大于0，且k为奇数，将最小值变为它的相反数Arrays.sort(nums);nums[0]=-nums[0];}for(int num:nums)sum+=num;//求和return sum;}
}

八、加油站

134. 加油站 - 力扣（LeetCode）

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum=0;int totalsum=0;int start=0;for(int i=0;i<gas.length;i++){curSum+=gas[i]-cost[i];totalsum+=gas[i]-cost[i];if(curSum<0){//curSum<0,说明[0,i]不能作为起点，否则会断油start=i+1;curSum=0;}}if(totalsum<0)return -1;return start;}
}

九、分发糖果

135. 分发糖果 - 力扣（LeetCode）

class Solution {public int candy(int[] ratings) {int[] candy=new int[ratings.length];candy[0]=1;for(int i=1;i<ratings.length;i++){if(ratings[i]>ratings[i-1])candy[i]=candy[i-1]+1;else candy[i]=1;}for(int i=ratings.length-1;i>0;i--){if(ratings[i-1]>ratings[i])candy[i-1]=Math.max(candy[i-1],candy[i]+1);}int sum=0;for(int i:candy)sum+=i;return sum;}
}

十、柠檬水找零

860. 柠檬水找零 - 力扣（LeetCode）

class Solution {public boolean lemonadeChange(int[] bills) {int five=0,ten=0,twenty=0;for(int bill:bills){if(bill==5)five++;if(bill==10){if(five<=0)return false;five--;ten++;}if(bill==20){if(five>0&&ten>0){five--;ten--;twenty++;}else if(five>=3){five-=3;twenty++;}else return false;}}return true;}
}

十一、根据身高重建队列

406. 根据身高重建队列 - 力扣（LeetCode）

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people,(a,b)->{if(a[0]==b[0])return a[1]-b[1];//体重相等则按k值排序，k小在前return b[0]-a[0];//按体重降序排列});LinkedList<int[]> res=new LinkedList<>();for(int[] i:people)res.add(i[1],i);return res.toArray(new int[people.length][]);}
}
/*
举例解释：[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
排序后：[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
结果集:     i    i[1]    res0     0      [7,0]1     1      [7,0],[7,1]2     1      [7,0],[6,1],[7,1]3     0      [5,0],[7,0],[6,1],[7,1]4     2      [5,0],[7,0],[5,2],[6,1],[7,1]5     4      [5,0],[7,0],[5,2],[6,1],[4,4],[7,1]
*//*逆序排序
Arrays.sort(num,new Comparator<Integer>(){public int compare(Integer a, Integer b){return b-a;}
});*/

十二、用最少数量的箭引爆气球

452. 用最少数量的箭引爆气球 - 力扣（LeetCode）

class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));int count=1;for(int i=1;i<points.length;i++){if(points[i][0]>points[i-1][1])count++;else points[i][1]=Math.min(points[i][1],points[i-1][1]);}return count;}
}

十三、无重叠区间

435. 无重叠区间 - 力扣（LeetCode）

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));int count=1;for(int i=1;i<intervals.length;i++){if(intervals[i][0]>=intervals[i-1][1])count++;else intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);}return intervals.length-count;}
}

十四、划分字母区间

763. 划分字母区间 - 力扣（LeetCode）

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> res=new ArrayList<>();int[] index=new int[27];char[] chars=s.toCharArray();for(int i=0;i<chars.length;i++)index[chars[i]-'a']=i;int left=0;int right=0;for(int i=0;i<chars.length;i++){right=Math.max(right,index[chars[i]-'a']);if(right==i){res.add(right-left+1);left=i+1;}}return res;}
}

十五、合并区间

56. 合并区间 - 力扣（LeetCode）

class Solution {public int[][] merge(int[][] intervals) {List<int[]> res=new ArrayList<>();Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));//按左边界排序int left=intervals[0][0];int right=intervals[0][1];for(int i=1;i<intervals.length;i++){if(intervals[i][0]>right){res.add(new int[]{left,right});left=intervals[i][0];right=intervals[i][1];}else right=Math.max(right,intervals[i][1]);}res.add(new int[]{left,right});return res.toArray(new int[res.size()][]);}
}

十六、单调递增的数字

738. 单调递增的数字 - 力扣（LeetCode）

class Solution {public int monotoneIncreasingDigits(int n) {String str=String.valueOf(n);char[] s=str.toCharArray();int flag=s.length;for(int i=s.length-1;i>0;i--){if(s[i-1]>s[i]){flag=i;s[i-1]--;}}for(int i=flag;i<s.length;i++)s[i]='9';return Integer.parseInt(String.valueOf(s));}
}