当前位置: 首页 > 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;更是“严上加…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...