贪心算法习题其二【力扣】【算法学习day.18】
前言
###我做这类文档一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴!!!
习题
1.分发糖果
题目链接:135. 分发糖果 - 力扣(LeetCode)
题面:
基本分析: 从左往右遍历,需要满足高分比低分多,从右往左遍历,同样也需要,遍历两次取最大值
代码:
class Solution {public int candy(int[] ratings) {int n = ratings.length;int[] left = new int[n];int[] right = new int[n];Arrays.fill(left,1);Arrays.fill(right,1);for(int i =1;i<n;i++){if(ratings[i]>ratings[i-1]){left[i]=left[i-1]+1;}}int sum = left[n-1];for(int i =n-2;i>=0;i--){if(ratings[i]>ratings[i+1]){right[i]=right[i+1]+1;}sum+=Math.max(left[i],right[i]);}return sum;}
}
2.柠檬水找零
题目链接:860. 柠檬水找零 - 力扣(LeetCode)
题面:
基本分析:优先使用掉大面值的钱
代码:
class Solution {public boolean lemonadeChange(int[] bills) {int n = bills.length;int[] arr = new int[11];for(int c:bills){if(c==5){arr[5]++;}else if(c==10){if(arr[5]==0)return false;arr[5]--;arr[10]++;}else{if(arr[10]>0){arr[10]--;if(arr[5]==0)return false;arr[5]--;}else{if(arr[5]<3)return false;arr[5]-=3;}}}return true;}
}
3.根据身高重建队列
题目链接:406. 根据身高重建队列 - 力扣(LeetCode)
题面:
基本分析:先排高的,矮的进行插队
代码:
class Solution {public int[][] reconstructQueue(int[][] people) {int n = people.length;Arrays.sort(people, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {if(o1[0]==o2[0])return o1[1]-o2[1];return o2[0]-o1[0];}});LinkedList<int[]> list = new LinkedList<>();for (int[] i : people) {list.add(i[1], i);}return list.toArray(new int[list.size()][2]);}
}
后言
上面是贪心算法的部分习题,下一篇会讲解贪心算法的其他相关力扣习题,希望有所帮助,一同进步,共勉!