java算法第32天 | ● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

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

在这里插入图片描述
在这里插入图片描述

本题中理解利润拆分是关键点! 不要整块的去看,而是把整体利润拆为每天的利润。假如第 0 天买入,第 3 天卖出,那么利润为:prices[3] - prices[0]。

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

一旦想到这里了,很自然就会想到贪心了,即:只收集每天的正利润,最后稳稳的就是最大利润了。

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

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)

55. 跳跃游戏

在这里插入图片描述
在这里插入图片描述

本题的思路是不断更新覆盖范围,而不去纠结具体跳了几步。
局部最优:每次取最大的覆盖范围
全局最优:最终能覆盖的最大范围

class Solution {
    public boolean canJump(int[] nums) {
        int cover=0;
        if(nums.length==1) return true;
        for(int i=0;i<=cover;i++){
            cover=Math.max(i+nums[i],cover);
            if(cover>=nums.length-1) return true;//一旦到达终点了,直接return true;
        }
        return false;
    }
}

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)

45.跳跃游戏II

在这里插入图片描述
本题的思路在于,每走一步都取能达到的最远位置。这就需要记录当前步的最远位置和下一步的最远位置,每当达到当前步的最远位置,直接走一步,并且把当前步的最远位置更新成下一步的最远位置,继续寻找下一步的最远位置,知道当前步的最远位置大于等于终点位置。

class Solution {
    public int jump(int[] nums) {
        if(nums.length==1) return 0;
        int nextMax=0;//记录下一步的最远位置
        int cur=0;//记录当前步的最远位置
        int step=0;//记录最终的结果
        for(int i=0;i<nums.length;i++){
            nextMax=Math.max(nextMax,i+nums[i]);
            if(i==cur){
                cur=nextMax;
                step++;//向前走一步
                if(cur>=nums.length-1) break;//如果走的这一步可以到达终点,直接break;
            }
        }
        return step;
    }
}

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/481546.html

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

相关文章

XSS-labs详解

xss-labs下载地址https://github.com/do0dl3/xss-labs 进入靶场点击图片&#xff0c;开始我们的XSS之旅&#xff01; Less-1 查看源码 代码从 URL 的 GET 参数中取得 "name" 的值&#xff0c;然后输出一个居中的标题&#xff0c;内容是 "欢迎用户" 后面…

手撕算法-买卖股票的最佳时机 II(买卖多次)

描述 分析 使用动态规划。dp[i][0] 代表 第i天没有股票的最大利润dp[i][1] 代表 第i天持有股票的最大利润 状态转移方程为&#xff1a;dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]); // 前一天没有股票&#xff0c;和前一天有股票今天卖掉的最大值dp[i][1] max(dp[i-1…

智能财务新选择!Zoho Books入选福布斯榜单,助力中小企业!

放眼全球&#xff0c;中小企业始终是经济发展的重要组成部分。然而&#xff0c;由于中小企业的规模、流程规范和资源等方面受限较多&#xff0c;从而导致其在管理及运营上存在着诸多问题。其中包括财务管理不规范、成本控制不到位、运营效率低下等&#xff0c;这些问题则直接影…

如何在CentOS安装SQL Server数据库并实现无公网IP远程连接内网数据库

文章目录 前言1. 安装sql server2. 局域网测试连接3. 安装cpolar内网穿透4. 将sqlserver映射到公网5. 公网远程连接6.固定连接公网地址7.使用固定公网地址连接 前言 简单几步实现在Linux centos环境下安装部署sql server数据库&#xff0c;并结合cpolar内网穿透工具&#xff0…

基于GD32E230C8T6的数字示波器

基于GD32E230C8T6的数字示波器 文章目录 基于GD32E230C8T6的数字示波器基于GD32E230C8T6的数字示波器实物演示电路原理**模拟前端处理电路**image.png**交直流耦合电路****输入信号衰减电路****信号调理电路****虚断:****虚短:****电压跟随器****反相比例放大器****同相比例放…

深度剖析GNSS高精度定位原理

一、背景 目前室外使用最广泛的定位手段是GNSS定位&#xff0c;常规的GNSS定位精度约5、10米左右&#xff0c;无法满足高精度场景的应用&#xff0c;如何提升GNSS定位性能是亟待解决的问题。本文由浅入深剖析GNSS定位原理并介绍如何实现厘米级高度定位。 二、GNSS定位原理 1、…

MySQL下载安装和本地连接

1、下载MySQL 从MySQL官网下载MySQL Community Server版本&#xff1a; 下载地址&#xff1a;MySQL官网 1、进入官网&#xff0c;点击DOWNLOADS 2、点击MySQL Community(GPL)Downloads 3、点击MySQL Installer for Windows 4、这个会直接跳转到最新的版本 如果想下载以往的…

面试算法-83-不同路径 II

题目 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish”&#xff09;。 现在考虑网格中有障碍物。那么从左上角到…

【进程概念】启动进程 | 查看进程 | 创建进程

目录 启动进程 查看进程 方法1&#xff1a;/proc 方法2&#xff1a;查看脚本 ​方法3&#xff1a;系统调用获取进程标示符❗❗ 终止进程 创建进程&#xff08;主fork) &#x1f642;查看父子进程的pid &#x1f642;进程创建/执行/终止 &#x1f642;多次重新启动进…

java的IO之NIO

NIO是一种同步非阻塞的I/O模型&#xff0c;在Java 1.4中引入了NIO框架&#xff0c;对应java.nio包&#xff0c;提供了channel、selector、buffer等。 NIO中的N可以理解为Non-blocking不在单纯是New&#xff0c;它支持面向缓冲的&#xff0c;基于通道的I/O操作方法。NIO提供了与…

论文阅读之LORA: LOW-RANK ADAPTATION OF LARGE LAN- GUAGE MODELS(2021)

文章目录 论文地址主要内容主要贡献模型图技术细节实验结果 论文地址 LORA: LOW-RANK ADAPTATION OF LARGE LAN- GUAGE MODELS 主要内容 这篇文章的主要内容是介绍了一种名为LoRA&#xff08;Low-Rank Adaptation&#xff09;的技术&#xff0c;这是一种针对大型语言模型进行…

阅读MySQL知识4

一、MySQL数据库主从同步延迟产生的原因 MySQL的主从复制都是单线程的操作&#xff0c;主库对所有DDL和DML产生的日志写进binlog&#xff0c;由于binlog是顺序写&#xff0c;所以效率很高。 Slave的SQL Thread线程将主库的DDL和DML操作事件在slave中重放。DML和DDL的IO操作…

【欧拉函数+快速幂】第十四届蓝桥杯省赛C++ C组 Java A组/研究生组 Python 研究生组《互质数的个数》(C++)

【题目描述】 给定 a,b&#xff0c;求 1≤x< 中有多少个 x 与 互质。 由于答案可能很大&#xff0c;你只需要输出答案对 998244353 取模的结果。 【输入格式】 输入一行包含两个整数分别表示 a,b&#xff0c;用一个空格分隔。 【输出格式】 输出一行包含一个整数表示…

8-深度学习

声明 本文章基于哔哩哔哩付费课程《小白也能听懂的人工智能原理》。仅供学习记录、分享&#xff0c;严禁他用&#xff01;&#xff01;如有侵权&#xff0c;请联系删除 目录 一、知识引入 &#xff08;一&#xff09;深度学习 &#xff08;二&#xff09;Tensorflo…

Java全栈课程之Linux———基本属性

一、看懂文件属性 Linux系统是一种典型的多用户系统&#xff0c;不同的用户处于不同的地位&#xff0c;拥有不同的权限。为了保护系统的安全性&#xff0c;Linux系统对不同的用户访问同一文件&#xff08;包括目录文件&#xff09;的权限做了不同的规定。 在Linux中我们可以使…

深入理解Ubuntu22:探索Linux操作系统的功能与应用

一、linux &#xff08;一&#xff09;、安装 1、电脑可以安装双系统&#xff0c;即在一套硬件上只能同时运行一个操作系统&#xff0c;例&#xff1a;C盘安装win&#xff0c;D盘安装linux。 2、虚拟机 虚拟机需要硬件支持&#xff0c;并需开启VT-x. 如&#xff1a;Virtual…

Ubuntu18.04显示--有线连接未托管

引用: Ubuntu18.04连不网 报"有线连接未托管"_ubuntu20.04以太网未托管-CSDN博客 正文 虚拟机环境配置&#xff1a; VirtaualBox Ubuntu18.04桌面版 问题现象&#xff1a; Ubuntu18.04虚拟机的桌面上提示“有线连接未托管”&#xff0c;虚拟机不能上网&#xf…

使用倒模耳机壳UV树脂胶液制作舞台监听耳返入耳式耳机壳有哪些缺点?

使用倒模耳机壳UV树脂胶液制作舞台监听耳返入耳式耳机壳也存在一些缺点&#xff0c;具体如下&#xff1a; 成本较高&#xff1a;相对于传统的塑料或金属材料&#xff0c;UV树脂胶液的成本较高&#xff0c;需要更多的材料和工艺成本。制作难度较大&#xff1a;由于UV树脂的特殊…

鸿蒙ArkTS实战开发-Native XComponent组件的使用

介绍 本篇Codelab主要介绍如何使用XComponent组件调用NAPI来创建EGL/GLES环境&#xff0c;实现在主页面绘制一个正方形&#xff0c;并可以改变正方形的颜色。本篇CodeLab使用Native C模板创建。 如图所示&#xff0c;点击绘制矩形按钮&#xff0c;XComponent组件绘制区域中渲…

校招岗位大解析

校园招聘岗位需要综合考虑岗位描述、行业背景、公司文化、职业发展路径、技能要求、薪酬福利以及公司口碑等多个方面的因素&#xff0c;全面了解并综合考虑这些因素&#xff0c;才能更好地选择适合自己的岗位&#xff0c;实现个人职业发展目标。 1. 软件/后端/前端开发 软件/…