当前位置：首页 > news >正文

贪心算法习题其二【力扣】【算法学习day.18】

news 2024/11/1 2:31:11

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

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]);}
}