代码随想录 Day31 - 贪心算法(一)

简介: 代码随想录 Day31 - 贪心算法(一)

理论基础


贪心算法解题步骤,一般分为如下四步:

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解


作业题


455. 分发饼干

package jjn.carl.greedy;
import java.util.Arrays;
import java.util.Scanner;
/**
 * @author Jjn
 * @since 2023/7/29 18:24
 */
public class LeetCode455 {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        for (int i = 0, j = 0; i < g.length && j < s.length; ) {
            if (s[j] >= g[i]) {
                count++;
                i++;
            }
            j++;
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int gCount = scanner.nextInt();
        int sCount = scanner.nextInt();
        int[] g = new int[gCount];
        int[] s = new int[sCount];
        for (int i = 0; i < gCount; i++) {
            g[i] = scanner.nextInt();
        }
        for (int i = 0; i < sCount; i++) {
            s[i] = scanner.nextInt();
        }
        int contentChildren = new LeetCode455().findContentChildren(g, s);
        System.out.println(contentChildren);
    }
}


376. 摆动序列

package jjn.carl.greedy;
import java.util.Scanner;
/**
 * @author Jjn
 * @since 2023/7/29 18:42
 */
public class LeetCode376 {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        //当前差值
        int curDiff = 0;
        //上一个差值
        int preDiff = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            //得到当前差值
            curDiff = nums[i] - nums[i - 1];
            //如果当前差值和上一个差值为一正一负
            //等于0的情况表示初始时的preDiff
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
                count++;
                preDiff = curDiff;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        int[] nums = new int[count];
        for (int i = 0; i < count; i++) {
            nums[i] = scanner.nextInt();
        }
        int maxLength = new LeetCode376().wiggleMaxLength(nums);
        System.out.println(maxLength);
    }
}


53. 最大子数组和

package jjn.carl.greedy;
import yz.LeetCode67_StrConverterNum;
import java.util.Map;
import java.util.Scanner;
/**
 * @author Jjn
 * @since 2023/7/29 19:35
 */
public class LeetCode53 {
    public int maxSubArray(int[] nums) {
        int prefix = 0;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            if (prefix < 0) {
                prefix = 0;
            }
            prefix += num;
            if (prefix >= 0) {
                max = Math.max(prefix, max);
            }
        }
        return max;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        int[] nums = new int[count];
        for (int i = 0; i < count; i++) {
            nums[i] = scanner.nextInt();
        }
        int maxSubArray = new LeetCode53().maxSubArray(nums);
        System.out.println(maxSubArray);
    }
}

目录
相关文章
|
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代码实现)

热门文章

最新文章