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

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...