Day 22:2786. 访问数组中的位置使分数最大
Leetcode 2786. 访问数组中的位置使分数最大
给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。
你 一开始 在数组的位置 0 处,你可以按照下述规则访问数组中的其他位置:
- 如果你当前在位置 i ,那么你可以移动到满足 i < j 的 任意 位置 j 。
- 对于你访问的位置 i ,你可以获得分数 nums[i] 。
- 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同,那么你将失去分数 x 。
请你返回你能得到的 最大 得分之和。
注意 ,你一开始的分数为 nums[0] 。
定义一个数组保存到当前位置且包含当前位置的最大分数,每判断一个元素是,遍历之前的元素进行累加得到最大的分数。
完整代码
class Solution {public long maxScore(int[] nums, int x) {int n = nums.length;long res = nums[0];long[] val = new long[n];val[0] = nums[0];for (int i = 1; i < n; i++) {long max = nums[i];for (int j = 0; j < i; j++) {long t = val[j] + (long) nums[i];if ((nums[j] % 2) != (nums[i] % 2)) t -= x;max = Math.max(max, t);}val[i] = max;res = Math.max(res, val[i]);}return res;}
}
但注意,一开始处于 0 处,所以需要从 0 开始,上述代码是可以不从 0 开始,从自己开始,因此值会偏大。
将当前元素的初始值初始化为 Long.MIN_VALUE
,那么从前面开始就比从自己开始小,因此就能避免从自己开始。
完整代码
class Solution {public long maxScore(int[] nums, int x) {int n = nums.length;long res = nums[0];long[] val = new long[n];val[0] = nums[0];for (int i = 1; i < n; i++) {long max = Long.MIN_VALUE;for (int j = 0; j < i; j++) {long t = val[j] + (long) nums[i];if ((nums[j] % 2) != (nums[i] % 2)) t -= x;max = Math.max(max, t);}val[i] = max;res = Math.max(res, val[i]);}return res;}
}
以上的时间复杂度为 O ( n 2 ) O(n^2) O(n2),因为每次都要遍历前面的结果。
保存前面的最优结果,它的最优结果就两种情况:
- 最优结果的最后一个元素是奇数
- 最优结果的最后一个元素是偶数
完整代码
class Solution {public long maxScore(int[] nums, int x) {int n = nums.length;long res = nums[0];long[] dp = new long[]{Integer.MIN_VALUE, Integer.MIN_VALUE};dp[nums[0] % 2] = nums[0];for (int i = 1; i < n; i++) {int part = nums[i] % 2;long cur = Math.max(dp[part] + nums[i], dp[1 - part] + nums[i] - x);res = Math.max(res, cur);dp[part] = Math.max(dp[part], cur);}return res;}
}
要注意最小值的设置,因为里面存在 -x
,可能会超出最小值的范围,因此可以设置为 -x
或 Integer.MIN_VALUE
。
相关文章:

Day 22:2786. 访问数组中的位置使分数最大
Leetcode 2786. 访问数组中的位置使分数最大 给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。 你 一开始 在数组的位置 0 处,你可以按照下述规则访问数组中的其他位置: 如果你当前在位置 i ,那么你可以移动到满足 i < j 的 任意 …...

理解Es的DSL语法(二):聚合
前一篇已经系统介绍过查询语法,详细可直接看上一篇文章(理解DSL语法(一)),本篇主要介绍DSL中的另一部分:聚合 理解Es中的聚合 虽然Elasticsearch 是一个基于 Lucene 的搜索引擎,但…...

matlab-2-simulink-小白教程-如何绘制电路图进行电路仿真
以上述电路图为例:包含D触发器,时钟CLK,与非门 一、启动simulink的三种方式 方式1 在MATLAB的命令行窗口输入“Simulink”命令。 方式2 在MATLAB主窗口的“主页”选项卡中,单击“SIMULINK”命令组中的Simulink命令按钮。 方式3 从MATLAB…...

CSS从入门到精通——背景样式
目录 背景颜色 任务描述 相关知识 背景色 编程要求 背景图片 任务描述 相关知识 背景图片 设置背景图片 平铺背景图像 任务要求 背景定位与背景关联 任务描述 相关知识 背景定位 背景关联 简写背景 编程要求 背景颜色 任务描述 本关任务:在本关…...

网络编程---Java飞机大战联机
解析服务器端代码 代码是放在app/lib下的src下的main/java,而与之前放在app/src/main下路径不同 Main函数 Main函数里只放着创建MyServer类的一行 public static void main(String args[]){new MyServer();} MyServer构造函数 1.获取本机IP地址 //获取本机IP地…...
一个简单的Oracle函数
CREATE OR REPLACE FUNCTION getyj_zhibiao_value(p_name IN varchar2, p_index IN varchar2) RETURN NUMBER IS -- 定义返回的指标值变量 v_result NUMBER; -- 定义临时变量来存储查询到的指标值 v_index1 VARCHAR2(50); v_index2 VARCHAR2(50); …...

word中根据上级设置下级编号
如上级是3.13.4,如下图 现在想设置下级编码跟随上级逐级显示成3.13.4.1 则在标题功能说明这点击顶部菜单栏的编号按钮,如下图 然后,选择自定义编号-自定义列表-自定义按钮 然后重点是编号格式这一栏,需要手动填写下前三级的编号&…...
【康复学习--LeetCode每日一题】2786. 访问数组中的位置使分数最大
题目描述: 给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。 你一开始 在数组的位置 0 处,你可以按照下述规则访问数组中的其他位置: 如果你当前在位置 i ,那么你可以移动到满足 i < j 的 任意 位置 j 。 对于你访问的…...
bash和sh区别
bash 和 sh 是两种常用的 Unix Shell,它们有一些区别,特别是在功能和兼容性方面。以下是一些主要的区别: 1. **历史与实现**: - sh(Bourne Shell)是第一个 Unix Shell,最初由 Stephen Bourn…...

Git 代码管理规范 !
分支命名 master 分支 master 为主分支,也是用于部署生产环境的分支,需要确保master分支稳定性。master 分支一般由 release 以及 hotfix 分支合并,任何时间都不能直接修改代码。 develop 分支 develop 为开发环境分支,始终保持最…...

MGRS坐标
一 概述 MGRS坐标系统,即军事格网参考系统,是北约(NATO)军事组织使用的标准坐标系统。它基于UTM(通用横向墨卡托)系统,并将每个UTM区域进一步划分为100km100km的小方块。这些方块通过两个相连的字母标识,其…...

FreeRTOS简单内核实现4 临界段
文章目录 0、思考与回答0.1、思考一0.2、思考二0.3、思考三 1、关中断1.1、带返回值1.2、不带返回值 2、开中断3、临界段4、应用 0、思考与回答 0.1、思考一 为什么需要临界段? 有时候我们需要部分代码一旦这开始执行,则不允许任何中断打断࿰…...
Scala的字符串插值
Scala的字符串插值 期待您的关注 ☀Scala学习笔记 目录 Scala的字符串插值 1. s插值器: 2. f插值器: 3. raw插值器: 在Scala中,字符串插值是一种方便的方式,可以在字符串中插入变量或表达式的值。Scala支持三种类型…...

EasyGBS服务器和终端配置
服务器配置 修改easygbs.ini sip/host为本机IP,否则终端能登录,无法视频。 [sip] host192.168.3.190 终端用于登录的用户名和密码 default_usertest default_passwordtest1234 default_guest_userguest default_guest_passwordtest1234终端配置 关…...
git配置2-不同的代码托管平台配置不同的ssh key
1. 配置单个ssh key 1.1. 原理1.2. 生成 ssh key1.3. 代码托管平台配置公钥 2. 配置多个ssh key 2.1. 应用场景2.2. 生成两个不同的key2.3. 修改config文件2.4. 配置代码托管平台2.5. 测试是否成功 1. 配置单个ssh key 1.1. 原理 使用ssh命令行工具(git安装成功…...

【CT】LeetCode手撕—102. 二叉树的层序遍历
目录 题目1-思路2- 实现⭐102. 二叉树的层序遍历——题解思路 3- ACM实现3-1 二叉树构造3-2 整体实现 题目 原题连接:102. 二叉树的层序遍历 1-思路 1.借助队列 Queue ,每次利用 ①while 循环遍历当前层结点,②将当前层结点的下层结点放入 …...
Flink 命令行提交、展示和取消作业
Apache Flink 是一个流处理和批处理的开源框架,用于在分布式环境中执行无边界和有边界的数据流。你可以使用 Flink 的命令行界面(CLI)来提交、展示和取消作业。 提交作业 使用 Flink CLI 提交作业的命令格式通常如下: ./bin/fl…...

STM32单片机选型方法
一.STM32单片机选型方法 1.首先要确定需求: 性能需求:根据应用的复杂度和性能要求,选择合适的CPU性能和主频。 内存需求:确定所需的内存大小,包括RAM和Flash存储空间。 外设需求:根据应用所需的功能&…...
gsap动画库的实践
先看效果: gsap动画库 安装插件:npm install gsap <template><div><h1 style"text-align: left">gsap的用法</h1><h1 style"text-align: left">https://gsap.com/resources/get-started</h1>&…...

LeetCode | 387.字符串中的第一个唯一字符
这道题可以用字典解决,只需要2次遍历字符串,第一次遍历字符串,记录每个字符出现的次数,第二次返回第一个出现次数为1的字符的下标,若找不到则返回-1 class Solution(object):def firstUniqChar(self, s):""…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...

关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...

微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...

R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...

解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...