Python每日一练(20230510) 石子游戏 VII\VIII\IX

简介: Python每日一练(20230510) 石子游戏 VII\VIII\IX

1. 石子游戏 Stone Game VII


石子游戏中,爱丽丝和鲍勃轮流进行自己的回合,爱丽丝先开始


有 n 块石子排成一排。每个玩家的回合中,可以从行中 移除 最左边的石头或最右边的石头,并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时,得分较高者获胜。


鲍勃发现他总是输掉游戏(可怜的鲍勃,他总是输),所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。


给你一个整数数组 stones ,其中 stones[i] 表示 从左边开始 的第 i 个石头的值,如果爱丽丝和鲍勃都 发挥出最佳水平 ,请返回他们 得分的差值 。


示例 1:

输入:stones = [5,3,1,4,2]

输出:6


解释:

- 爱丽丝移除 2 ,得分 5 + 3 + 1 + 4 = 13 。游戏情况:爱丽丝 = 13 ,鲍勃 = 0 ,石子 = [5,3,1,4] 。

- 鲍勃移除 5 ,得分 3 + 1 + 4 = 8 。游戏情况:爱丽丝 = 13 ,鲍勃 = 8 ,石子 = [3,1,4] 。

- 爱丽丝移除 3 ,得分 1 + 4 = 5 。游戏情况:爱丽丝 = 18 ,鲍勃 = 8 ,石子 = [1,4] 。

- 鲍勃移除 1 ,得分 4 。游戏情况:爱丽丝 = 18 ,鲍勃 = 12 ,石子 = [4] 。

- 爱丽丝移除 4 ,得分 0 。游戏情况:爱丽丝 = 18 ,鲍勃 = 12 ,石子 = [] 。

得分的差值 18 - 12 = 6 。


示例 2:

输入:stones = [7,90,5,1,100,10,10,2]

输出:122


提示:

   n == stones.length

   2 <= n <= 1000

   1 <= stones[i] <= 1000


代码1: 动态规划


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


代码2:记忆化搜索

from typing import List
class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + stones[i]
        memo = [[None] * n for _ in range(n)]
        def dfs(left, right):
            if left == right:
                return 0
            if memo[left][right] is not None:
                return memo[left][right]
            res = max(prefix_sum[right + 1] - prefix_sum[left + 1] - dfs(left + 1, right), 
                      prefix_sum[right] - prefix_sum[left] - dfs(left, right - 1))
            memo[left][right] = res
            return res
        return dfs(0, n - 1)
#%%
s = Solution()
stones = [5,3,1,4,2]
print(s.stoneGameVII(stones))
stones = [7,90,5,1,100,10,10,2]
print(s.stoneGameVII(stones))


输出:

6

122



2. 石子游戏 Stone Game VIII


Alice 和 Bob 玩一个游戏,两人轮流操作, Alice 先手


总共有 n 个石子排成一行。轮到某个玩家的回合时,如果石子的数目 大于 1 ,他将执行以下操作:


   选择一个整数 x > 1 ,并且 移除 最左边的 x 个石子。

   将 移除 的石子价值之 和 累加到该玩家的分数中。

   将一个 新的石子 放在最左边,且新石子的值为被移除石子值之和。


当只剩下 一个 石子时,游戏结束。


Alice 和 Bob 的 分数之差 为 (Alice 的分数 - Bob 的分数) 。 Alice 的目标是 最大化 分数差,Bob 的目标是 最小化 分数差。


给你一个长度为 n 的整数数组 stones ,其中 stones[i] 是 从左边起 第 i 个石子的价值。请你返回在双方都采用 最优 策略的情况下,Alice 和 Bob 的 分数之差 。


示例 1:

输入:stones = [-1,2,-3,4,-5]

输出:5


解释:

- Alice 移除最左边的 4 个石子,得分增加 (-1) + 2 + (-3) + 4 = 2 ,并且将一个价值为 2 的石子放在最左边。stones = [2,-5] 。

- Bob 移除最左边的 2 个石子,得分增加 2 + (-5) = -3 ,并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。

两者分数之差为 2 - (-3) = 5 。


示例 2:

输入:stones = [7,-6,5,10,5,-2,-6]

输出:13


解释:

- Alice 移除所有石子,得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ,并且将一个价值为 13 的石子放在最左边。stones = [13] 。

两者分数之差为 13 - 0 = 13 。


示例 3:

输入:stones = [-10,-12]

输出:-22


解释:

- Alice 只有一种操作,就是移除所有石子。得分增加 (-10) + (-12) = -22 ,并且将一个价值为 -22 的石子放在最左边。stones = [-22] 。

两者分数之差为 (-22) - 0 = -22 。


提示:

   n == stones.length

   2 <= n <= 10^5

   -10^4 <= stones[i] <= 10^4


代码: 动态规划

from typing import List
class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        n = len(stones)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + stones[i]
        dp = [0] * n
        dp[n - 1] = prefix_sum[n]
        for i in range(n - 2, 0, -1):
            dp[i] = max(dp[i + 1], prefix_sum[i + 1] - dp[i + 1])
        return dp[1]
#%%
s = Solution()
stones = [-1,2,-3,4,-5]
print(s.stoneGameVIII(stones))
stones = [7,-6,5,10,5,-2,-6]
print(s.stoneGameVIII(stones))
stones = [-10,-12]
print(s.stoneGameVIII(stones))



输出:

5

13

-22


3. 石子游戏 Stone Game IX


Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ,其中 stones[i] 是第 i 个石子的价值。


Alice 和 Bob 轮流进行自己的回合,Alice 先手。每一回合,玩家需要从 stones 中移除任一石子。


   如果玩家移除石子后,导致 所有已移除石子 的价值 总和 可以被 3 整除,那么该玩家就 输掉游戏 。


   如果不满足上一条,且移除后没有任何剩余的石子,那么 Bob 将会直接获胜(即便是在 Alice 的回合)。


假设两位玩家均采用 最佳 决策。如果 Alice 获胜,返回 true ;如果 Bob 获胜,返回 false 。


示例 1:

输入:stones = [2,1]

输出:true


解释:游戏进行如下:

- 回合 1:Alice 可以移除任意一个石子。

- 回合 2:Bob 移除剩下的石子。  

已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此,Bob 输,Alice 获胜。


示例 2:

输入:stones = [2]

输出:false

解释:Alice 会移除唯一一个石子,已移除石子的值总和为 2 。  

由于所有石子都已移除,且值总和无法被 3 整除,Bob 获胜。


示例 3:

输入:stones = [5,1,2,4,3]

输出:false


解释:Bob 总会获胜。其中一种可能的游戏进行方式如下:


- 回合 1:Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。

- 回合 2:Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。

- 回合 3:Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。

- 回合 4:Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10.

- 回合 5:Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15.

Alice 输掉游戏,因为已移除石子值总和(15)可以被 3 整除,Bob 获胜。


提示:

   1 <= stones.length <= 10^5

   1 <= stones[i] <= 10^4


代码:

from typing import List
class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        count = [0] * 3  # 统计每个余数出现的次数
        for stone in stones:
            count[stone % 3] += 1
        if count[0] % 2 == 0:  # 如果余数为 0 的石子个数为偶数,Alice 一定会输
            return count[1] > 0 and count[2] > 0  # 只有同时存在余数为 1 和余数为 2 的石子,Bob 才能获胜
        return abs(count[1] - count[2]) > 2  # 如果余数为 0 的石子个数为奇数,Alice 一定会获胜
#%%
s = Solution()
stones = [2,1]
print(s.stoneGameIX(stones))
stones = [2]
print(s.stoneGameIX(stones))
stones = [5,1,2,4,3]
print(s.stoneGameIX(stones))


输出:

True

False

False

目录
打赏
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编程:从基础到高级
在这篇文章中,我们将一起深入探索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
|
2月前
|
Python高性能编程:五种核心优化技术的原理与Python代码
Python在高性能应用场景中常因执行速度不及C、C++等编译型语言而受质疑,但通过合理利用标准库的优化特性,如`__slots__`机制、列表推导式、`@lru_cache`装饰器和生成器等,可以显著提升代码效率。本文详细介绍了这些实用的性能优化技术,帮助开发者在不牺牲代码质量的前提下提高程序性能。实验数据表明,这些优化方法能在内存使用和计算效率方面带来显著改进,适用于大规模数据处理、递归计算等场景。
73 5
Python高性能编程:五种核心优化技术的原理与Python代码
|
3月前
|
[oeasy]python055_python编程_容易出现的问题_函数名的重新赋值_print_int
本文介绍了Python编程中容易出现的问题,特别是函数名、类名和模块名的重新赋值。通过具体示例展示了将内建函数(如`print`、`int`、`max`)或模块名(如`os`)重新赋值为其他类型后,会导致原有功能失效。例如,将`print`赋值为整数后,无法再用其输出内容;将`int`赋值为整数后,无法再进行类型转换。重新赋值后,这些名称失去了原有的功能,可能导致程序错误。总结指出,已有的函数名、类名和模块名不适合覆盖赋新值,否则会失去原有功能。如果需要使用类似的变量名,建议采用其他命名方式以避免冲突。
56 14

热门文章

最新文章