[已解决]Python：每日一题 352

zltzlt

今天的题目：

给定一个表示分数的非负整数数组。

玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，……。

每次一个玩家只能拿取一个分数，分数被拿取之后不再可取，直到没有剩余分数可取时游戏结束。

最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家 1 是否会成为赢家。假设每个玩家的玩法都会使他的分数最大化。

示例 1：

输入：[1, 5, 2]
输出：False
解释：一开始，玩家 1 可以从 1 和 2 中进行选择。
如果他选择 2（或者 1），那么玩家 2 可以从 1（或者 2）和 5 中进行选择。如果玩家 2 选择了 5，那么玩家 1 则只剩下 1（或者 2）可选。
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5。
因此，玩家 1 永远不会成为赢家，返回 False。

示例 2：

输入：[1, 5, 233, 7]
输出：True
解释：玩家 1 一开始选择 1。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

TJBEST

2020-3-16 15:19:15

zltzlt 发表于 2020-3-16 13:23
解答错误

输入：[1, 2, 99]

已修改 如下

def fun352(arr):

    M = len(arr)

    if M == 1:

        return True

    dictionary = dict()#存储形式 (起始，终止):(先手，后手)  起始终止 和切片一致

    for index in range(0,M-1):

        A = arr[zxsq-anti-bbcode-index]

        B = arr[index+1]

        if A < B:

            dictionary[(index,index+2)]=(B,A)

        else:

            dictionary[(index,index+2)]=(A,B)

    for index in range(3,M+1):

        for inner in range(0,M+1-index):

            choose1 = arr[zxsq-anti-bbcode-inner]

            before1 = dictionary[(inner+1,inner+index)][zxsq-anti-bbcode-0]

            after1 = dictionary[(inner+1,inner+index)][zxsq-anti-bbcode-1]

            result1 = (choose1+after1,before1)

            

            choose2 = arr[inner+index-1]

            before2 = dictionary[(inner,inner+index-1)][zxsq-anti-bbcode-0]

            after2 = dictionary[(inner,inner+index-1)][zxsq-anti-bbcode-1]

            result2 = (choose2+after2,before2)



            if result1[zxsq-anti-bbcode-0]>result2[zxsq-anti-bbcode-0]:

                dictionary[(inner,inner+index)] = result1

            else:

                dictionary[(inner,inner+index)] = result2

    if dictionary[(0,M)][zxsq-anti-bbcode-0]>dictionary[(0,M)][zxsq-anti-bbcode-1]:

        return True

    else:

        return False

跳转到最佳答案楼层

zltzlt

平局返回 True

TJBEST

测试了一下，比较慢 先这样，我再想想有什么好办法。测试1000个数接近秒级 不甚理想。

def fun352(arr):
    M = len(arr)
    if M == 1:
        return True
    dictionary = dict()#存储形式 (起始，终止):(先手，后手)  起始终止 和切片一致
    for index in range(0,M-1):
        A = arr[index]
        B = arr[index+1]
        if A < B:
            dictionary[(index,index+2)]=(B,A)
        else:
            dictionary[(index,index+2)]=(A,B)
    for index in range(3,M+1):
        for inner in range(0,M+1-index):
            choose1 = arr[inner]
            before1 = dictionary[(inner+1,inner+index)][0]
            after1 = dictionary[(inner+1,inner+index)][1]
            result1 = (choose1+after1,before1)
            
            choose2 = arr[inner+index-1]
            before2 = dictionary[(inner,inner+index-1)][0]
            after2 = dictionary[(inner,inner+index-1)][1]
            result2 = (choose1+after1,before1)
            
            dictionary[(inner,inner+index)] = max([result1,result2])
    if dictionary[(0,M)][0]>dictionary[(0,M)][1]:
        return True
    else:
        return False

蒋博文

def fun352(num):
    n = len(num)
    if n % 2 == 0 or n == 1:
        return True
    a = [[0] * n for each in range(n)]
    for i in reversed(range(n)):
        for j in range(i+1, n):
            a[i][j] = max(num[i] - a[i+1][j], num[j] - a[i][j-1])     
    return a[0][-1] >= 0

永恒的蓝色梦想

参考leetcode题解和评论区大神得出来的答案，动态规划

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        if len(nums)&1:
            length=len(nums)
            dp=[[0]*length]*length

            for i in range(length):
                dp[i][i]=nums[i]

            i=length
            while i:
                i-=1
                for j in range(i+1,length):
                    dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
            
            return dp[0][-1]>=0
        else:
            return True

Qiummmmmml

等一下发！

TJBEST

我在考虑如果数组过大，可能很麻烦这个是指数次的运算量 而且涉及博弈

ouyunfu

def f352(L:list)->bool:
    def f(a, b):
        if b-a == 0:
            return L[a]
        elif b-a == 1:
            return max(L[a:b+1])-min(L[a:b+1])
        x,y,z=f(a+2, b),f(a+1, b-1),f(a, b-2)
        return max(min(x-L[a+1]+L[a],y-L[b]+L[a]),min(y-L[a]+L[b],z-L[b-1]+L[b]))
    if len(L)==1 or len(L)==2:
        return True
    elif len(L)==3:
        if L[0]+L[2]>L[1]:
            return True
        else:
            return False
    elif len(L)==4:
        if L[0]+L[2]!=L[1]+L[3]:
            return True
        else:
            return False
    else:
        return f(0,len(L)-1)>0  
print(f352([1, 5, 2]))
print(f352([1, 5, 233, 7]))
print(f352([i for i in range(30)]))

l0stparadise

。。。放弃，只想到了暴力的思路，围观大佬们

风魔孤行者

第二个例子，马上把我写的代码否定了

kinkon

编出来的程序自己都看不懂，没有数据计算，单纯的选大小，除了快一点，其他的只能emmm了

def f352(n):   
    a, b = 0, len(n) - 1
    if not len(n)%2:return True
    res = []
    while a < b:        
        if a + 1 == b:
            if n[a] > n[b]:
                res.append(n[a])
                a += 1
            else:
                res.append(n[b])
                b -= 1      
        if n[a] > n[b] and n[a] > n[a+1]:                               
                res.append(n[a])
                a += 1        
        elif n[b] > n[a] and n[b] > n[b-1]:            
                res.append(n[b])
                b -= 1               
        elif n[a] < n[b] and n[a] < n[a+1]:
            #if n[a+1] <= n[b] and n[b-1] > n[b]:             
            if n[a+1] <= n[b-1]:                 
                res.append(n[a])
                a += 1
            else:
                res.append(n[b])
                b -= 1                
        elif n[b] < n[a] and n[b] < n[b-1]:             
            if n[b-1] <= n[a+1]:                
                res.append(n[b])
                b -= 1
            else:
                res.append(n[a])
                a += 1                
        elif n[a] > n[b] and n[a] < n[a+1]:             
            if n[a+1] <= n[b-1]:                 
                res.append(n[a])
                a += 1
            else:
                res.append(n[b])                
                b -= 1                
        elif n[b] > n[a] and n[b] < n[b-1]:             
            if n[b-1] <= n[a+1]:                 
                res.append(n[b])
                b -= 1
            else:
                res.append(n[a])
                a += 1                
        elif n[a] < n[b] and n[a] > n[a+1]:             
            if n[b] <= n[b-1]:                 
                res.append(n[a])
                a += 1
            else:
                res.append(n[b])
                b -= 1                
        elif n[b] < n[a] and n[b] > n[b-1]:             
            if n[a] <= n[a+1]:                 
                res.append(n[b])
                b -= 1
            else:
                res.append(n[a])
                a += 1
        else:            
            if n[a] > n[b]:
                res.append(n[a])
                a += 1
            else:
                res.append(n[b])
                b -= 1                                                
    c = sum([res[i] for i in range(len(res)) if not i % 2])
    d = sum([res[i] for i in range(len(res)) if i % 2]) 
    if c > d: return True
    return False

TJBEST

版主已经写完，见二楼，可能不甚理想，但是结果应该没错

546623863

def fun352(scores:list):
    if(len(scores) == 0):
        return None
    elif(len(scores) == 1):
        return True
    player1 = 0
    player2 = 0
    Sum = sum(scores)
    def choice(scores:list, Cur:int, Next:int):
        length = len(scores)
        if(length == 0):
            return None
        elif(length == 1):
            return 0
        elif(1 < length < 4):
            return scores.index(max(scores[0],scores[-1]))
        if(scores[1] >= scores[-2]):
            if((scores[1] + min(scores[0],scores[-1]) > scores[-2] + max(scores[0],scores[-1])) or ((scores[1] + Next) >= Sum/2)):
                return -1
            else:
                return scores.index(max(scores[0],scores[-1]))
        else:
            if((scores[-2] + min(scores[0],scores[-1]) > scores[1] + max(scores[0],scores[-1])) or (scores[-2] + Next >= Sum/2)):
                return 0
            else:
                return scores.index(max(scores[0],scores[-1]))
    
    while(scores != []):
        index = choice(scores, player1, player2)
        player1 += scores.pop(index)
        index = choice(scores, player2, player1)
        if(index == None):
            break
        else:
            player2 += scores.pop(index)
    if(player1 > player2):
        return True
    elif(player1 < player2):
        return False
    else:
        return "平局"

例子测试的没啥问题，估计效率不会太高

Unicorn#

def solve(s):
    def f(l, r):
        if r - l == 0:
            return s[l]
        elif r - l == 1:
            return max(s[l:r+1])-min(s[l:r+1])
        a = f(l+2, r)
        b = f(l+1, r-1)
        c = f(l, r-2)
        return max(
            min(a - s[l+1] + s[l],
                b - s[r] + s[l]),
            min(b - s[l] + s[r],
                c - s[r-1] + s[r])
            )
    return f(0, len(s)-1) > 0

fan1993423

平局怎么办，还有0分的吗？

小python1

马上发

fan1993423

A_player,B_player=0,0
def fun352(lst):
    if not len(lst):return '平局'
    elif len(lst)==1 and lst[0]>0:return True
    elif len(lst)==1 and lst[0]==0:return '平局'
    elif len(lst)==2:
        if lst[0]==lst[1] :return '平局'
        else:return True
    else:
        def recursive(lst,player,i):
            global A_player,B_player
            if len(lst)==1 and i%2:
                B_player+=lst[0]
                return
            elif len(lst)==1 and not i%2:
                A_player+=lst[0]
                return
            if lst[0]>=lst[1] and lst[-1]>=lst[-2]:
                if lst[0]>=lst[-1]:
                    player+=lst[0]
                    lst.pop(0)
                else:
                    player+=lst[-1]
                    lst.pop(-1)
            elif lst[0]>=lst[1] and lst[-1]<lst[-2]:
                player+=lst[0]
                lst.pop(0)
            elif lst[0]<lst[1] and lst[-1]>=lst[-2]:
                player+=lst[-1]
                lst.pop(-1)
            else:
                if (lst[1]-lst[0])>=(lst[-2]-lst[-1]):
                    player+=lst[-1]
                    lst.pop(-1)
                else:
                    player+=lst[0]
                    lst.pop(0)
            i+=1
            if i%2:
                A_player+=player
                recursive(lst,0,i)
            else:
                B_player+=player
                recursive(lst,0,i)
        recursive(lst,0,0)
    return True if A_player>B_player else '平局' if A_player==B_player else False

塔利班

def f352(x):
    def dp(l,r):
        if l==r:
            return x[l]
        else:
            return max(x[l]-dp(l+1,r),x[r]-dp(l,r-1))
    return dp(0,len(x)-1)>=0

回头一看之前的通项是对了，但是递归限制太多，偶数个必定先手不输，输了就copyB走法

def f352(x):
    a= len(x)
    if not a%2 or a==1:
        return True
    dp = [[0] * a for _ in range(a)]
    for l in range(a):
        for r in range(l+1,a):
            dp[l][r]=max(x[l]-dp[l+1][r],x[r]-dp[l][r-1])
    return dp[0][-1] >= 0

Windypper

開始實在想不出來，所以借鑑了思路，然後寫了個recursion的，發現效率低到髮指。。

蒋博文

fan1993423 发表于 2020-3-15 20:50
平局怎么办，还有0分的吗？

平局应该算玩家1赢

永恒的蓝色梦想

昨天的题太难了，今天要不出点简单的把