当前位置: 首页 > news >正文

力扣解法汇总1140. 石子游戏 II

目录链接:

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

GitHub同步刷题项目:

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

原题链接:力扣


描述:

爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行,每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

爱丽丝和鲍勃轮流进行,爱丽丝先开始。最初,M = 1

在每个玩家的回合中,该玩家可以拿走剩下的  X 堆的所有石子,其中 1 <= X <= 2M。然后,令 M = max(M, X)

游戏一直持续到所有石子都被拿走。

假设爱丽丝和鲍勃都发挥出最佳水平,返回爱丽丝可以得到的最大数量的石头。

示例 1:

输入:piles = [2,7,9,4,4]
输出:10
解释:如果一开始Alice取了一堆,Bob取了两堆,然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 = 10堆。如果Alice一开始拿走了两堆,那么Bob可以拿走剩下的三堆。在这种情况下,Alice得到2 + 7 = 9堆。返回10,因为它更大。

示例 2:

输入:piles = [1,2,3,4,5,100]
输出:104

提示:

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 104

解题思路:

* 解题思路:
* 我的解法是两人互弈,分别构建对象A和,A先走,分别尝试取1堆和2堆,分别调用battle方法,该方法返回的对方可能取到的最大值。所以遍历的1,2过程中,会取让对方更小的那个来尝试。
* 进入到battle流程后,等于身份切换,切换到B的身份,也走上述同样的逻辑,一直这样执行下去。
* 如果剩余的堆数少于m,那么一定是全部取完。
* 但是这样穷举所有可能的方式会导致算法超时,所以我们做一个优化。用map来存储结果。
* key为执行到的步数和m值,value则为可能取到的最大值。则不同场景下走到同样的key,直接返回即可,节省运算量。
 

代码:

public class Solution1140 {Model playA;Model playB;int sumValue;Map<String, Integer> mapA = new HashMap<>();Map<String, Integer> mapB = new HashMap<>();public int stoneGameII(int[] piles) {playA = new Model("A");playB = new Model("B");sumValue = Arrays.stream(piles).sum();return battle(piles, 0, 2, true, 0);}/*** 返回值为当前对象可能的最大值*/private int battle(int[] piles, int index, int m, boolean isARun, int step) {int sum = 0;if (m >= (piles.length - index)) {for (int i = index; i < piles.length; i++) {sum += piles[i];}return sum;}Map<String, Integer> map = isARun ? mapA : mapB;String key = index + "_" + m;if (map.get(key) != null) {return map.get(key);}Model play = isARun ? playA : playB;Model other = isARun ? playB : playA;int minSum = Integer.MAX_VALUE;for (int i = 0; i < m; i++) {sum += piles[index + i];play.sum += sum;//这里的battle是对方运行时可能的最大值。int battle = battle(piles, index + i + 1, Math.max(m, 2 * (i + 1)), !isARun, step + 1);play.sum -= sum;if (battle < minSum) {minSum = battle;}}int value = sumValue - play.sum - other.sum - minSum;map.put(key, value);return value;}static class Model {String name;int sum;Model(String name) {this.name = name;}}
}

相关文章:

力扣解法汇总1140. 石子游戏 II

目录链接&#xff1a; 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目&#xff1a; https://github.com/September26/java-algorithms 原题链接&#xff1a;力扣 描述&#xff1a; 爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行&#xff0c;每堆都有正整…...

Kerberos认证原理与使用教程

Kerberos认证原理与使用教程 一、Kerberos 概述 二、什么是 Kerberos ​ Kerberos 是一种计算机网络认证协议&#xff0c;用来在非安全网络中&#xff0c;对个人通信以安全的手段进行身份认证。这个词又指麻省理工学院为这个协议开发的一套计算机软件。软件设计上采用客户端…...

内存取证常见例题思路方法-volatility (没有最全 只有更全)

目录 1.从内存文件中获取到用户hacker 的密码并且破解密码&#xff0c;将破解后的密码作为 Flag值提交; 2.获取当前系统的主机名&#xff0c;将主机名作为Flag值提交; 3.获取当前系统浏览器搜索过的关键词&#xff0c;作为Flag提交; 4.获取当前内存文件的 ip地址 5.当前系…...

10 种主数据模型设计示例分享,推荐收藏

主数据模型是主数据管理的基础&#xff0c;一个完整的、可扩展的、相对稳定的主数据模型对于主数据管理的成功起着重要的作用。规划、创建主数据模型的过程&#xff0c;是梳理主数据管理体系的过程&#xff0c;目的是建立一个良好的资源目录结构&#xff0c;划分合理的资源粒度…...

React学习笔记

React学习笔记 概述 React是用于构建用户界面的JavaScript库。 现在前端领域最为流行的三大框架&#xff1a; VueReactAngular 其中&#xff0c;Vue和React是国内最为流行的两个框架。 React的特点&#xff1a; 1、声明式编程&#xff1a;它允许我们只需要维护自己的状态…...

【Vue源码解析】Vue虚拟dom和diff算法

Vue虚拟dom和diff算法1. 简介2. 搭建环境1. 安装snabbdom2. 安装webpack5并配置3、函数3.1 虚拟节点vnode的属性3.2 使用h函数 创建虚拟节点3.3 使用patch函数 将虚拟节点上DOM树3.4 h函数嵌套使用&#xff0c;得到虚拟DOM树&#xff08;重要&#xff09;3.5 patchVnode函数3.6…...

算法学习与填充计划---2023.2.21---夏目

&#x1f680;write in front&#x1f680; &#x1f4dd;个人主页&#xff1a;认真写博客的夏目浅石.CSDN &#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐️ 留言&#x1f4dd;​ &#x1f4e3;系列专栏&#xff1a;ACM周训练题目合集.CSDN &#x1f4ac;总结&#xff1a…...

JavaScript中怎么实现链表?

JavaScript中怎么实现链表&#xff1f; 学习数据结构的的链表和树时&#xff0c;会遇到节点&#xff08;node&#xff09;这个词&#xff0c;节点是处理数据结构的链表和树的基础。节点是一种数据元素&#xff0c;包括两个部分&#xff1a;一个是实际需要用到的数据&#xff1b…...

多孔弹性材料中传播的膨胀波方法(Matlab代码实现)

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密…...

时间复杂度与空间复杂度

目录一、算法的复杂度二、时间复杂度2.1 什么叫时间复杂度2.2 大O的渐进表示法2.3 计算时间复杂度的练习三、空间复杂度四、常见复杂度的对比一、算法的复杂度 算法在编写成可执行程序后&#xff0c;运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏&#xf…...

UDP报文详解

目录 &#x1f433;今日良言:走好选择的路&#xff0c;别选择好走的路&#xff0c;你才能拥有真正的自己。 &#x1f43c;一、UDP协议特点 &#x1f43c;二、UDP协议段格式详解 &#x1f433;今日良言:走好选择的路&#xff0c;别选择好走的路&#xff0c;你才能拥有真正的自…...

C#开发的OpenRA的NextPowerOf2

C#开发的OpenRA的NextPowerOf2 在游戏里,经常需要对计算资源进行优化。 比如屏幕的大小,以及缓冲区的大小,还有纹理的大小。 由于计算机都是基于二进制的原理,那么它的最快计算速度,就是让计算的数字都是2的n次方。 基于此策略,在程序里就需要计算出来最接近2的n次方的数…...

CDH 6.3.2启用HDFS高可用

启用原因 CDH 6.3.2平台即将用于生产&#xff0c;生产平台几乎需要高可用平台&#xff0c;故需要升级CDH中的HDFS为HA。 启用准备 CDH已经成功安装并正常使用CMS的管理员账号正常登陆 HDFS启用HA 登陆CMS系统->选择HDFS服务->点击进入到HDFS服务详情页面&#xff0c…...

多服务器节点访问解决一人一单问题+redis设置锁方案

项目地址及项目具体介绍-码云仓库&#xff1a;https://gitee.com/flowers-bloom-is-the-sea/distributeNodeSolvePessimisticLockByRedis 测试1&#xff1a; 这里使用jmeter同时启动2各线程&#xff1a; 原来的数据库表的数据&#xff1a; goods的数据是&#xff1a; id …...

tensorflow 学习笔记(三):神经网络八股

本节内容&#xff1a; 前两节使用 Tensorflow2 的原生代码大叫神经网络。本节使用 keras 搭建神经网络&#xff08;八股&#xff1a;六步法&#xff0c;有 Sequential 和 class 两种&#xff09;。 文章目录一、搭建网络八股 sequential1.1、keras 介绍1.2、六步法搭建 keras …...

华为OD机试真题Python实现【射击比赛】真题+解题思路+代码(20222023)

射击比赛 题目 给定一个射击比赛成绩单 包含多个选手若干次射击的成绩分数 请对每个选手按其最高三个分数之和进行降序排名 输出降序排名后的选手 ID 序列 条件如下: 一个选手可以有多个射击成绩的分数 且次序不固定如果一个选手成绩小于三个 则认为选手的所有成绩无效 排名忽…...

【YBT2023寒假Day12 C】树的计数 II(prufer)(结论)(数学)

树的计数 II 题目链接&#xff1a;YBT2023寒假Day12 C 题目大意 给你一个长度为 n 的排列 p&#xff0c;问你有多少个不同的有标号无根树&#xff0c;满足如果 i,j 有边那 pi,pj 也有边。 思路 首先可以把排列变成置换环。 注意到是树&#xff0c;发现一个置换中似乎不太可…...

深入浅出C++ ——多态

文章目录一、多态的概念二、多态的定义及实现1. 多态的构成条件2. 虚函数3. 虚函数的重写4. virtual的使用&#xff1a;5. 虚函数重写的两个例外&#xff1a;6. C11 override 和 final7. 重载、重写、重定义的对比三、抽象类四、多态的原理1. 虚函数表2. 多态的原理3. 静态绑定…...

华为OD机试真题Python实现【整数编码】真题+解题思路+代码(20222023)

整数编码 题目 实现一个整数编码方法 使得待编码的数字越小 编码后所占用的字节数越小 编码规则如下 编码时7位一组,每个字节的低 7 位用于存储待编码数字的补码字节的最高位表示后续是否还有字节,置1表示后面还有更多的字节,置0表示当前字节为最后一个字节采用小端序编码…...

FPGA纯Vhdl实现MIPI CSI2RX视频解码输出,OV13850采集,提供工程源码和技术支持

目录1、前言2、Xilinx官方主推的MIPI解码方案3、纯Vhdl方案解码MIPI4、vivado工程介绍5、上板调试验证6、福利&#xff1a;工程代码的获取1、前言 FPGA图像采集领域目前协议最复杂、技术难度最高的应该就是MIPI协议了&#xff0c;MIPI解码难度之高&#xff0c;令无数英雄竞折腰…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...