​LeetCode解法汇总1686. 石子游戏 VI

news/2024/12/4 16:49:01/

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

 GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台


描述:

Alice 和 Bob 轮流玩一个游戏,Alice 先手。

一堆石子里总共有 n 个石子,轮到某个玩家时,他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。

给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。

所有石子都被取完后,得分较高的人为胜者。如果两个玩家得分相同,那么为平局。两位玩家都会采用 最优策略 进行游戏。

请你推断游戏的结果,用如下的方式表示:

  • 如果 Alice 赢,返回 1 。
  • 如果 Bob 赢,返回 -1 。
  • 如果游戏平局,返回 0 。

示例 1:

输入:aliceValues = [1,3], bobValues = [2,1]
输出:1
解释:
如果 Alice 拿石子 1 (下标从 0开始),那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ,得到 2 分。
Alice 获胜。

示例 2:

输入:aliceValues = [1,2], bobValues = [3,1]
输出:0
解释:
Alice 拿石子 0 , Bob 拿石子 1 ,他们得分都为 1 分。
打平。

示例 3:

输入:aliceValues = [2,4,3], bobValues = [1,6,7]
输出:-1
解释:
不管 Alice 怎么操作,Bob 都可以得到比 Alice 更高的得分。
比方说,Alice 拿石子 1 ,Bob 拿石子 2 , Alice 拿石子 0 ,Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。

提示:

  • n == aliceValues.length == bobValues.length
  • 1 <= n <= 105
  • 1 <= aliceValues[i], bobValues[i] <= 100

解题思路:

两者都是聪明的人,则每次选择则一定选择对自己最有利的选择,有利排序如下:

1.某个位置,自己的权重大,对方也大;

2.某个位置,自己的权重大对方小,或者自己的权重小对方大;

3.某个位置,自己的权重和对方权重都小。

所以,总结下来,就可以自己的权重+对方的权重之和作为总权重,然后排序,排在前面的就是最应该被提前选择的。

 

代码:

class Solution1686
{
public:int stoneGameVI(vector<int> &aliceValues, vector<int> &bobValues){vector<pair<int, int>> dp(aliceValues.size());for (int i = 0; i < aliceValues.size(); i++){dp[i] = make_pair(i, abs(aliceValues[i] + bobValues[i]));}sort(dp.begin(), dp.end(), [](const pair<int, int> &a, const pair<int, int> &b){ return a.second > b.second; });int aScore = 0;int bScore = 0;for (int i = 0; i < dp.size(); i++){if (i % 2 == 0){aScore += aliceValues[dp[i].first];}else{bScore += bobValues[dp[i].first];}}if (aScore > bScore){return 1;}if (aScore < bScore){return -1;}return 0;}
};


http://www.ppmy.cn/news/1340269.html

相关文章

python绘图指南—Bokeh库从基础到高级打造交互式数据可视【第51篇—python:Bokeh库】

文章目录 Bokeh库深度解析&#xff1a;从基础到高级&#xff0c;打造交互式数据可视化安装Bokeh库Bokeh绘图基础基础图形绘制完善图形 实例演示案例&#xff1a;股票走势图 Bokeh库高级功能探索1. 工具栏和交互性2. 高级图形元素3. 数据链接和动态更新 Bokeh库与其他库的整合1.…

麒麟系统—— openKylin 安装 Maven

麒麟系统—— openKylin 安装 Maven 一、准备工作1. 确保麒麟系统 openKylin 已经安装完毕。2. 确保 java 已经安装完毕 二、下载Maven三、解压 Maven 与环境配置解压配置环境变量验证 最终&#xff1a;介绍配置的其他参数使用 本文将分享如何在麒麟操作系统 openKylin 上安装…

使用 PyTorch 构建 NLP 聊天机器人

一、说明 聊天机器人提供自动对话&#xff0c;可以帮助用户完成任务或寻求信息。随着深度学习的最新进展&#xff0c;聊天机器人正变得越来越具有对话性和实用性。这个全面的教程将利用 PyTorch 和 Python 从头开始构建聊天机器人&#xff0c;涵盖模型架构、数据准备、训练循环…

Linux mount

挂载移动硬盘 1、通过 命令 fdisk -l 查看移动硬盘 2、创建 挂载点及文件 mkdir zen 3、mount -t ntfs /dev/sdb1 zen 报错&#xff1a;mount: unknown filesystem type ‘ntfs’ 需要安装ntfs-3g 如下才用编译安装方法&#xff1a; wget https://tuxera.com/opensource/ntf…

二叉树及其操作

导言&#xff1a; 二叉树是一种常见的树形数据结构&#xff0c;一棵二叉树是节点的一个有限集合&#xff0c;该集合或者为空或者是由一个根节点加上两颗分别为左子树和右子树的二叉树组成。本文主要对二叉树的四种遍历和基本操作进行介绍。 正文&#xff1a; 一、 二叉树的基…

如何在CentOS安装DataEase数据分析服务并实现远程访问管理界面

如何在CentOS安装DataEase数据分析服务并实现远程访问管理界面 前言1. 安装DataEase2. 本地访问测试3. 安装 cpolar内网穿透软件4. 配置DataEase公网访问地址5. 公网远程访问Data Ease6. 固定Data Ease公网地址 &#x1f308;你好呀&#xff01;我是 是Yu欸 &#x1f30c; 202…

重写Sylar基于协程的服务器(2、配置模块的设计)

重写Sylar基于协程的服务器&#xff08;2、配置模块的设计&#xff09; 重写Sylar基于协程的服务器系列&#xff1a; 重写Sylar基于协程的服务器&#xff08;0、搭建开发环境以及项目框架 || 下载编译简化版Sylar&#xff09; 重写Sylar基于协程的服务器&#xff08;1、日志模…

第0章 Linux 基础入门

第0章 Linux 基础入门 RHCSA Red Hat Certified System Administrator 红帽认证系统管理员。 什么是计算机 计算机的组成&#xff1a; 控制器 运算器 存储器 输出设备 输入设备 计算机只能识别0和1&#xff0c;也就是二进制数。 为什么要学习Linux Linux 因其高效率…