【4.18】贪心算法入门必刷题

news/2024/4/24 23:54:56/

文章目录

    • 买卖股票的最佳时机 II
    • 跳跃游戏
    • 跳跃游戏 II
    • K 次取反后最大化的数组和

买卖股票的最佳时机 II

  • 122. 买卖股票的最佳时机 II - 力扣(LeetCode)

    解法一:动态规划

    class Solution {public int maxProfit(int[] prices) {int n = prices.length;int [][] dp = new int [n][2];dp[0][0] = 0;dp[0][1] = - prices[0];for(int i = 1 ; i < n ; i ++){//第i天不持有,第i - 1天持有,今天刚卖出去 ,或者第i - 1天就不持有dp[i][0] = Math.max(dp[i - 1][1] + prices[i] , dp[i - 1][0]);//第i天持有,今天才持有 / 之前就持有dp[i][1] = Math.max(dp[i - 1][1] , dp[i - 1][0] - prices[i]);}return dp[n - 1][0];}
    }
    

    解法二:贪心算法

    假如第0天买入,第3天卖出,那么利润为:prices[3] - prices[0]。

    相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

    此时就是把利润分解为每天为单位的维度,而不是从0天到第3天整体去考虑!

    那么根据prices可以得到每天的利润序列:(prices[i] - prices[i - 1])…(prices[1] - prices[0])。

    所以可以使用贪心算法,局部最优就是每天都是正利润,这样就可以获得全局最优!

    class Solution {public int maxProfit(int[] prices) {int result = 0;for(int i = 1 ; i < prices.length ; i ++){int path = prices[i] - prices[i - 1];if( path > 0){result += path;}}return result;}
    }
    

跳跃游戏

  • 55. 跳跃游戏 - 力扣(LeetCode)

    随着对nums的遍历更新覆盖范围,遍历范围也随着覆盖范围的更新而更新。

    class Solution {//最优子问题:在符合条件的范围内,每次跳到数字最大的下标上。public boolean canJump(int[] nums) {int cover = 0;for(int i = 0 ; i <= cover ; i ++){cover = Math.max(i + nums[i] , cover);if(cover >= nums.length - 1){return true;}}return false;}
    }
    

跳跃游戏 II

  • 45. 跳跃游戏 II - 力扣(LeetCode)

    跳跃问题找的是覆盖距离,最远覆盖距离是当前走到的距离 + 当前下标的覆盖距离。

    所以最远覆盖距离都是从0开始算的。而i也是从0开始找的,如果碰到了最远的距离,说明不能继续往前走了,此时就要比较这个最远覆盖距离是否已经超过了界限。

    class Solution {public int jump(int[] nums) {//当前可以覆盖的最远距离的下标。int maxCover = 0;//下一个可以覆盖的最远距离下标。int next_maxCover = 0;//记录最大步数。int ans = 0;for(int i = 0 ; i < nums.length ; i ++){next_maxCover = Math.max(i + nums[i] , next_maxCover); //找到最远覆盖距离下标//遇到当前最远覆盖距离下标if(i == maxCover){//当前不是终点if(maxCover < nums.length - 1){ans ++;maxCover = next_maxCover;}else break;}}return ans;}
    }
    

K 次取反后最大化的数组和

  • 1005. K 次取反后最大化的数组和 - 力扣(LeetCode)

    解法一:

    class Solution {public int largestSumAfterKNegations(int[] nums, int k) {//局部最优:将绝对值从大到小排序,之后从头开始反转,如果是负数Arrays.sort(nums);while(k > 0){nums[0] = - nums[0];Arrays.sort(nums);k --;}int sum = 0;for(int i : nums){sum += i;}return sum;}
    }
    

    解法二:

    局部最优处理:对数组排序,遇到负数,就反转。如果下一个还是负数,就继续反转。否则遇到正数就正常反转。

    class Solution {public int largestSumAfterKNegations(int[] nums, int k) {//局部最优:将绝对值从大到小排序,之后从头开始反转,如果是负数Arrays.sort(nums);int idx = 0;for(int i = 0 ; i < k ; i ++){//nums[idx]是负数if(idx < nums.length - 1 && nums[idx] < 0){nums[idx] = - nums[idx];//如果下一个还是负数,idx ++,往下反转if(nums[idx] >= Math.abs(nums[idx + 1])) idx ++;continue;}nums[idx] = - nums[idx];}int sum = 0;for(int i : nums){sum += i;}return sum;}
    }
    

http://www.ppmy.cn/news/48488.html

相关文章

LEAP模型应用于工业、交通、建筑、电力、煤炭、炼油、经济、林业等各领域碳排放预测及建模分析

查看原文>>>LEAP软件&#xff08;使用说明LEAP的模拟练习碳排放相关模板&#xff09;IPCC收录的各种燃料CO2排放系数 目录 第一章 &#xff1a;LEAP建模理论基础 第二章&#xff1a;基于LEAP模型的能源需求预测模型构建 第三章&#xff1a;基于LEAP模型的能源供应…

【Paper Note】Swin Transformer: Hierarchical ViT using Shifted Windows

Swin Transformer: Hierarchical ViT using Shifted Windows 概述核心思想整体结构名词解释与vit区别 模型处理过程概括Patch EmbeddingBasicLayerPatch MergingSwin Transform BlockWindow AttentionShifted Window Attention小结 模型使用及代码模型使用环境配置SwinT 代码Pa…

Maven打包跳过测试的5种方式

Maven打包跳过测试的5种方式 1、命令行方式跳过测试 我们可以通过使用命令将项目打包&#xff0c;添加跳过测试的命令就可以了&#xff0c;可以用两种命令来跳过测试&#xff1a; -DskipTeststrue mvn package -DskipTeststrue-DskipTeststrue&#xff0c;不执行测试用例&a…

数据库实验 | 第2关:建立和调用存储过程(带输出参数)

任务描述 本关任务&#xff1a; 销售数据库有工作人员、销售单数据表 工作人员gzry数据表有雇员号gyh、姓名gyxm、出生日期csrq、学历xl、工资gz、部门bm、电话dh字段 销售单xsd数据表有销售单号xsdh、会员号hyh、雇员号gyh、销售日期xsrq、应付款yfk、实际付款sjfk字段 任…

Android11.0 原生系统SystemUI下拉状态栏和通知栏视图之锁屏通知布局

1.前言 在11.0的系统rom定制化开发中,对于系统原生systemui的锁屏界面的功能也是非常重要的,所以在锁屏页面布局中,也是有通知栏布局的,所以接下来对于息屏亮屏 通知栏布局的相关流程分析,看下亮屏后锁屏页面做了哪些功能 2.原生系统SystemUI下拉状态栏和通知栏视图之锁…

13.接口,包

七&#xff0e;接口 1.代码 package 第四章; import java.util.* ;//导入使用包 interface Birth { //声明接口 int agetoyear(int a); } class Person implements Birth{//实现接口&#xff0c;类&#xff0c;先声明&#xff0c;在实现 protected String name; pro…

SHELL中for循环和IF判断的使用

1。编写脚本for1.sh,使用for循环创建20账户&#xff0c;账户名前缀由用户从键盘输入&#xff0c;账户初始密码由用户输入&#xff0c;例如: test1、test2、test3、.....、 test10 分析 首先循环创建账户则需要使用for循环&#xff0c;但是创建的用户当中可能会有已经存在的账…

Linux基础—网络设置

Linux基础—网络设置 一、查看网络配置1.查看网络接口信息 ifconfig2.查看主机名称 hostname3.查看路由表条目 route4.查看网络连接情况 netstat5.获取socket统计信息 ss 二、测试网络连接1.测试网络连接 ping2.跟踪数据包 traceroute3.域名解析 nslookup 三、使用网络配置命令…

经验分享:如何有效应对Facebook广告数据波动问题?

Facebook广告作为一种重要的数字营销工具&#xff0c;可以帮助企业和品牌快速获得目标受众的关注和转化。然而&#xff0c;由于广告投放过程的不稳定性&#xff0c;Facebook广告数据波动问题也经常出现。 对于广告主而言&#xff0c;如何应对Facebook广告数据波动问题&#xf…

一文搞懂前台,后台,中台,前端,后端,管理端,业务端,技术中台,业务中台,数据中台,物联网中台到底是什么?

1. 前台/前端 前台 (Frontend)&#xff1a;是指用户直接面对的系统界面部分&#xff0c;包括用户界面设计、页面交互逻辑、数据呈现和用户操作等&#xff0c;主要职责是与用户打交道&#xff0c;用友好的交互方式把闭门造车的后台功能暴露出来。 前端 (Frontend)&#xff1a;…

U-Boot 初次编译

1.在 Ubuntu 中创建存放 uboot 的目录 &#xff0c;比如我的是/home/hsj/linux/IMX6ULL/uboot,然后在此目录 下新建一个名为“alientek_uboot”的文件夹用于存放 uboot 源码。alientek_uboot 文件夹创建成功以后使用 FileZilla 软件将正点原子提供的 uboot 源码拷贝到此目录中.…

优思学院|六西格玛常见问题有哪些?

要实现高质量、高效率和高客户满意度的目标&#xff0c;许多企业采用了六西格玛方法。然而&#xff0c;在实施过程中&#xff0c;往往会遇到各种各样的问题。优思学院会在这里探讨一下几个六西格玛常见问题&#xff0c;并提供解决方案&#xff0c;以帮助企业成功实施六西格玛方…

day33—编程题

文章目录 1.第一题1.1题目1.2思路1.3解题 2.第二题2.1题目2.2思路2.3解题 1.第一题 1.1题目 描述&#xff1a; NowCoder开了一家早餐店&#xff0c;这家店的客人都有个奇怪的癖好&#xff1a;他们只要来这家店吃过一次早餐&#xff0c;就会每天都过来&#xff1b;并且&#x…

核心业务7:放款实现

核心业务7:放款实现 1.放款实现流程 -------------------未完成生成借款人还款计划和投资人回款计划-------------- 2.数据库表 3.前端流程 4.汇付宝流程 5.尚融宝后端流程 -------------------未完成生成借款人还款计划和投资人回款计划-------------- -------------…

二十分钟深入详解<二叉搜索树>!!!

目录 前文 一&#xff0c;什么是二叉搜索树&#xff1f; 1.1 二叉搜索树的概念 二&#xff0c; 二叉搜索树的常用操作及其实现 2.1 查找 2.2 插入 2.3 删除 三&#xff0c;二叉搜索树的应用 3.1 K模型 3.2 KV模型 四&#xff0c;二叉搜索树的性能分析 五&#xff0c;…

【设计模式】Java 的三种代理模式

文章目录 一、前言二、正文1、静态代理2、动态代理3、Cglib代理Spring中AOP使用代理 三、总结 一、前言 代理(Proxy)模式是一种结构型设计模式&#xff0c;提供了对目标对象另外的访问方式&#xff1b;即通过代理对象访问目标对象。 这样做的好处是&#xff1a;可以在目标对…

更全面的对比GPT4和Claude对MLIR的掌握能力

本文构造了20个MLIR基础概念的问题以及使用OneFlow IR转换为Tosa IR的5个代码段来评测GPT4和Claude对于MLIR的掌握能力&#xff0c;我的结论是对于基础概念的理解Claude整体上和GPT4持平&#xff0c;而在阅读相关代码片段时Claude表现出了比GPT4更强一点的理解能力。 0x0. 前言…

vue2使用sync修饰符父子组件的值双向绑定

1、使用场景 当我需要对一个 prop 进行“双向绑定的时候&#xff0c;通常用在封装弹窗组件的时候来进行使用&#xff0c;当然也会有其他的使用场景&#xff0c;只要涉及到父子组件之间需要传参的都可以使用&#xff0c;尽量不要使用watch监听来进行修改值&#xff0c;也不要尝试…

如何给厂区做导航地图?智能工厂导航地图解决方案公司

如何给厂区做导航地图&#xff1f;在智慧园区中&#xff0c;基于园区的电子地图地图使用的重要性越来越凸显。但目前在园区信息化应用形式中&#xff0c;广泛缺乏专业电子地图的使用&#xff0c;主要原因是&#xff1a;一是地图系统(GIS)实现繁复&#xff0c;与其他展会业务系统…

大数据实战 --- 美团外卖平台数据分析

目录 开发环境 数据描述 功能需求 数据准备 数据分析 RDD操作 Spark SQL操作 创建Hbase数据表 创建外部表 统计查询 开发环境 HadoopHiveSparkHBase 启动Hadoop&#xff1a;start-all.sh 启动zookeeper&#xff1a;zkServer.sh start 启动Hive&#xff1a; nohup …