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

【leetcode详解】心算挑战: 一题搞懂涉及奇偶数问题的 “万金油” 思路(思路详解)

前记: 

做了几日的leetcode每日一题,几乎全是十分钟结束战斗的【中等】题,今日杀出来个【简单】题,反倒开始难以想出很清楚的解题思路,反复调试修改才将题目逐渐考虑全面,看到了原本思路的漏洞,于是重新思考,方逐渐明了。

Tips for 涉及奇偶数的问题:

0. 基本思想:奇数 = 奇数 + 偶数; 此外,两数之和均为偶数

1. 由此延伸出:要使和为偶数,奇数要“一对对”地往上加(即至少2个),偶数数量上就任意

2. 基于上述讨论,我们就得到了涉及奇偶数问题的 “万金油” 式思路:转偶数

具体来说:

        要使结果和为偶数,那就先将数的个数(本题中cnt)转为偶数,这样便于后面奇数一对对地往上加,简化讨论(推荐参考下面本题思路详解食用 ~)

        要使结果和为奇数,那就转化为 “一个奇数+偶数” 的问题(从而转化为了和为偶数的问题)

思路详解:

1. 将奇偶数放到两个数组中并分别排序,分开讨论:

int maxmiumScore(vector<int>& cards, int cnt) {vector<int>ji; vector<int>ou;for(int i=0; i<cards.size(); i++){if(cards[i]%2 == 0){ou.push_back(cards[i]);}else{ji.push_back(cards[i]);}}sort(ou.begin(), ou.end());sort(ji.begin(), ji.end());
}

2. 若cnt初始为奇数,则转化为偶数

int k = ou.size()-1;
if(cnt%2 == 1)//若cnt初始为奇数
{cnt--;if(k>=0) re+=ou[k--];//最大偶数一定在被抽的卡里面else return 0;
} //保证当前cnt一定是偶数

 3. 遍历直到cnt=0或出现异常(return 0)

for循环遍历的内层分解:

3.1 特殊情况单独讨论

if(i < 0)//特殊情况单独讨论
{if(k+1 < cnt) return 0;else{re += ou[k]; k--; cnt--; continue;}
}
else if(k < 0)//特殊情况单独讨论
{if(cnt%2 == 1 || cnt > i+1) return 0;else{re+=(ji[i]+ji[i-1]);cnt-=2; i-=2; continue;}
}

3.2 因为抽卡数目(cnt)有限,且奇数牌只能一对一对抽,所以需要判断抽一对奇数牌和抽一对偶数牌谁的增值大

if(i >= 1)//奇数数组至少剩余两个元素
{if(k >= 1)//偶数数组至少剩余两个元素{if(ou[k]+ou[k-1] <= ji[i]+ji[i-1]){re+=(ji[i]+ji[i-1]);cnt-=2; i-=2;}else{re+=(ou[k]+ou[k-1]);cnt-=2; k-=2;}}else{re+=(ji[i]+ji[i-1]);cnt-=2; i-=2;}
}
else if(k >= 1){//奇数数组剩余元素个数<1re+=(ou[k]+ou[k-1]);cnt-=2; k-=2;
}
else{//i,k == 1return 0;
}

 AC代码见下 ~

class Solution {
public:int maxmiumScore(vector<int>& cards, int cnt) {vector<int>ji; vector<int>ou;for(int i=0; i<cards.size(); i++){if(cards[i]%2 == 0){ou.push_back(cards[i]);}else{ji.push_back(cards[i]);}}sort(ou.begin(), ou.end());sort(ji.begin(), ji.end());//保证从小到大排列int re = 0;int i = ji.size()-1;int k = ou.size()-1;if(cnt%2 == 1)//若cnt初始为奇数{cnt--;if(k>=0) re+=ou[k--];else return 0;} //保证当前cnt一定是偶数for(; cnt>0 ; ){if(i < 0)//特殊情况单独讨论{if(k+1 < cnt) return 0;else{re += ou[k]; k--; cnt--; continue;}}else if(k < 0)//特殊情况单独讨论{if(cnt%2 == 1 || cnt > i+1) return 0;else{re+=(ji[i]+ji[i-1]);cnt-=2; i-=2; continue;}}if(i >= 1)//奇数数组至少剩余两个元素{if(k >= 1)//偶数数组至少剩余两个元素{if(ou[k]+ou[k-1] <= ji[i]+ji[i-1]){re+=(ji[i]+ji[i-1]);cnt-=2; i-=2;}else{re+=(ou[k]+ou[k-1]);cnt-=2; k-=2;}}else{re+=(ji[i]+ji[i-1]);cnt-=2; i-=2;}}else if(k >= 1){//奇数数组剩余元素个数<1re+=(ou[k]+ou[k-1]);cnt-=2; k-=2;}else{//i,k == 1return 0;}}return re;}
};

~希望对你有启发~

相关文章:

【leetcode详解】心算挑战: 一题搞懂涉及奇偶数问题的 “万金油” 思路(思路详解)

前记&#xff1a; 做了几日的leetcode每日一题&#xff0c;几乎全是十分钟结束战斗的【中等】题&#xff0c;今日杀出来个【简单】题&#xff0c;反倒开始难以想出很清楚的解题思路&#xff0c;反复调试修改才将题目逐渐考虑全面&#xff0c;看到了原本思路的漏洞&#xff0c…...

【资料集】数据库设计说明书(Word原件提供)

2 数据库环境说明 3 数据库的命名规则 4 逻辑设计 5 物理设计 5.1 表汇总 5.2 表结构设计 6 数据规划 6.1 表空间设计 6.2 数据文件设计 6.3 表、索引分区设计 6.4 优化方法 7 安全性设计 7.1 防止用户直接操作数据库 7.2 用户帐号加密处理 7.3 角色与权限控制 8 数据库管理与维…...

MySQL 常用查询语句精粹

引言 MySQL 是一种广泛使用的开源关系型数据库管理系统&#xff0c;其强大的查询语言为用户提供了丰富的数据处理能力。掌握 MySQL 的常用查询语句对于数据库管理和数据分析至关重要。本文将介绍一些 MySQL 中的常用查询语句&#xff0c;并提供实际的示例。 基础查询 1. 选择…...

hive的内部表(MANAGED_TABLE)和外部表(EXTERNAL_TABLE)的区别

1.hive的表类型分为外部表和内部表 内部表和外部表的主要区别在于数据的存储方式。 外部表&#xff1a;外部表的存储在hdfs中&#xff0c;是我们指定的文件目录&#xff0c;当我们删除数据或者删除分区的时候不会将元数据删除&#xff0c;数据还会在hdfs目录中&#xff0c;我们…...

【AutoSar网络管理】验证ecu能够从RepeatMessage状态切换到ReadySleep

本专栏将为您提供: Autosar网络管理介绍,包括:状态迁移、状态行为、状态表现、切换条件、时间参数、消息类型等。DUT模拟节点介绍,包括:设计思路、代码展示、编写须知等。测试用例介绍,包括:测试内容、测试步骤、期望结果等。测试脚本介绍,包括:编写思路、代码展示、脚…...

js逻辑或(||)和且()

重点&#xff1a; JavaScript 中的逻辑运算符按照布尔逻辑进行计算&#xff0c;并且返回值是操作数本身 || ||:逻辑或&#xff0c;只要有一个表达式为真&#xff08;truthy&#xff09;&#xff0c;整个表达式就为真 逻辑或 (||) 的行为&#xff1a; ||运算符可以用来连接两个…...

ElasticSearch入门(六)SpringBoot2

private String author; Field(name “word_count”, type FieldType.Integer) private Integer wordCount; /** Jackson日期时间序列化问题&#xff1a; Cannot deserialize value of type java.time.LocalDateTime from String “2020-06-04 15:07:54”: Failed to des…...

vue项目Nginx部署启动

1.vue打包 &#xff08;1&#xff09;package.json增加打包命令 "scripts": {"dev": "webpack-dev-server --inline --progress --config build/webpack.dev.conf.js --host 10.16.14.110","start": "npm run dev","un…...

Duplicate class kotlin.collections.jdk8.CollectionsJDK8Kt found in modules。Android studio纯java代码报错

我使用java代码 构建项目&#xff0c;初始代码运行就会报错。我使用的是Android Studio Giraffe&#xff08;Adroid-studio-2022.3.1.18-windows&#xff09;。我在网上找的解决办法是删除重复的类&#xff0c;但这操作起来真的太麻烦了。 这是全部报错代码&#xff1a; Dupli…...

filebeat

1、作用 1、可以在本机收集日志2、也可以远程收集日志3、轻量级的日志收集系统&#xff0c;可以在非java环境运行。logstash是在jmv环境中运行&#xff0c;资源消耗很大&#xff0c;启动一个logstash要消耗500M左右的内存&#xff0c;filebeat只消耗10M左右的内存。收集nginx的…...

matlab y=sin(x) - 2/π*(x)函数绘制

[TOC](matlab ysin(x) - 2/π*(x)函数绘制) ysin(x) - 2/π*(x) clc; clear; close all; x_axis_length 10; y_axis_length 10; % 创建 x 值向量 x_positive linspace(0.1, 10, 1000); % 正半轴上的 x 值 x_negative linspace(-10, -0.1, 1000); % 负半轴上的 x 值% 计算…...

HyperDiffusion阅读

ICCV 2023 创新点 HyperDiffusion&#xff1a;一种用隐式神经场无条件生成建模的新方法。 HyperDiffusion直接对MLP权重进行操作&#xff0c;并生成新的神经隐式场。 HyperDiffusion是与维度无关的生成模型。可以对不同维度的数据用相同的训练方法来合成高保真示例。 局限性…...

分治思想 排序数组

题目 这是一道经典的关于分治思想的算法题&#xff0c;适合刚接触分治的小白。 . - 力扣&#xff08;LeetCode&#xff09; 思路 采用递归分治的思想&#xff0c;也就是快速排序的模拟&#xff0c;这里先确定每趟递归的作用&#xff1a; 在一个规定的区间内&#xff0c;随机…...

通用前端分页插件

/*** >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>* 分页组件* >>>>>>>>>>>>>>>>>>>…...

jEasyUI 扩展编辑器

jEasyUI 扩展编辑器 jEasyUI 是一个基于 jQuery 的前端框架,它提供了一系列的组件,用于快速构建交互式的网页界面。这些组件包括布局、窗口、数据网格等,但有时候,开发者可能需要更多的定制化功能,这时候就需要使用 jEasyUI 的扩展编辑器。 什么是 jEasyUI 扩展编辑器 …...

腾讯课堂停服,付费课程怎么观看!!!

腾讯课堂十月1停服拉&#xff0c;大家的付费课程赶紧保存收获一波啊&#xff0c; 爬虫工程师手拿把掐啦&#xff01;&#xff01;&#xff01;...

C# 桥接模式

栏目总目录 概念 桥接模式&#xff08;Bridge Pattern&#xff09;是一种结构型设计模式&#xff0c;用于将抽象部分与具体实现部分分离&#xff0c;使它们可以独立地变化。这种设计模式通过创建一个连接&#xff08;桥&#xff09;来将抽象和实现部分分离&#xff0c;从而允许…...

GPT-4o mini一手测评:懂得不多,但答得极快

在性能方面,GPT-4o mini 在 MMLU 上的得分为 82%,在 LMSYS 排行榜的聊天方面分数优于 GPT-4。 OpenAI 突然上线新模型 GPT-4o mini, 声称要全面取代 GPT-3.5 Turbo。 在性能方面,GPT-4o mini 在 MMLU 上的得分为 82%,在 LMSYS 排行榜的聊天方面分数优于 GPT-4。 在价格…...

Python面试题:结合Python技术,如何使用Pytest进行单元测试和集成测试

使用Pytest进行单元测试和集成测试是非常常见和有效的方法。下面是如何使用Pytest进行这些测试的详细指南。 安装Pytest 首先&#xff0c;使用pip安装Pytest&#xff1a; pip install pytest单元测试 单元测试用于测试单个模块或函数的功能。假设我们有一个简单的Python模块…...

Java面试必看!知己知彼才能百战百胜,如何做好面试前的准备?

随着 Java 这个赛道的不断内卷&#xff0c;这两年&#xff0c;Java 程序员的面试&#xff0c;从原来的常规八股文&#xff08;有 标准答案&#xff09;到现在&#xff0c;以项目、场景问题、技术深度思考为主&#xff0c;逐步转变成没有标准答案&#xff0c; 需要大家基于自己的…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

Matlab实现任意伪彩色图像可视化显示

Matlab实现任意伪彩色图像可视化显示 1、灰度原始图像2、RGB彩色原始图像 在科研研究中&#xff0c;如何展示好看的实验结果图像非常重要&#xff01;&#xff01;&#xff01; 1、灰度原始图像 灰度图像每个像素点只有一个数值&#xff0c;代表该点的​​亮度&#xff08;或…...

UE5 音效系统

一.音效管理 音乐一般都是WAV,创建一个背景音乐类SoudClass,一个音效类SoundClass。所有的音乐都分为这两个类。再创建一个总音乐类&#xff0c;将上述两个作为它的子类。 接着我们创建一个音乐混合类SoundMix&#xff0c;将上述三个类翻入其中&#xff0c;通过它管理每个音乐…...

【工具教程】多个条形码识别用条码内容对图片重命名,批量PDF条形码识别后用条码内容批量改名,使用教程及注意事项

一、条形码识别改名使用教程 打开软件并选择处理模式&#xff1a;打开软件后&#xff0c;根据要处理的文件类型&#xff0c;选择 “图片识别模式” 或 “PDF 识别模式”。如果是处理包含条形码的 PDF 文件&#xff0c;就选择 “PDF 识别模式”&#xff1b;若是处理图片文件&…...

Shell 解释器​​ bash 和 dash 区别

bash 和 dash 都是 Unix/Linux 系统中的 ​​Shell 解释器​​&#xff0c;但它们在功能、语法和性能上有显著区别。以下是它们的详细对比&#xff1a; ​​1. 基本区别​​ ​​特性​​​​bash (Bourne-Again SHell)​​​​dash (Debian Almquist SHell)​​​​来源​​G…...