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):""…...
从GlobeLand30数据到统计报表:QGIS分区统计+Excel,打造你的地表覆盖分析工作流
从GlobeLand30到专业报表:QGISExcel高效地表覆盖分析全流程 地表覆盖数据是理解区域生态环境、规划土地利用的重要基础。GlobeLand30作为30米分辨率的全球地表覆盖数据集,为研究者提供了高精度的分析素材。但如何将这些数据转化为可操作的见解࿱…...
手把手教你用Cloudflare免费RPC节点开发以太坊应用
从零构建以太坊DApp:Cloudflare免费RPC节点实战指南 当你在深夜调试智能合约时,是否曾被突然失效的RPC节点打断思路?作为以太坊开发者,稳定可靠的节点连接是开发流程中最基础却最容易被忽视的一环。Cloudflare提供的免费以太坊RPC…...
「码动四季·开源同行」go实战案例:如何在 Go 微服务中实现负载均衡?
在上文章中,我们已经介绍了负载均衡的相关概念以及在服务高可用架构中的重要性,也了解了几种主流负载均衡算法的实现。在本文中,我们将在Go微服务实例中具体使用负载均衡技术,并详细说明如何基于服务发现来实现负载均衡的微服务间…...
告别手动更新!用Python+Pandas快速解析通达信tnf文件,构建本地股票代码库
用PythonPandas高效解析通达信TNF文件:打造自动化股票代码库 每次手动更新股票代码库时,那些重复性操作总让我想起学生时代抄写课文的场景——机械、耗时且容易出错。作为量化研究员,我们真正需要的是把时间花在策略优化上,而不是…...
新手必看:在快马平台学习排列组合公式的代码实现
新手必看:在快马平台学习排列组合公式的代码实现 作为一个编程新手,当我第一次接触排列组合公式时,那些数学符号和递归逻辑让我一头雾水。直到在InsCode(快马)平台上找到了带详细注释的示例代码,才真正理解了Cn和An公式的实现原理…...
实战指南:为spring boot项目快速配置最优jdk环境,助力应用高效部署
最近在准备一个Spring Boot项目时,发现JDK环境配置这个看似简单的环节其实藏着不少学问。特别是当项目需要兼顾开发效率和生产环境稳定性时,合理的JDK配置方案就显得尤为重要。今天就来分享下我的实战经验,以及如何利用工具快速搞定这些配置。…...
hadoop+spark+hive基于大数据的食谱分析与个性化推荐系统 美食推荐系统 美食可视化 大数据毕业设计
前言随着互联网技术的快速发展,人们获取信息的方式发生了巨大变化。特别是在食品领域,用户渴望获得更加个性化的推荐服务。大数据分析技术的出现为满足这一需求提供了可能。并据此提供精准的食谱推荐,从而提升用户体验。系统架构设计本项目 采…...
革新性英雄联盟智能辅助解决方案:一站式游戏体验提升工具
革新性英雄联盟智能辅助解决方案:一站式游戏体验提升工具 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 在快节奏的英…...
Phi-3-mini-4k-instruct-gguf实战教程:开箱即用的轻量中文问答部署指南
Phi-3-mini-4k-instruct-gguf实战教程:开箱即用的轻量中文问答部署指南 1. 认识Phi-3-mini-4k-instruct-gguf Phi-3-mini-4k-instruct-gguf是微软Phi-3系列中的轻量级文本生成模型GGUF版本。这个模型特别适合处理中文问答、文本改写、摘要整理以及简短创作等任务。…...
新手零基础入门CAN总线:借助快马AI生成可运行代码理解通信机制
作为一个刚接触嵌入式开发的菜鸟,最近被导师要求学习CAN总线协议。面对手册里密密麻麻的寄存器配置和报文格式说明,我一度怀疑自己是不是选错了专业方向。直到发现了InsCode(快马)平台,用它的AI生成功能快速搭建了一个可运行的CAN通信demo&am…...
