当前位置: 首页 > 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;令无数英雄竞折腰…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...