代码随想录 Day32 - 贪心算法(二)

简介: 代码随想录 Day32 - 贪心算法(二)

122. 买卖股票的最佳时机 II

只要有利润,就持续叠加,直到没有利润可得。

package jjn.carl.greedy;
import java.util.Scanner;
/**
 * @author Jjn
 * @since 2023/7/29 19:58
 */
public class LeetCode122 {
    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] >= prices[i - 1]) {
                max += prices[i] - prices[i - 1];
            }
        }
        return max;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        int[] prices = new int[count];
        for (int i = 0; i < count; i++) {
            prices[i] = scanner.nextInt();
        }
        int maxProfit = new LeetCode122().maxProfit(prices);
        System.out.println(maxProfit);
    }
}


55. 跳跃游戏

package jjn.carl.greedy;
import java.util.Scanner;
/**
 * @author Jjn
 * @since 2023/7/29 20:07
 */
public class LeetCode55 {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        int coverage = 0;
        for (int i = 0; i <= coverage; i++) {
            coverage = Math.max(i + nums[i], coverage);
            if (coverage >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
    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();
        }
        boolean canJump = new LeetCode55().canJump(nums);
        System.out.println(canJump);
    }
}


45. 跳跃游戏 II

  • 如果某一个作为 起跳点 的格子可以跳跃的距离是 3,那么表示后面 3 个格子都可以作为 起跳点。故可以对每一个能作为 起跳点 的格子都尝试跳一次,把 能跳到最远的距离 不断更新。
  • 如果从这个 起跳点 起跳叫做第 1 次 跳跃,那么从后面 3 个格子起跳 都可以叫做第 2 次 跳跃。
  • 所以,当一次跳跃结束时,从下一个格子开始,到现在 能跳到最远的距离,都是下一次跳跃的起跳点。
  • 对每一次 跳跃 用 for 循环来模拟。
  • 跳完一次之后,更新下一次 起跳点 的范围。
  • 在新的范围内跳,更新 能跳到最远的距离。
  • 记录 跳跃 次数,如果跳到了终点,就得到了结果。
package jjn.carl.greedy;
import java.util.Scanner;
/**
 * @author Jjn
 * @since 2023/7/29 20:20
 */
public class LeetCode45 {
    public int jump(int[] nums) {
        int k = 0;
        //记录跳跃的次数
        int step = 0;
        int end = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            //一定跳得到,因此不存在 k < i
            k = Math.max(k, i + nums[i]);
            //第一次起跳 或 到达跳跃的边界
            if (i == end) {
                //再次起跳
                step++;
                //更新边界
                end = k;
            }
        }
        return step;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();
        int[] nums = new int[total];
        for (int i = 0; i < total; i++) {
            nums[i] = scanner.nextInt();
        }
        int jump = new LeetCode45().jump(nums);
        System.out.println(jump);
    }
}



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

热门文章

最新文章