Python每日一练(20230508) 石子游戏 I\II\III

简介: Python每日一练(20230508) 石子游戏 I\II\III

1. 石子游戏 Stone Game I


Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子,排成一行;每堆都有 整数颗石子,数目为 piles[i]


游戏以谁手中的石子最多来决出胜负。石子的 总数奇数 ,所以没有平局。


Alice 和 Bob 轮流进行,Alice 先开始 。 每回合,玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中 石子最多 的玩家 获胜 。


假设 Alice 和 Bob 都发挥出最佳水平,当 Alice 赢得比赛时返回 true ,当 Bob 赢得比赛时返回 false 。


示例 1:

输入:piles = [5,3,4,5]

输出:true


解释:

Alice 先开始,只能拿前 5 颗或后 5 颗石子 。

假设他取了前 5 颗,这一行就变成了 [3,4,5] 。

如果 Bob 拿走前 3 颗,那么剩下的是 [4,5],Alice 拿走后 5 颗赢得 10 分。

如果 Bob 拿走后 5 颗,那么剩下的是 [3,4],Alice 拿走后 4 颗赢得 9 分。

这表明,取前 5 颗石子对 Alice 来说是一个胜利的举动,所以返回 true 。


示例 2:

输入:piles = [3,7,2,3]

输出:true


提示:

   2 <= piles.length <= 500

   piles.length 是 偶数

   1 <= piles[i] <= 500

   sum(piles[i]) 是 奇数


代码:

from typing import List
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        return dp[0][n-1] > 0
# %%
s = Solution()
piles = [5,3,4,5]
print(s.stoneGame(piles))
piles = [3,7,2,3]
print(s.stoneGame(piles))

输出:

True

True


2. 石子游戏 Stone Game II


爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行,每堆都有正整数颗石子 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] <= 10^4


代码:


from typing import List
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        prefix = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            prefix[i] = prefix[i+1] + piles[i]
        def dfs(i: int, m: int) -> int:
            if i + 2*m >= n:
                return prefix[i]
            res = float("inf")
            for x in range(1, 2*m+1):
                res = min(res, dfs(i+x, max(m, x)))
            return prefix[i] - res
        return dfs(0, 1)
# %%
s = Solution()
piles = [2,7,9,4,4]
print(s.stoneGameII(piles))
piles = [1,2,3,4,5,100]
print(s.stoneGameII(piles))
from typing import List
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        prefix = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            prefix[i] = prefix[i+1] + piles[i]
        cache = {}
        def dfs(i: int, M: int) -> int:
            if (i, M) in cache:
                return cache[(i, M)]
            if i + 2*M >= n:
                return prefix[i]
            score = float("-inf")
            for x in range(1, 2*M+1):
                score = max(score, prefix[i] - dfs(i+x, max(M, x)))
            cache[(i, M)] = score
            return score
        return dfs(0, 1)
# %%
s = Solution()
piles = [2,7,9,4,4]
print(s.stoneGameII(piles))
piles = [1,2,3,4,5,100]
print(s.stoneGameII(piles))

输出:

10

104


3. 石子游戏 Stone Game III


Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行,每堆石子都对应一个得分,由数组 stoneValue 给出。


Alice 和 Bob 轮流取石子,Alice 总是先开始。在每个玩家的回合中,该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。


每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分,得分最高的选手将会赢得比赛,比赛也可能会出现平局。


假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 "Alice" ,Bob 赢了就返回 "Bob",平局(分数相同)返回 "Tie" 。


示例 1:

输入:values = [1,2,3,7]

输出:"Bob"

解释:Alice 总是会输,她的最佳选择是拿走前三堆,得分变成 6 。但是 Bob 的得分为 7,Bob 获胜。


示例 2:

输入:values = [1,2,3,-9]

输出:"Alice"


解释:Alice 要想获胜就必须在第一个回合拿走前三堆石子,给 Bob 留下负分。

如果 Alice 只拿走第一堆,那么她的得分为 1,接下来 Bob 拿走第二、三堆,得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆,输掉比赛。

如果 Alice 拿走前两堆,那么她的得分为 3,接下来 Bob 拿走第三堆,得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆,同样会输掉比赛。

注意,他们都应该采取 最优策略 ,所以在这里 Alice 将选择能够使她获胜的方案。


示例 3:

输入:values = [1,2,3,6]

输出:"Tie"

解释:Alice 无法赢得比赛。如果她决定选择前三堆,她可以以平局结束比赛,否则她就会输。


示例 4:

输入:values = [1,2,3,-1,-2,-3,7]

输出:"Alice"


示例 5:

输入:values = [-1,-2,-3]

输出:"Tie"


提示:

   1 <= values.length <= 50000

   -1000 <= values[i] <= 1000

代码:

from typing import List
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            total = 0
            dp[i] = -float("inf")
            for j in range(i, min(n, i + 3)):
                total += stoneValue[j]
                dp[i] = max(dp[i], total - dp[j + 1])
        if dp[0] > 0:
            return "Alice"
        elif dp[0] < 0:
            return "Bob"
        else:
            return "Tie"
#%%
s = Solution()
values = [1,2,3,7]
print(s.stoneGameIII(values))
values = [1,2,3,-9]
print(s.stoneGameIII(values))
values = [1,2,3,6]
print(s.stoneGameIII(values))
values = [1,2,3,-1,-2,-3,7]
print(s.stoneGameIII(values))
values = [-1,-2,-3]
print(s.stoneGameIII(values))

输出:

Bob

Alice

Tie

Alice

Tie

目录
打赏
0
0
0
0
74
分享
相关文章
【01】做一个精美的打飞机小游戏,浅尝阿里云通义灵码python小游戏开发AI编程-之飞机大战小游戏上手实践-优雅草央千澈-用ai开发小游戏尝试-分享源代码和游戏包
【01】做一个精美的打飞机小游戏,浅尝阿里云通义灵码python小游戏开发AI编程-之飞机大战小游戏上手实践-优雅草央千澈-用ai开发小游戏尝试-分享源代码和游戏包
232 48
【01】做一个精美的打飞机小游戏,浅尝阿里云通义灵码python小游戏开发AI编程-之飞机大战小游戏上手实践-优雅草央千澈-用ai开发小游戏尝试-分享源代码和游戏包
【02】做一个精美的打飞机小游戏,python开发小游戏-鹰击长空—优雅草央千澈-持续更新-分享源代码和游戏包供游玩-记录完整开发过程-用做好的素材来完善鹰击长空1.0.1版本
【02】做一个精美的打飞机小游戏,python开发小游戏-鹰击长空—优雅草央千澈-持续更新-分享源代码和游戏包供游玩-记录完整开发过程-用做好的素材来完善鹰击长空1.0.1版本
69 7
【03】做一个精美的打飞机小游戏,规划游戏项目目录-分门别类所有的资源-库-类-逻辑-打包为可玩的exe-练习python打包为可执行exe-优雅草卓伊凡-持续更新-分享源代码和游戏包供游玩-1.0.2版本
【03】做一个精美的打飞机小游戏,规划游戏项目目录-分门别类所有的资源-库-类-逻辑-打包为可玩的exe-练习python打包为可执行exe-优雅草卓伊凡-持续更新-分享源代码和游戏包供游玩-1.0.2版本
133 31
【03】做一个精美的打飞机小游戏,规划游戏项目目录-分门别类所有的资源-库-类-逻辑-打包为可玩的exe-练习python打包为可执行exe-优雅草卓伊凡-持续更新-分享源代码和游戏包供游玩-1.0.2版本
|
3月前
|
课程设计项目之基于Python实现围棋游戏代码
游戏进去默认为九路玩法,当然也可以选择十三路或是十九路玩法 使用pycharam打开项目,pip安装模块并引用,然后运行即可, 代码每行都有详细的注释,可以做课程设计或者毕业设计项目参考
84 33
Python扑克游戏编程---摸大点
Python扑克游戏编程---摸大点
90 1
python编写下象棋游戏|4-14
python编写下象棋游戏|4-14
Python pygame 实现游戏 彩色 五子棋 详细注释 附源码 单机版
Python pygame 实现游戏 彩色 五子棋 详细注释 附源码 单机版
121 0
探索Python编程:从基础到高级
在这篇文章中,我们将一起深入探索Python编程的世界。无论你是初学者还是有经验的程序员,都可以从中获得新的知识和技能。我们将从Python的基础语法开始,然后逐步过渡到更复杂的主题,如面向对象编程、异常处理和模块使用。最后,我们将通过一些实际的代码示例,来展示如何应用这些知识解决实际问题。让我们一起开启Python编程的旅程吧!
Python编程入门:从零基础到实战应用
本文是一篇面向初学者的Python编程教程,旨在帮助读者从零开始学习Python编程语言。文章首先介绍了Python的基本概念和特点,然后通过一个简单的例子展示了如何编写Python代码。接下来,文章详细介绍了Python的数据类型、变量、运算符、控制结构、函数等基本语法知识。最后,文章通过一个实战项目——制作一个简单的计算器程序,帮助读者巩固所学知识并提高编程技能。
[oeasy]python053_学编程为什么从hello_world_开始
视频介绍了“Hello World”程序的由来及其在编程中的重要性。从贝尔实验室诞生的Unix系统和C语言说起,讲述了“Hello World”作为经典示例的起源和流传过程。文章还探讨了C语言对其他编程语言的影响,以及它在系统编程中的地位。最后总结了“Hello World”、print、小括号和双引号等编程概念的来源。
128 80

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等