力扣解法汇总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 <= 1001 <= 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
目录链接: 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目: https://github.com/September26/java-algorithms 原题链接:力扣 描述: 爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行,每堆都有正整…...
Kerberos认证原理与使用教程
Kerberos认证原理与使用教程 一、Kerberos 概述 二、什么是 Kerberos Kerberos 是一种计算机网络认证协议,用来在非安全网络中,对个人通信以安全的手段进行身份认证。这个词又指麻省理工学院为这个协议开发的一套计算机软件。软件设计上采用客户端…...
内存取证常见例题思路方法-volatility (没有最全 只有更全)
目录 1.从内存文件中获取到用户hacker 的密码并且破解密码,将破解后的密码作为 Flag值提交; 2.获取当前系统的主机名,将主机名作为Flag值提交; 3.获取当前系统浏览器搜索过的关键词,作为Flag提交; 4.获取当前内存文件的 ip地址 5.当前系…...
10 种主数据模型设计示例分享,推荐收藏
主数据模型是主数据管理的基础,一个完整的、可扩展的、相对稳定的主数据模型对于主数据管理的成功起着重要的作用。规划、创建主数据模型的过程,是梳理主数据管理体系的过程,目的是建立一个良好的资源目录结构,划分合理的资源粒度…...
React学习笔记
React学习笔记 概述 React是用于构建用户界面的JavaScript库。 现在前端领域最为流行的三大框架: VueReactAngular 其中,Vue和React是国内最为流行的两个框架。 React的特点: 1、声明式编程:它允许我们只需要维护自己的状态…...
【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函数嵌套使用,得到虚拟DOM树(重要)3.5 patchVnode函数3.6…...
算法学习与填充计划---2023.2.21---夏目
🚀write in front🚀 📝个人主页:认真写博客的夏目浅石.CSDN 🎁欢迎各位→点赞👍 收藏⭐️ 留言📝 📣系列专栏:ACM周训练题目合集.CSDN 💬总结:…...
JavaScript中怎么实现链表?
JavaScript中怎么实现链表? 学习数据结构的的链表和树时,会遇到节点(node)这个词,节点是处理数据结构的链表和树的基础。节点是一种数据元素,包括两个部分:一个是实际需要用到的数据;…...
多孔弹性材料中传播的膨胀波方法(Matlab代码实现)
👨🎓个人主页:研学社的博客💥💥💞💞欢迎来到本博客❤️❤️💥💥🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密…...
时间复杂度与空间复杂度
目录一、算法的复杂度二、时间复杂度2.1 什么叫时间复杂度2.2 大O的渐进表示法2.3 计算时间复杂度的练习三、空间复杂度四、常见复杂度的对比一、算法的复杂度 算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏…...
UDP报文详解
目录 🐳今日良言:走好选择的路,别选择好走的路,你才能拥有真正的自己。 🐼一、UDP协议特点 🐼二、UDP协议段格式详解 🐳今日良言:走好选择的路,别选择好走的路,你才能拥有真正的自…...
C#开发的OpenRA的NextPowerOf2
C#开发的OpenRA的NextPowerOf2 在游戏里,经常需要对计算资源进行优化。 比如屏幕的大小,以及缓冲区的大小,还有纹理的大小。 由于计算机都是基于二进制的原理,那么它的最快计算速度,就是让计算的数字都是2的n次方。 基于此策略,在程序里就需要计算出来最接近2的n次方的数…...
CDH 6.3.2启用HDFS高可用
启用原因 CDH 6.3.2平台即将用于生产,生产平台几乎需要高可用平台,故需要升级CDH中的HDFS为HA。 启用准备 CDH已经成功安装并正常使用CMS的管理员账号正常登陆 HDFS启用HA 登陆CMS系统->选择HDFS服务->点击进入到HDFS服务详情页面,…...
多服务器节点访问解决一人一单问题+redis设置锁方案
项目地址及项目具体介绍-码云仓库:https://gitee.com/flowers-bloom-is-the-sea/distributeNodeSolvePessimisticLockByRedis 测试1: 这里使用jmeter同时启动2各线程: 原来的数据库表的数据: goods的数据是: id …...
tensorflow 学习笔记(三):神经网络八股
本节内容: 前两节使用 Tensorflow2 的原生代码大叫神经网络。本节使用 keras 搭建神经网络(八股:六步法,有 Sequential 和 class 两种)。 文章目录一、搭建网络八股 sequential1.1、keras 介绍1.2、六步法搭建 keras …...
华为OD机试真题Python实现【射击比赛】真题+解题思路+代码(20222023)
射击比赛 题目 给定一个射击比赛成绩单 包含多个选手若干次射击的成绩分数 请对每个选手按其最高三个分数之和进行降序排名 输出降序排名后的选手 ID 序列 条件如下: 一个选手可以有多个射击成绩的分数 且次序不固定如果一个选手成绩小于三个 则认为选手的所有成绩无效 排名忽…...
【YBT2023寒假Day12 C】树的计数 II(prufer)(结论)(数学)
树的计数 II 题目链接:YBT2023寒假Day12 C 题目大意 给你一个长度为 n 的排列 p,问你有多少个不同的有标号无根树,满足如果 i,j 有边那 pi,pj 也有边。 思路 首先可以把排列变成置换环。 注意到是树,发现一个置换中似乎不太可…...
深入浅出C++ ——多态
文章目录一、多态的概念二、多态的定义及实现1. 多态的构成条件2. 虚函数3. 虚函数的重写4. virtual的使用:5. 虚函数重写的两个例外: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、福利:工程代码的获取1、前言 FPGA图像采集领域目前协议最复杂、技术难度最高的应该就是MIPI协议了,MIPI解码难度之高,令无数英雄竞折腰…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
从零开始了解数据采集(二十八)——制造业数字孪生
近年来,我国的工业领域正经历一场前所未有的数字化变革,从“双碳目标”到工业互联网平台的推广,国家政策和市场需求共同推动了制造业的升级。在这场变革中,数字孪生技术成为备受关注的关键工具,它不仅让企业“看见”设…...
ArcPy扩展模块的使用(3)
管理工程项目 arcpy.mp模块允许用户管理布局、地图、报表、文件夹连接、视图等工程项目。例如,可以更新、修复或替换图层数据源,修改图层的符号系统,甚至自动在线执行共享要托管在组织中的工程项。 以下代码展示了如何更新图层的数据源&…...
