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

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...