【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详解】心算挑战: 一题搞懂涉及奇偶数问题的 “万金油” 思路(思路详解)
前记: 做了几日的leetcode每日一题,几乎全是十分钟结束战斗的【中等】题,今日杀出来个【简单】题,反倒开始难以想出很清楚的解题思路,反复调试修改才将题目逐渐考虑全面,看到了原本思路的漏洞,…...
【资料集】数据库设计说明书(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 是一种广泛使用的开源关系型数据库管理系统,其强大的查询语言为用户提供了丰富的数据处理能力。掌握 MySQL 的常用查询语句对于数据库管理和数据分析至关重要。本文将介绍一些 MySQL 中的常用查询语句,并提供实际的示例。 基础查询 1. 选择…...
hive的内部表(MANAGED_TABLE)和外部表(EXTERNAL_TABLE)的区别
1.hive的表类型分为外部表和内部表 内部表和外部表的主要区别在于数据的存储方式。 外部表:外部表的存储在hdfs中,是我们指定的文件目录,当我们删除数据或者删除分区的时候不会将元数据删除,数据还会在hdfs目录中,我们…...
【AutoSar网络管理】验证ecu能够从RepeatMessage状态切换到ReadySleep
本专栏将为您提供: Autosar网络管理介绍,包括:状态迁移、状态行为、状态表现、切换条件、时间参数、消息类型等。DUT模拟节点介绍,包括:设计思路、代码展示、编写须知等。测试用例介绍,包括:测试内容、测试步骤、期望结果等。测试脚本介绍,包括:编写思路、代码展示、脚…...
js逻辑或(||)和且()
重点: JavaScript 中的逻辑运算符按照布尔逻辑进行计算,并且返回值是操作数本身 || ||:逻辑或,只要有一个表达式为真(truthy),整个表达式就为真 逻辑或 (||) 的行为: ||运算符可以用来连接两个…...
ElasticSearch入门(六)SpringBoot2
private String author; Field(name “word_count”, type FieldType.Integer) private Integer wordCount; /** Jackson日期时间序列化问题: Cannot deserialize value of type java.time.LocalDateTime from String “2020-06-04 15:07:54”: Failed to des…...
vue项目Nginx部署启动
1.vue打包 (1)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代码 构建项目,初始代码运行就会报错。我使用的是Android Studio Giraffe(Adroid-studio-2022.3.1.18-windows)。我在网上找的解决办法是删除重复的类,但这操作起来真的太麻烦了。 这是全部报错代码: Dupli…...
filebeat
1、作用 1、可以在本机收集日志2、也可以远程收集日志3、轻量级的日志收集系统,可以在非java环境运行。logstash是在jmv环境中运行,资源消耗很大,启动一个logstash要消耗500M左右的内存,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:一种用隐式神经场无条件生成建模的新方法。 HyperDiffusion直接对MLP权重进行操作,并生成新的神经隐式场。 HyperDiffusion是与维度无关的生成模型。可以对不同维度的数据用相同的训练方法来合成高保真示例。 局限性…...
分治思想 排序数组
题目 这是一道经典的关于分治思想的算法题,适合刚接触分治的小白。 . - 力扣(LeetCode) 思路 采用递归分治的思想,也就是快速排序的模拟,这里先确定每趟递归的作用: 在一个规定的区间内,随机…...
通用前端分页插件
/*** >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>* 分页组件* >>>>>>>>>>>>>>>>>>>…...
jEasyUI 扩展编辑器
jEasyUI 扩展编辑器 jEasyUI 是一个基于 jQuery 的前端框架,它提供了一系列的组件,用于快速构建交互式的网页界面。这些组件包括布局、窗口、数据网格等,但有时候,开发者可能需要更多的定制化功能,这时候就需要使用 jEasyUI 的扩展编辑器。 什么是 jEasyUI 扩展编辑器 …...
腾讯课堂停服,付费课程怎么观看!!!
腾讯课堂十月1停服拉,大家的付费课程赶紧保存收获一波啊, 爬虫工程师手拿把掐啦!!!...
C# 桥接模式
栏目总目录 概念 桥接模式(Bridge Pattern)是一种结构型设计模式,用于将抽象部分与具体实现部分分离,使它们可以独立地变化。这种设计模式通过创建一个连接(桥)来将抽象和实现部分分离,从而允许…...
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 首先,使用pip安装Pytest: pip install pytest单元测试 单元测试用于测试单个模块或函数的功能。假设我们有一个简单的Python模块…...
Java面试必看!知己知彼才能百战百胜,如何做好面试前的准备?
随着 Java 这个赛道的不断内卷,这两年,Java 程序员的面试,从原来的常规八股文(有 标准答案)到现在,以项目、场景问题、技术深度思考为主,逐步转变成没有标准答案, 需要大家基于自己的…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
