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

文章目录

    • 买卖股票的最佳时机 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.mfbz.cn/a/13449.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【设计模式】深入浅出--外观模式

文章目录 前言一、外观模式介绍二、案例场景三、外观模式优缺点四、外观模式应用场景总结 前言 不知道大家有没有比较过自己泡茶和去茶馆喝茶的区别&#xff0c;如果是自己泡茶需要自行准备茶叶、茶具和开水&#xff0c;而去茶馆喝茶&#xff0c;最简单的方式就是跟茶馆服务员…

【UE】暂停游戏界面及功能实现

效果 步骤 1. 首先在项目设置中添加一个暂停的操作映射 2. 新建一个控件蓝图&#xff0c;命名为“PauseMenuWidget” 3. 打开“ThirdPersonCharacter”&#xff0c;添加一个布尔类型变量&#xff0c;命名为“isScreenShow”&#xff0c;用于判断当前玩家是否打开了暂停界面 在…

S7-200 SMART 和 S7-1200PLC进行PROFINET IO通信

从 S7-200 SMART V2.5 版本开始,S7-200 SMART 开始支持做 PROFINET IO 通信的智能设备。因此,两个 S7-200 SMART 之间可以进行 PROFINET IO 通信,一个CPU 作PROFINET IO 控制器,一个 CPU 作 PROFINET 通信的设备。组态的时候有两种方法,一种是通过硬件目录组态另外一种是通…

原理+配置+实战,Canal一套带走

前几天在网上冲浪的时候发现了一个比较成熟的开源中间件——Canal。在了解了它的工作原理和使用场景后&#xff0c;顿时产生了浓厚的兴趣。今天&#xff0c;就让我们跟随阿Q的脚步&#xff0c;一起来揭开它神秘的面纱吧。 简介 canal 翻译为管道&#xff0c;主要用途是基于 M…

EEG源定位

导读 自从脑电图(EEG)被发现以来&#xff0c;人们希望EEG能提供一个了解大脑的窗口&#xff0c;研究人员一直试图用EEG无创定位大脑中产生头皮电位的神经元活动。20世纪50年代的早期探索使用电场理论从头皮电位分布推断大脑中电流偶极子的位置和方向&#xff0c;引发了大量定量…

2023美赛春季赛Z题模型代码

已经完成模型代码&#xff0c;仅供大家参考&#xff0c;需要更多请看文末 一、问题分析 首先需要收集与奥运会举办城市/国家相关的历史数据。这需要涉及诸如经济、土地利用、人类满意度&#xff08;包括运动员和观众&#xff09;、旅行、基础设施建设、环境影响等多个方面。数…

日常项目技术方案脉络

开篇引砖 软件在其生命周期中&#xff0c;当其进入稳定期后&#xff0c;大部分时间都处于迭代更新维护阶段。在这漫长的三年甚至五年的存活期内&#xff0c;我们需要面对林林种种大大小小的需求。今天我们就聊聊在这段期间&#xff0c;如何快速产出一份合格的技术方案。 方案给…

Banana Pi BPI-Centi-S3 使用MicroPython编程显示JPG图片

BPI-Centi-S3是我们新推出的一款板载1.9英寸彩屏的小尺寸ESP32-S3开发板&#xff01; BPI-Centi-S3 banana-pi wiki BPI-Centi-S3 bpi-steam wiki 1 关键特性 ESP32-S3&#xff0c;Xtensa 32 bit LX72M PSRAM , 8M FLASH2.4G WIFI &#xff0c;Bluetooth 5 &#xff0c;Blue…

基于鲸鱼算法的极限学习机(ELM)回归预测-附代码

基于鲸鱼算法的极限学习机(ELM)回归预测 文章目录 基于鲸鱼算法的极限学习机(ELM)回归预测1.极限学习机原理概述2.ELM学习算法3.回归问题数据处理4.基于鲸鱼算法优化的ELM5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;本文利用鲸鱼算法对极限学习机进行优化&#xff0c;并…

微服务学习之面试知识相关总结(Nacos、MQ)

文章目录 壹 微服务Nacos1.1 SpringCloud常见组件1.2 Nacos的服务注册表结构1.3 Nacos如何支撑内部数十万服务注册压力1.4 Nacos避免并发读写冲突问1.5 Nacos与Eureka的区别1.6 Sentinel的限流与Gateway的限流的差别1.7 Sentinel的线程隔离与Hystix的线程隔离的差别 贰 MQ知识2…

7款神仙级非常漂亮的 Linux 操作系统UI,你都用过吗

Linux 的发行版有很多&#xff0c;这里罗列7个漂亮的 Linux 发行版&#xff0c;可以说是Linux操作系统界的颜值担当了。 1、elementary OS 网站&#xff1a;https://elementaryos.cn elementary OS操作系统是最漂亮的Linux发行版之一。它基于macOS外观&#xff0c;同时为Linu…

C# 特性(Attribute)

一、特性&#xff08;Attribute&#xff09;定义 特性&#xff08;Attribute&#xff09;是用于在运行时传递程序中各种元素&#xff08;比如类、方法、结构、枚举、组件等&#xff09;的行为信息的声明性标签。您可以通过使用特性向程序添加声明性信息。 特性使用中括号…

AI智能课程第一讲:chatgpt介绍

AI应用现状 用AI艺术创作 一个小女孩打折手电筒在侏罗世纪公园找恐龙。 AI用于医疗行业 AI辅助驾驶 AI广告投放上的应用 什么是chatgpt&#xff1f; chatgpt相关技术的发展 为什么用chatgpt写代码会特别的快呢&#xff1f; 因为它集成了GitHub上所有开发者的库公用资源&…

供需两端催化口腔医疗服务市场增长 未来将呈现线上化、智能化、品质化三大趋势

一、口腔医疗服务行业概述 口腔由唇、颊、舌、腭、涎腺、牙和颌骨等部分组成。口腔疾病种类繁多&#xff0c;伴随人全生命周期&#xff0c;常见疾病有龋病、牙周疾病、牙髓病、根尖周病、牙齿缺损、错颌畸形等&#xff0c;多数口腔疾病的发病率高&#xff0c;诊疗需求大。除此…

原型设计工具即时设计、Axure、Figma、Sketch,哪个更好用?

在线网页原型图设计软件的使用与桌面端相比具备优势&#xff0c;因为在线网页原型图设计软件的使用全程不需要安装&#xff0c;而且在线网页原型图设计软件也没有任何地点上的限制&#xff0c;更主要的是在线网页原型图设计软件在操作系统上也没有限制&#xff0c;不论是现在使…

GPT模型支持下的Python-GEE遥感云大数据分析、管理与可视化技术应用

随着航空、航天、近地空间等多个遥感平台的不断发展&#xff0c;近年来遥感技术突飞猛进。由此&#xff0c;遥感数据的空间、时间、光谱分辨率不断提高&#xff0c;数据量也大幅增长&#xff0c;使其越来越具有大数据特征。对于相关研究而言&#xff0c;遥感大数据的出现为其提…

服务型企业如何使用飞项实现项目化管理?

服务型企业的业务模式一般都是按项目来运作的&#xff0c;其业务分为售前&#xff0c;售中和售后三个阶段&#xff0c;分别由不同部门和人员对客户进行个性化服务。在这个过程中需要对人、流程和知识的高效统筹管理&#xff0c;即项目的整体管理&#xff0c;因此存在着不小的挑…

git lfs简易使用教程

参考资料&#xff1a; https://zzz.buzz/zh/2016/04/19/the-guide-to-git-lfs/ 这篇随笔简单记录一下git lfs的使用教程&#xff0c;只记录最为常用的部分&#xff0c;并阐述原理&#xff0c;方便后面查阅。 首先说明一下git lfs的原理&#xff0c;看名称&#xff1a;git lfs。…

算法:(力扣)(牛客)打印螺旋矩阵题

手撕螺旋矩阵 题目思路解题 题目 描述&#xff1a;给定一个m x n大小的矩阵&#xff08;m行&#xff0c;n列&#xff09;&#xff0c;按螺旋的顺序返回矩阵中的所有元素。数据范围&#xff1a;0 \le n,m \le 100≤n,m≤10&#xff0c;矩阵中任意元素都满足 |val| \le 100∣val…

如何优化语音交友app开发的搜索和匹配算法

语音交友app开发的挑战 在当今社交媒体行业中&#xff0c;语音交友app开发已经成为一个热门的领域。越来越多的人开始使用语音交友app来寻找新的朋友&#xff0c;这也为开发者们带来了许多机会。然而&#xff0c;这个领域也面临着一些挑战。其中一个最大的挑战是如何优化搜索和…
最新文章