代码随想录 Day35 - 贪心算法(四)

简介: 代码随想录 Day35 - 贪心算法(四)

860. 柠檬水找零

能否找的开零钱主要看是否有足量的 5 元和 10 元的数量,故存在三种情况:

  • 碰到 5 元的只需要加上;
  • 碰到 10 元的,减掉 5 元,10 元的数量+1;
  • 碰到 20 元的,看此时是否有 10 元的,有的话,10 元及 5 元的次数分别-1,没有的话,则 5 元的数量-3。

每一步在扣减的时候,均需要判断是否有足量的零钱,没有则直接返回 false。

package jjn.carl.greedy;
import java.util.Scanner;
/**
 * @author Jjn
 * @since 2023/8/1 13:25
 */
public class LeetCode860 {
    public boolean lemonadeChange(int[] bills) {
        int fiveCount = 0, tenCount = 0;
        for (int bill : bills) {
            if (bill == 5) {
                fiveCount++;
                continue;
            }
            if (bill == 10) {
                fiveCount--;
                tenCount++;
                if (fiveCount < 0) {
                    return false;
                }
                continue;
            }
            if (bill == 20) {
                if (tenCount > 0) {
                    tenCount--;
                    fiveCount--;
                    if (fiveCount < 0) {
                        return false;
                    }
                    continue;
                }
                fiveCount -= 3;
                if (fiveCount < 0) {
                    return false;
                }
            }
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();
        int[] bills = new int[total];
        for (int i = 0; i < total; i++) {
            bills[i] = scanner.nextInt();
        }
        boolean lemonadeChange = new LeetCode860().lemonadeChange(bills);
        System.out.println(lemonadeChange);
    }
}


406. 根据身高重建队列

package jjn.carl.greedy;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
/**
 * @author Jjn
 * @since 2023/8/1 13:34
 */
public class LeetCode406 {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (first, second) -> {
            if (first[0] == second[0]) {
                return first[1] - second[1];
            }
            return second[0] - first[0];
        });
        List<int[]> list = new ArrayList<>();
        for (int[] p : people) {
            list.add(p[1], p);
        }
        return list.toArray(new int[people.length][]);
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        int[][] people = new int[count][2];
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < 2; j++) {
                people[i][j] = scanner.nextInt();
            }
        }
        int[][] reconstructQueue = new LeetCode406().reconstructQueue(people);
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int[] element : reconstructQueue) {
            stringBuilder.append(Arrays.toString(element));
        }
        stringBuilder.append("]");
        System.out.println(stringBuilder);
    }
}


452. 用最少数量的箭引爆气球

package jjn.carl.greedy;
import java.util.Arrays;
import java.util.Scanner;
/**
 * @author Jjn
 * @since 2023/8/1 16:11
 */
public class LeetCode452 {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (first, second) -> {
            if (first[0] == second[0]) {
                return Integer.compare(first[1], second[1]);
            }
            return Integer.compare(first[0], second[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;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        int[][] points = new int[count][2];
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < 2; j++) {
                points[i][j] = scanner.nextInt();
            }
        }
        int minArrowShots = new LeetCode452().findMinArrowShots(points);
        System.out.println(minArrowShots);
    }
}



目录
相关文章
|
6天前
|
存储 算法 调度
【复现】【遗传算法】考虑储能和可再生能源消纳责任制的售电公司购售电策略(Python代码实现)
【复现】【遗传算法】考虑储能和可再生能源消纳责任制的售电公司购售电策略(Python代码实现)
102 26
|
6天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
9天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
8天前
|
传感器 机器学习/深度学习 算法
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
|
3天前
|
机器学习/深度学习 人工智能 搜索推荐
从零构建短视频推荐系统:双塔算法架构解析与代码实现
短视频推荐看似“读心”,实则依赖双塔推荐系统:用户塔与物品塔分别将行为与内容编码为向量,通过相似度匹配实现精准推送。本文解析其架构原理、技术实现与工程挑战,揭秘抖音等平台如何用AI抓住你的注意力。
101 6
从零构建短视频推荐系统:双塔算法架构解析与代码实现
|
6天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
82 14
|
11天前
|
机器学习/深度学习 传感器 算法
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
|
11天前
|
算法 安全 BI
基于粒子群算法的多码头连续泊位分配优化研究(Matlab代码实现)
基于粒子群算法的多码头连续泊位分配优化研究(Matlab代码实现)
|
6天前
|
机器学习/深度学习 运维 算法
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
|
9天前
|
机器学习/深度学习 运维 算法
【储能选址定容】基于多目标粒子群算法的配电网储能选址定容(Matlab代码实现)
【储能选址定容】基于多目标粒子群算法的配电网储能选址定容(Matlab代码实现)

热门文章

最新文章