LeetCode.1686. 石子游戏 VI
题目
题目链接
分析
本题采取贪心的策略
我们先假设只有两个石头a,b,
对于 Alice 价值分别为 a1,a2,
对于 Bob 价值而言价值分别是 b1,b2
- 第一种方案是 Alice取第一个,Bob 取第二个,Alice与Bob的价值差是 c1 = a1 - b1;
- 第一种方案是 Alice取第二个,Bob 取第一个,Alice与Bob的价值差是 c1 = a2 - b2;
那么这两种方案对于 Alice来说哪一种更优呢??
取决于两种方案的价值差,记 c = c1 - c2 = (a1 - b2) - (a2 - b1) = (a1 + b1) - (a2 + b2);
如果 c > 0,那么方案一更优,如果 c == 0,则两种方案一样,如果 c < 0,则方案二更优。
那么比较两个方案的优劣其实就是比较 a1+b1 与 a2+b2 的优劣,也就是比较每个下标i的a[i]+b[i]的优劣。
所以贪心的策略:将两组石头的价值合并,每次取价值最大的那一组。
总结以上:先将两个数组的价值合并,并用下标去标记,对价值进行排序,
Alice取偶数下标,Bob取奇数下标,最后比较Alice和Bob的价值总和。
代码
class Solution {public int stoneGameVI(int[] aliceValues, int[] bobValues) {int n = aliceValues.length;Integer[] ids = new Integer[n];for (int i = 0; i < n; ++i) ids[i] = i;// 两个数组价值之和按照 大->小 排序,ids 记录下标// 例如: aliceValues = {1, 2, 3}; bobValues = {3, 1, 3};// 经过下面的代码:ids = {2,0,1}Arrays.sort(ids, (a, b) -> {int val1 = aliceValues[a] + bobValues[a];int val2 = aliceValues[b] + bobValues[b];return val2 - val1;});// Alice 价值总和int alisCount = 0;// Bob 价值总和int bobCount = 0;for(int i =0;i < n;i ++) {// 偶数下标,Alice取值if(i % 2 == 0) {alisCount += aliceValues[ids[i]];}else {// 奇数下标,Bob取值bobCount += bobValues[ids[i]];}}if(alisCount - bobCount > 0) {return 1;}else if(alisCount == bobCount) {return 0;}else {return -1;}}
}

相关文章:
LeetCode.1686. 石子游戏 VI
题目 题目链接 分析 本题采取贪心的策略 我们先假设只有两个石头a,b, 对于 Alice 价值分别为 a1,a2, 对于 Bob 价值而言价值分别是 b1,b2 第一种方案是 Alice取第一个,Bob 取第二个,Alice与Bob的价值差是 c1 a1 - b1…...
【硬件产品经理】锂电池充电时间怎么计算?
目录 前言 电池容量 充电器功率 电能转换效率 充电时间计算 作者简介<...
Oracle篇—普通表迁移到分区表(第五篇,总共五篇)
☘️博主介绍☘️: ✨又是一天没白过,我是奈斯,DBA一名✨ ✌✌️擅长Oracle、MySQL、SQLserver、Linux,也在积极的扩展IT方向的其他知识面✌✌️ ❣️❣️❣️大佬们都喜欢静静的看文章,并且也会默默的点赞收藏加关注❣…...
作为开发人的我们,怎么可以不了解这些?
必备技能: 文章结尾处,有资源获取方式 Spring Spring是一个轻量级的Java框架,它可以用于开发各种Java应用程序。Spring提供了丰富的功能,包括IoC容器、AOP、事务管理、Web开发、安全管理等等。Spring的IoC容器可以…...
基于 Echarts 的 Python 图表库:Pyecahrts交互式的日历图和3D柱状图
文章目录 概述一、日历图和柱状图介绍1. 日历图基本概述2. 日历图使用场景3. 柱状图基本概述4. 柱状图使用场景 二、代码实例1. Pyecharts绘制日历图2. Pyecharts绘制2D柱状图3. Pyecharts绘制3D柱状图 总结 概述 本文将引领读者深入了解数据可视化领域中的两个强大工具&#…...
web应用课——(第四讲:中期项目——拳皇)
代码AC Git地址:拳皇——AC Git链接...
Python爬虫http基本原理
Python爬虫逆向系列(更新中):http://t.csdnimg.cn/5gvI3 HTTP 基本原理 在本节中,我们会详细了解 HTTP 的基本原理,了解在浏览器中敲入 URL 到获取网页内容之间发生了什么。了解了这些内容,有助于我们进一…...
iOS17使用safari调试wkwebview
isInspectable配置 之前开发wkwebview的页面的时候一直使用safari调试,毕竟jssdk交互还是要用这个比较方便,虽说用一个脚本插件没问题。不过还是不太方便。 但是这个功能突然到了iOS17之后发现不能用了,还以为又是苹果搞得bug,每…...
二叉树(1)
1 树概念及结构 1.1树的概念 树是一种非线性的数据结构,它是由n(n>0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个特殊的结点&a…...
ArcGIS Pro字段编号相关代码
字段属于SHP文件的重要组成部分,在某些时候需要对字段进行编号,这里为大家介绍一下字段编号相关的代码,希望能对你有所帮助。 数据来源 教程所使用的数据是从水经微图中下载的POI数据,除了POI数据,常见的GIS数据都可…...
AJAX-URL查询参数
定义:浏览器提供给服务器的额外信息,让服务器返回浏览器想要的数据 http://xxxx.com/xxx/xxx?参数名1值1&参数名2值2 axios语法 使用axios提供的params选项 注意:axios在运行时把参数名和值,会拼接到url?参数名值 axios(…...
DBeaver连接ClickHouse,时间少了8小时
文章目录 业务场景问题描述解决办法 业务场景 表字段time,类型为Datetime,插入时间格式为“yyyy-MM-dd HH:mm:ss” 问题描述 插入表中的时间比正常给的时间少了8小时。如,给定时间为: 2024-01-30 14:52:08 在表中显示的时间为&…...
week03day03(文件操作、正则表达式1)
一、文件操作 1.数据持久化(数据本地化) -- 将数据保存在硬盘 程序中的数据默认是保存在运行内存中的,保存在运行内存中的数据在程序运行结束后会自动释放。如果希望在程序结束后,数据仍可以使用&…...
【数据分享】1929-2023年全球站点的逐年最高气温数据(Shp\Excel\免费获取)
气象数据是在各项研究中都经常使用的数据,气象指标包括气温、风速、降水、湿度等指标,其中又以气温指标最为常用!说到气温数据,最详细的气温数据是具体到气象监测站点的气温数据! 之前我们分享过1929-2023年全球气象站…...
数据结构—基础知识:哈夫曼树
文章目录 数据结构—基础知识:哈夫曼树哈夫曼树的基本概念哈夫曼树的构造算法哈夫曼树的构造过程哈夫曼算法的实现算法:构造哈夫曼树 数据结构—基础知识:哈夫曼树 哈夫曼树的基本概念 哈夫曼(Huffman)树又称最优树&…...
计算机网络(第六版)复习提纲24
3 传输控制协议TCP概述 A TCP最主要的特点 1 面向连接的传输层协议 2 每一条TCP连接只能有两个端点,且只能是点对点的 3 提供可靠交付的服务(无差错、不丢失、不重复、不乱序) 4 全双工通信,两端设有发送缓存和接收缓存 5 面向字节…...
[机器学习]TF-IDF算法
一.TF-IDF算法概述 什么是TF-IDF? 词频-逆文档频率(Term Frequency-Inverse Document Frequency,TF-IDF)是一种常用于文本处理的统计方法,可以评估一个单词在一份文档中的重要程度。简单来说就是可以用于文档关键词的提…...
Loadbalancer如何优雅分担服务负荷
欢迎来到我的博客,代码的世界里,每一行都是一个故事 Loadbalancer如何优雅分担服务负荷 前言Loadbalancer基础:数字世界的分配大师1. 分发请求:2. 健康检查:3. 会话保持:4. 可伸缩性:5. 负载均衡…...
计算机网络——链路层(1)
计算机网络——链路层(1) 小程一言专栏链接: [link](http://t.csdnimg.cn/ZUTXU)前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家, [跳转到网站](https://www.captainbed.…...
OpenCV 0 - VS2019配置OpenCV
1 配置好环境变量 根据自己的opencv的安装目录配置 2 新建一个空项目 3 打开 视图->工具栏->属性管理器 4 添加新项目属性表 右键项目名(我这是opencvdemo)添加新项目属性表,如果有配置好了的属性表选添加现有属性表 5 双击选中Debug|x64的刚添加的属性表 6 (重点)添…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
