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

leetcode刷题day29|贪心算法Part03（ 134. 加油站、135. 分发糖果、860.柠檬水找零、406.根据身高重建队列）

article 2024/9/29 22:25:15

134. 加油站

思路：
暴力解法：for循环适合模拟从头到尾的遍历，while循环适合模拟环形遍历！但是会超出leetcode的时间限制。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for(int i=0;i<gas.length;i++){
            int rest=gas[i]-cost[i];
            int index=(i+1)%gas.length;
            while(rest>0 && index!=i){ 
                rest+=gas[index]-cost[index];
                index=(index+1)%gas.length;
            }
            if(rest>=0 && index==i) return i;
        }
        return -1;
    }
}

贪心算法：计算每个地点的剩余油量，如果剩余油量的累加和小于零，则说明0-i作为起点均不能绕环一周，从i+1开始，重新进行剩余油量的累加。如果剩余油量全部加起来小于0，说明不够一周，返回-1；否则一定存在index使得能够环绕一周。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum=0;
        int totalSum=0;
        int index=0;
        for(int i=0;i<gas.length;i++){
            curSum+=gas[i]-cost[i];
            totalSum+=gas[i]-cost[i];
            if(curSum<0){
                index=i+1;
                curSum=0;
            }
        }
        if(totalSum<0) return -1;
        else return index;
    }
}

135. 分发糖果

思路：设置一个数组来存储分发的糖果量，令0处的糖果数为1，先从0开始遍历右边，如果右边大，则右边的为左边的糖果数加一，否则为1；在从后往前遍历，如果左边的比右边的大，要选择右边的数+1和当前值更大的那个，才能保证两边条件都满足，否则当前糖数不变。
代码如下：

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

860.柠檬水找零

思路：这个题比较简单，直接分情况讨论就好，如果是5直接收下；如果是10，5减去一个；如果是20，先用10元找零，没有10了再考虑用3个5找零（体现贪心：优先使用作用有限的）

代码如下：

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int num5=0;
        int num10=0;
        int num20=0;
        for(int i=0;i<bills.length;i++){
            if(bills[i]==5) num5++;
            else if(bills[i]==10){
                if(num5<=0) return false;
                else{
                    num5--;
                    num10++;
                }
            }else if(bills[i]==20){
                if((num5<=0) ||(num5<=2 && num10<=0)) return false;
                else if(num10>0){
                    num20++;
                    num10--;
                    num5--;
                }else{
                    num20++;
                    num5=num5-3;
                }
            } 
        }
        return true;
    }
}

考虑代码优化，最后判断5和10的数量是否小于零，这个逻辑更清晰。

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;

        for (int i = 0; i < bills.length; i++) {
            if (bills[i] == 5) {
                five++;
            } else if (bills[i] == 10) {
                five--;
                ten++;
            } else if (bills[i] == 20) {
                if (ten > 0) {
                    ten--;
                    five--;
                } else {
                    five -= 3;
                }
            }
            if (five < 0 || ten < 0) return false;
        }
        
        return true;
    }
}

406.根据身高重建队列

思路：首先这道题理解题意就理解了很久，意思是身高为h的人前面有k个人，需要按照身高重新排列来满足k。和糖果分发题目一样，技巧都是确定一边然后贪心另一边，两边一起考虑，就会顾此失彼。如果按照k的大小来排序，得到的结果还是无序的，意义不大，所以按照身高h来排序。
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性

代码如下：

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,(a,b)->{
            if(a[0]==b[0]) return a[1]-b[1];//如果h相同，k按升序排序
            else return b[0]-a[0];
        });
        LinkedList<int[]> queue=new LinkedList<>();
        for(int[] p:people){
            queue.add(p[1],p);
        }
        return queue.toArray(new int[people.length][]);
    }
}