Python每日一练(20230509) 石子游戏 IV\V\VI

简介: Python每日一练(20230509) 石子游戏 IV\V\VI

1. 石子游戏 Stone Game IV


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


一开始,有 n 个石子堆在一起。每个人轮流操作,正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。


如果石子堆里没有石子了,则无法操作的玩家输掉游戏。


给你正整数 n ,且已知两个人都采取最优策略。如果 Alice 会赢得比赛,那么返回 True ,否则返回 False 。


示例 1:

输入:n = 1

输出:true

解释:Alice 拿走 1 个石子并赢得胜利,因为 Bob 无法进行任何操作。


示例 2:

输入:n = 2

输出:false

解释:Alice 只能拿走 1 个石子,然后 Bob 拿走最后一个石子并赢得胜利(2 -> 1 -> 0)。


示例 3:

输入:n = 4

输出:true

解释:n 已经是一个平方数,Alice 可以一次全拿掉 4 个石子并赢得胜利(4 -> 0)。


示例 4:

输入:n = 7

输出:false

解释:当 Bob 采取最优策略时,Alice 无法赢得比赛。


如果 Alice 一开始拿走 4 个石子, Bob 会拿走 1 个石子,然后 Alice 只能拿走 1 个石子,Bob 拿走最后一个石子并赢得胜利(7 -> 3 -> 2 -> 1 -> 0)。


如果 Alice 一开始拿走 1 个石子, Bob 会拿走 4 个石子,然后 Alice 只能拿走 1 个石子,Bob 拿走最后一个石子并赢得胜利(7 -> 6 -> 2 -> 1 -> 0)。


示例 5:

输入:n = 17

输出:false

解释:如果 Bob 采取最优策略,Alice 无法赢得胜利。


提示:

   1 <= n <= 10^5

代码:

class Solution:
    def stoneGameIV(self, n: int) -> bool:
        dp = [False] * (n + 1)
        for i in range(1, n + 1):
            for j in range(1, int(i**0.5) + 1):
                if not dp[i - j*j]:
                    dp[i] = True
                    break
        return dp[n]
#%%
s = Solution()
print(s.stoneGameIV(1))
print(s.stoneGameIV(2))
print(s.stoneGameIV(4))
print(s.stoneGameIV(7))
print(s.stoneGameIV(17))

输出:

True

False

True

False

False


2. 石子游戏 Stone Game V


几块石子 排成一行 ,每块石子都有一个关联值,关联值为整数,由数组 stoneValue 给出。


游戏中的每一轮:Alice 会将这行石子分成两个 非空行(即,左侧行和右侧行);Bob 负责计算每一行的值,即此行中所有石子的值的总和。Bob 会丢弃值最大的行,Alice 的得分为剩下那行的值(每轮累加)。如果两行的值相等,Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。


只 剩下一块石子 时,游戏结束。Alice 的分数最初为 0 。


返回 Alice 能够获得的最大分数 。


示例 1:

输入:stoneValue = [6,2,3,4,5,5]

输出:18

解释:在第一轮中,Alice 将行划分为 [6,2,3],[4,5,5] 。左行的值是 11 ,右行的值是 14 。Bob 丢弃了右行,Alice 的分数现在是 11 。


在第二轮中,Alice 将行分成 [6],[2,3] 。这一次 Bob 扔掉了左行,Alice 的分数变成了 16(11 + 5)。


最后一轮 Alice 只能将行分成 [2],[3] 。Bob 扔掉右行,Alice 的分数现在是 18(16 + 2)。游戏结束,因为这行只剩下一块石头了。


示例 2:

输入:stoneValue = [7,7,7,7,7,7,7]

输出:28


示例 3:

输入:stoneValue = [4]

输出:0

提示:

   1 <= stoneValue.length <= 500

   1 <= stoneValue[i] <= 10^6


代码1: 动态规划

from typing import List
class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)
        presum = [0] * (n + 1)
        for i in range(n):
            presum[i + 1] = presum[i] + stoneValue[i]
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 0
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                for k in range(i, j):
                    leftsum = presum[k + 1] - presum[i]
                    rightsum = presum[j + 1] - presum[k + 1]
                    if leftsum < rightsum:
                        dp[i][j] = max(dp[i][j], dp[i][k] + leftsum)
                    elif leftsum > rightsum:
                        dp[i][j] = max(dp[i][j], dp[k + 1][j] + rightsum)
                    else:
                        dp[i][j] = max(dp[i][j], dp[i][k] + leftsum, dp[k + 1][j] + rightsum)
        return dp[0][n - 1]
#%%
s = Solution()
stoneValue = [6,2,3,4,5,5]
print(s.stoneGameV(stoneValue))
stoneValue = [7,7,7,7,7,7,7]
print(s.stoneGameV(stoneValue))


代码2:记忆化搜索

from typing import List
class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)
        presum = [0] * (n + 1)
        for i in range(n):
            presum[i + 1] = presum[i] + stoneValue[i]
        memo = [[-1] * n for _ in range(n)]
        def dfs(i, j):
            if memo[i][j] != -1:
                return memo[i][j]
            if i == j:
                memo[i][j] = 0
                return 0
            res = 0
            for k in range(i, j):
                leftsum = presum[k + 1] - presum[i]
                rightsum = presum[j + 1] - presum[k + 1]
                if leftsum < rightsum:
                    res = max(res, dfs(i, k) + leftsum)
                elif leftsum > rightsum:
                    res = max(res, dfs(k + 1, j) + rightsum)
                else:
                    res = max(res, dfs(i, k) + leftsum, dfs(k + 1, j) + rightsum)
            memo[i][j] = res
            return res
        return dfs(0, n - 1)
#%%
s = Solution()
stoneValue = [6,2,3,4,5,5]
print(s.stoneGameV(stoneValue))
stoneValue = [7,7,7,7,7,7,7]
print(s.stoneGameV(stoneValue))

输出:

18

28


3. 石子游戏 Stone Game VI


Alice 和 Bob 轮流玩一个游戏,Alice 先手。


一堆石子里总共有 n 个石子,轮到某个玩家时,他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。


给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。


所有石子都被取完后,得分较高的人为胜者。如果两个玩家得分相同,那么为平局。两位玩家都会采用 最优策略 进行游戏。


请你推断游戏的结果,用如下的方式表示:


   如果 Alice 赢,返回 1 。

   如果 Bob 赢,返回 -1 。

   如果游戏平局,返回 0 。


示例 1:

输入:aliceValues = [1,3], bobValues = [2,1]

输出:1


解释:

如果 Alice 拿石子 1 (下标从 0开始),那么 Alice 可以得到 3 分。

Bob 只能选择石子 0 ,得到 2 分。

Alice 获胜。


示例 2:

输入:aliceValues = [1,2], bobValues = [3,1]

输出:0

解释:

Alice 拿石子 0 , Bob 拿石子 1 ,他们得分都为 1 分。

打平。


示例 3:

输入:aliceValues = [2,4,3], bobValues = [1,6,7]

输出:-1

解释:

不管 Alice 怎么操作,Bob 都可以得到比 Alice 更高的得分。

比方说,Alice 拿石子 1 ,Bob 拿石子 2 , Alice 拿石子 0 ,Alice 会得到 6 分而 Bob 得分为 7 分。

Bob 会获胜。


提示:

   n == aliceValues.length == bobValues.length

   1 <= n <= 105

   1 <= aliceValues[i], bobValues[i] <= 100


代码1: 动态规划


from typing import List
class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
        n = len(aliceValues)
        total_values = [(aliceValues[i] + bobValues[i], i) for i in range(n)]
        total_values.sort(reverse=True)
        alice_dp, bob_dp = [0] * (n + 1), [0] * (n + 1)
        for i in range(n):
            if i % 2 == 0:
                alice_dp[i // 2 + 1] = alice_dp[i // 2] + aliceValues[total_values[i][1]]
            else:
                bob_dp[i // 2 + 1] = bob_dp[i // 2] + bobValues[total_values[i][1]]
        for i in range(n // 2):
            alice_dp[i + 1] = max(alice_dp[i], alice_dp[i + 1])
            bob_dp[i + 1] = max(bob_dp[i], bob_dp[i + 1])
        diff = alice_dp[n // 2] - bob_dp[n // 2]
        if diff > 0:
            return 1
        elif diff < 0:
            return -1
        else:
            return 0
#%%
s = Solution()
aliceValues = [1,3]
bobValues = [2,1]
print(s.stoneGameVI(aliceValues, bobValues))
aliceValues = [1,2]
bobValues = [3,1]
print(s.stoneGameVI(aliceValues, bobValues))
aliceValues = [2,4,3]
bobValues = [1,6,7]
print(s.stoneGameVI(aliceValues, bobValues))


代码2: 贪心算法

from typing import List
class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
        n = len(aliceValues)
        stones = [(aliceValues[i] + bobValues[i], i) for i in range(n)]
        stones.sort(reverse=True)
        a_score, b_score = 0, 0
        for i in range(n):
            if i % 2 == 0:
                a_score += aliceValues[stones[i][1]]
            else:
                b_score += bobValues[stones[i][1]]
        if a_score > b_score:
            return 1
        elif a_score < b_score:
            return -1
        else:
            return 0
#%%
s = Solution()
aliceValues = [1,3]
bobValues = [2,1]
print(s.stoneGameVI(aliceValues, bobValues))
aliceValues = [1,2]
bobValues = [3,1]
print(s.stoneGameVI(aliceValues, bobValues))
aliceValues = [2,4,3]
bobValues = [1,6,7]
print(s.stoneGameVI(aliceValues, bobValues))


输出:

1

0

-1

目录
打赏
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

热门文章

最新文章

AI助理

你好,我是AI助理

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