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

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

article 2024/11/4 22:14:28

前言

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

习题

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[]>() {
            @Override
            public 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]);
    }
}