当前位置: 首页 > news >正文

LeetCode 2786.访问数组中的位置使分数最大:奇偶分开记录(逻辑还算清晰的题解)

【LetMeFly】2786.访问数组中的位置使分数最大:奇偶分开记录(逻辑还算清晰的题解)

力扣题目链接:https://leetcode.cn/problems/visit-array-positions-to-maximize-score/

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。

一开始 在数组的位置 0 处,你可以按照下述规则访问数组中的其他位置:

  • 如果你当前在位置 i ,那么你可以移动到满足 i < j 的 任意 位置 j 。
  • 对于你访问的位置 i ,你可以获得分数 nums[i] 。
  • 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同,那么你将失去分数 x 。

请你返回你能得到的 最大 得分之和。

注意 ,你一开始的分数为 nums[0] 。

 

示例 1:

输入:nums = [2,3,6,1,9,2], x = 5
输出:13
解释:我们可以按顺序访问数组中的位置:0 -> 2 -> 3 -> 4 。
对应位置的值为 2 ,6 ,1 和 9 。因为 6 和 1 的奇偶性不同,所以下标从 2 -> 3 让你失去 x = 5 分。
总得分为:2 + 6 + 1 + 9 - 5 = 13 。

示例 2:

输入:nums = [2,4,6,8], x = 3
输出:20
解释:数组中的所有元素奇偶性都一样,所以我们可以将每个元素都访问一次,而且不会失去任何分数。
总得分为:2 + 4 + 6 + 8 = 20 。

 

提示:

  • 2 <= nums.length <= 105
  • 1 <= nums[i], x <= 106

解题方法:两个变量分别记录上一个位置是奇数和偶数时的最大值

每个数都大于0,并且奇偶性相同的数之间跳跃没有额外的费用(不用-x)。因此奇偶性相同的数不会间隔地跳

以奇数为例,假设有三个奇数 a a a b b b c c c,则由奇数跳到 c c c的话,一定是从 b b b跳过去的,不可能是从 a a a直接跳到 c c c。因为 a − > c a->c a>c不如 a − > b − > c a->b->c a>b>c

因此,我们只需要使用两个变量 o d d odd odd e v e n even even,分别记录上一个数为奇数或偶数时的分数最大值。遍历整数数组时有如下公式:

  • 若当前元素 t t t为奇数,则从奇数跳过来的话分数为 o d d + t odd+t odd+t,从偶数跳过来的话分数为 e v e n + t − x even+t-x even+tx,因此最大分数为 max ⁡ ( o d d + t , e v e n + t − x ) \max(odd+t, even+t-x) max(odd+t,even+tx)
  • 若当前元素 t t t为偶数,则从奇数跳过来的话分数为 o d d + t − x odd+t-x odd+tx,从偶数跳过来的话分数为 e v e n + t even+t even+t,因此最大分数为 max ⁡ ( o d d + t − x , e v e n + t ) \max(odd+t-x, even+t) max(odd+tx,even+t)

特别的,起点必须为第一个数。假设第一个数为奇数,则偶数的默认值为 − x -x x。这是因为:

第一个数为奇数的话,第一次跳到偶数的时候,实质上必定是由奇数跳过去的。而计算公式中的 e v e n + t even+t even+t是由偶数跳过去的,相当于少扣了 x x x分。

时空复杂度分析

  • 时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))
  • 空间复杂度 O ( 1 ) O(1) O(1)

AC代码

C++
typedef long long ll;
class Solution {
public:ll maxScore(vector<int>& nums, int x) {ll odd = nums[0] % 2 ? 0 : -x, even = nums[0] % 2 ? -x : 0;for (int t : nums) {if (t % 2) {odd = max(odd + t, even + t - x);}else {even = max(odd + t - x, even + t);}}return max(odd, even);}
};
Go
func max(a int64, b int64) int64 {if a > b {return a}return b
}func maxScore(nums []int, x int) int64 {odd, even := int64(0), int64(0)if nums[0] % 2 == 0 {odd = -int64(x)} else {even = -int64(x)}for _, t := range nums {if t % 2 != 0 {odd = max(odd + int64(t), even + int64(t) - int64(x))} else {even =  max(odd + int64(t) - int64(x), even + int64(t))}}return max(odd, even)
}
Java
class Solution {public long maxScore(int[] nums, int x) {long odd = nums[0] % 2 != 0 ? 0 : -x, even = nums[0] % 2 != 0 ? -x : 0;for (int t : nums) {if (t % 2 != 0) {odd = Math.max(odd + t, even + t - x);}else {even = Math.max(odd + t - x, even + t);}}return Math.max(odd, even);}
}
Python
# from typing import Listclass Solution:def maxScore(self, nums: List[int], x: int) -> int:odd, even = 0 if nums[0] % 2 else -x, -x if nums[0] % 2 else 0for t in nums:if t % 2:odd = max(odd + t, even + t - x)else:even = max(odd + t - x, even + t)return max(even, odd)

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

Tisfy:https://letmefly.blog.csdn.net/article/details/139688753

相关文章:

LeetCode 2786.访问数组中的位置使分数最大:奇偶分开记录(逻辑还算清晰的题解)

【LetMeFly】2786.访问数组中的位置使分数最大&#xff1a;奇偶分开记录&#xff08;逻辑还算清晰的题解&#xff09; 力扣题目链接&#xff1a;https://leetcode.cn/problems/visit-array-positions-to-maximize-score/ 给你一个下标从 0 开始的整数数组 nums 和一个正整数 …...

嵌入式仪器模块:音频综测仪和自动化测试软件

• 24 位分辨率 • 192 KHz 采样率 • 支持多种模拟/数字音频信号的输入/输出 应用场景 • 音频信号分析&#xff1a;幅值、频率、占空比、THD、THDN 等指标 • 模拟音频测试&#xff1a;耳机、麦克风、扬声器测试&#xff0c;串扰测试 • 数字音频测试&#xff1a;平板电…...

计算商场折扣 、 判断体重指数 题目

题目 JAVA5 计算商场折扣分析&#xff1a;代码&#xff1a; JAVA6 判断体重指数分析&#xff1a;代码&#xff1a;大佬代码&#xff1a; JAVA5 计算商场折扣 描述 牛牛商场促销活动&#xff1a; 满100全额打9折&#xff1b; 满500全额打8折&#xff1b; 满2000全额打7折&…...

input输入框禁止输入小数点方法

使用blur事件&#xff1a; <el-input v-model"number" type"number" placeholder"请输入" blur"numberBlur" /> 第一种&#xff1a; 使用parseInt转为整数&#xff1a; this.number parseInt(this.number);第二种&#xff…...

使用adb通过wifi连接手机

1&#xff0c;手机打开开发者模式&#xff0c;打开无线调试 2&#xff0c;命令行使用adb命令配对&#xff1a; adb pair 192.168.0.102:40731 输入验证码&#xff1a;422859 3&#xff0c;连接设备&#xff1a; adb connect 192.168.0.102:36995 4&#xff0c;查看连接状态:…...

如何一键拷贝PPT中的所有文字?

有时我们可能需要引用PPT的文字&#xff0c;但一个幻灯片一个幻灯片拷贝很是麻烦&#xff0c;我们想一键拷贝PPT中所有幻灯片中的内容&#xff08;最近我就遇到了这个需求&#xff09;。今天就来讲讲这个一键拷贝的技巧。因为大家可能会遇到同样的问题&#xff0c;所以在此记录…...

Hive的存储格式和压缩算法的特点和选择

1、数据存储格式&#xff1a; ①TEXTFILE HIVE 中默认的存储格式&#xff1b; 一般使用在数据贴源层(ODS 或 STG) &#xff0c;针对需要使用脚本 LOAD 加载数据到 HIVE 数仓表中的情况&#xff1b;需要把表里数据导出或直接可以查看等场景&#xff0c;作为BI供数 易读性…...

C语言中的枚举类型(enum)是如何定义的

在C语言中&#xff0c;枚举类型&#xff08;enum&#xff09;是一种用户定义的数据类型&#xff0c;它允许为整数值指定一个易读的名字。枚举类型通常用于表示固定数量的可能值&#xff0c;例如一周的七天或颜色的集合。 枚举类型的定义使用关键字 enum&#xff0c;后面跟着枚…...

SPI通信协议

一、SPI通信 1、SPI&#xff08;Serial Peripheral Interface&#xff09;是由Motorola公司开发的一种通用数据总线 2、四根通信线&#xff1a;SCK&#xff08;Serial Clock&#xff09;、MOSI&#xff08;Master Output Slave Input&#xff09;、MISO&#xff08;Master In…...

【免费Web系列】大家好 ,今天是Web课程的第二一天点赞收藏关注,持续更新作品 !

这是Web第一天的课程大家可以传送过去学习 http://t.csdnimg.cn/K547r 员工管理 1. 条件分页查询 1.1 概述 在页面原型中&#xff0c;我们可以看到在查询员工信息列表时&#xff0c;既需要根据条件动态查询&#xff0c;还需要对查询的结果进行分页处理。 那要完成这个页面…...

【单片机毕业设计选题24007】-基于STM32和阿里云的家庭健康数据监测系统

系统功能: 本课题设计是基于STM32单片机作为控制主体&#xff0c;通过HX711称重模块&#xff0c;HC-SR04超声波测距模块&#xff0c;红外测温&#xff0c;心率传感器等模块通过I2C或SPI接口与STM32进行通信&#xff0c;并读取传感器输出的身高&#xff0c;体重&#xff0c;心率…...

基于微信公众号开发h5的前端流程

1.首先公众号进行配置&#xff0c;必须要https域名 还有个txt文件&#xff0c;有弹框提示需要下载放在服务器上 前端处理code的代码封装 // 微信公众号授权 export function wxAuthorize(calback) {// 非静默授权&#xff0c;第一次有弹框 这里的回调页面就是放在服务器上微信…...

python操作数据库,django操作数据库

安装驱动 pip install mysqlclient工程同名app下的settings.py DATABASES {default: {ENGINE: django.db.backends.mysql,NAME: test,USER: root,PASSWORD: hirain123,HOST: localhost,PORT: 3306,OPTION; {init_command: SET sql_model"STRICT_TRANS_TABLES",}} …...

React框架资源

React框架资源可以从多个方面获取&#xff0c;包括官方文档、教程、书籍、社区等。以下是一些React框架资源的清晰分点和归纳&#xff1a; 官方文档 新官方文档&#xff1a;React在2023年3月发布了全新的官方文档&#xff0c;位于https://react.dev/​。新文档包含教程、指南…...

【数据结构】初识数据结构之复杂度与链表

【数据结构】初识数据结构之复杂度与链表 &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;C语言学习之路 文章目录 【数据结构】初识数据结构之复杂度与链表前言一.数据结构和算法1.1数据结构1.2算法1.3数据结构和算法的重要性 二.时间与空间…...

word怎么单页横向设置(页码不连续版)

打开word&#xff0c;将光标放在第一页的最后位置。 然后点击布局下的分隔符&#xff0c;选择下一页。 将光标放在第二页的开头&#xff0c;点击布局下的纸张方向&#xff0c;选择横向即可。 效果展示。 PS&#xff1a;如果那一页夹在两页中间&#xff0c;那么在…...

搭建 Tomcat 集群【Nginx 负载均衡】

当我们想要提高后端服务器的并发性能&#xff0c;可以通过分配更多的资源给 Tomcat 服务器&#xff0c;但是这只能提高一部分的性能。因为每台 Tomcat 的服务器是有最大连接数为 200.所以即可拥有无穷无尽的内存&#xff0c;也会因为单台 Tomcat 的原因而无法发挥这些资源的最大…...

深入理解指针(二)

目录 1. 数组名的理解 2. 使用指针访问数组 3. ⼀维数组传参的本质 4. 冒泡排序 5. 二级指针 6. 指针数组 7. 指针数组模拟二维数组 1. 数组名的理解 有下面一段代码: #include <stdio.h> int main() {int arr[10] { 1,2,3,4,5,6,7,8,9,10 };int* p &arr[…...

【Qt 学习笔记】Qt窗口 | 标准对话框 | 文件对话框QFileDialog

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt窗口 | 标准对话框 | 文件对话框QFileDialog 文章编号&#xff1a;Q…...

换卡槽=停机?新手机号使用指南!

刚办理的手机号莫名其妙的就被停用了&#xff1f;这到底是怎么回事&#xff1f;这篇文章快来学习一下吧。 ​ 先说一下&#xff0c;你的手机为什么被停机&#xff1f; 现在运营商对于手机卡的使用有着非常严格的要求&#xff0c;尤其是刚办理的新号码&#xff0c;更是“严上加…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...