网站内容建设的布局和结构,网站型营销,关于 公司网站建设的通知,网站图片特效代码目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;力扣 描述#xff1a;
爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行#xff0c;每堆都有正整…目录链接
力扣编程题-解法汇总_分享记录-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方法该方法返回的对方可能取到的最大值。所以遍历的12过程中会取让对方更小的那个来尝试。
* 进入到battle流程后等于身份切换切换到B的身份也走上述同样的逻辑一直这样执行下去。
* 如果剩余的堆数少于m那么一定是全部取完。
* 但是这样穷举所有可能的方式会导致算法超时所以我们做一个优化。用map来存储结果。
* key为执行到的步数和m值value则为可能取到的最大值。则不同场景下走到同样的key直接返回即可节省运算量。 代码
public class Solution1140 {Model playA;Model playB;int sumValue;MapString, Integer mapA new HashMap();MapString, 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;}MapString, 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;}}
}
