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 (重点)添…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
