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

news/2024/2/29 2:38:07

目录链接:

力扣编程题-解法汇总_分享+记录-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 因其高效率…

C# 根据USB设备VID和PID 获取设备总线已报告设备描述

总线已报告设备描述 DEVPKEY_Device_BusReportedDeviceDesc 模式 winform 语言 c# using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Window…

Hana SQL+正则表达式

目录 一、Pre 前言 二、知识点拆解 1&#xff09;case when…then…else 2&#xff09;json_value 函数 拓展资料 3&#xff09;CAST 函数 拓展资料 4) ROUND 函数 5&#xff09;occurences_regexpr 函数 拓展资料 6&#xff09;正则表达式 拓展资料 三、整合分析…

Git 指令

Git 安装 操作 命令行 简介&#xff1a; Git 是一个开源的分布式版本控制系统&#xff0c;用于敏捷高效地处理任何或小或大的项目。 Git 是 Linus Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。 Git 与常用的版本控制工具 CVS, Subversion …

Springboot项目启动后浏览器不能直接访问接口,而postman可以访问?

在云服务器上部署springboot后端时&#xff0c;项目启动后浏览器不能直接访问接口,而postman可以访问。这是当时困扰了我大半天的小问题&#xff0c;在我打开防火墙和阿里云安全组之后还是没解决。然后在网上搜了很多很多资料&#xff0c;以为是浏览器访问权限或者是https什么证…

QSqlRelationalTableModel 关系表格模型

一、 1.1 QSqlRelationalTableModel继承自QSqlTableModel&#xff0c;并且对其进行了扩展&#xff0c;提供了对外键的支持。一个外键就是一个表中的一个字段 和 其他表中的主键字段之间的一对一的映射。例如&#xff0c;“studInfo”表中的departID字段对应的是“departments…

C语言·贪吃蛇游戏(下)

上节我们将要完成贪吃蛇游戏所需的前置知识都学完了&#xff0c;那么这节我们就开始动手写代码了 1. 程序规划 首先我们应该规划好我们的代码文件&#xff0c;设置3个文件&#xff1a;snack.h 用来声明游戏中实现各种功能的函数&#xff0c;snack.c 用来实现函数&#xff0c;t…

Java知识点总结

数据类型强转&#xff1a;byte short int long float double &#xff1b; 数组定义 [ ]数组名 clone-复制数组equals-比较存储地址 toString sort-排序 length-长度 arraycopy([]a,s,[]b,ss,n)-数组复制 运算符及语句 instanceof双目运算符 –左对象右类 判断是否是该类创建…

SQL 语句

SQL 语句 1 数据定义语言&#xff08;Data Definition Language, DDL&#xff09;1.1 CREATE1.1.1 创建数据库1.1.2 创建表 1.2 DROP1.2.1 删除数据库1.2.2 删除表 1.3 ALTER1.3.1 添加列1.3.2 删除列1.3.3 修改列1.3.4 添加主键1.3.5 删除主键 2 数据操纵语言&#xff08;Data…

洗牌发牌并整理(1.数组 2.集合)

问题描述&#xff1a; 对52张牌进行洗10次后&#xff0c;依次发牌给4个玩家&#xff0c;再对每个玩家的牌进行整理。 第一种方式&#xff1a;数组实现 public static void main(String[] args) {//所有牌面花色char[] colors {红,黑,梅,方};//所有牌面数字String[] numbers…

pg数据库替换指定ip

pg数据库替换指定ip 配菜单是部署机ip发生变化&#xff0c;记录一下处理方法,先根据源ip查询出主键id&#xff0c;在将源ip替换成目标ip updatesys_menu sethref replace(href, 10.116.63.4, 10.116.58.23) whereid in(select*fromsys_menuwherehref like %10.116.58.23% )

Codeforces Round 481 (Div. 3)

本场比赛也是没有考察什么算法重点在于思维模式 目录 A. Remove Duplicates B. File Name C. Letters D. Almost Arithmetic Progression E. Bus Video System F. Mentors G. Petyas Exams A. Remove Duplicates 要求我们从右边开始保留数&#xff0c;我们可以考虑的就…

Git版本管理工具(实战进阶):零基础到起飞实战项目完整篇 →Git学习一篇就够 从基本指令、到本地仓库、远程仓库、实战项目开发演练介绍超详细!

heima 李师傅最新版 Git的讲解 文章目录 Git在实战项目开发使用功能学习01.Git 初识02.Git 仓库03.Git 的三个区域04.Git 文件状态05.Git 暂存区作用06.练习-登录页面07.Git-切换版本08.删除文件09.忽略文件10.分支的概念11.练习-登录 bug 修复12.分支-合并与删除13.分支-合并与…
最新文章