[已解决]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]

已修改 如下

1. def fun352(arr):
   
2.     M = len(arr)
   
3.     if M == 1:
   
4.         return True
   
5.     dictionary = dict()#存储形式 (起始，终止):(先手，后手)  起始终止 和切片一致
   
6.     for index in range(0,M-1):
   
7.         A = arr[index]
   
8.         B = arr[index+1]
   
9.         if A < B:
   
10.             dictionary[(index,index+2)]=(B,A)
    
11.         else:
    
12.             dictionary[(index,index+2)]=(A,B)
    
13.     for index in range(3,M+1):
    
14.         for inner in range(0,M+1-index):
    
15.             choose1 = arr[inner]
    
16.             before1 = dictionary[(inner+1,inner+index)][0]
    
17.             after1 = dictionary[(inner+1,inner+index)][1]
    
18.             result1 = (choose1+after1,before1)
    
19.             
    
20.             choose2 = arr[inner+index-1]
    
21.             before2 = dictionary[(inner,inner+index-1)][0]
    
22.             after2 = dictionary[(inner,inner+index-1)][1]
    
23.             result2 = (choose2+after2,before2)
    
24. 
    
25.             if result1[0]>result2[0]:
    
26.                 dictionary[(inner,inner+index)] = result1
    
27.             else:
    
28.                 dictionary[(inner,inner+index)] = result2
    
29.     if dictionary[(0,M)][0]>dictionary[(0,M)][1]:
    
30.         return True
    
31.     else:
    
32.         return False

复制代码

跳转到最佳答案楼层

zltzlt

平局返回 True

TJBEST

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

1. def fun352(arr):
   
2.     M = len(arr)
   
3.     if M == 1:
   
4.         return True
   
5.     dictionary = dict()#存储形式 (起始，终止):(先手，后手)  起始终止 和切片一致
   
6.     for index in range(0,M-1):
   
7.         A = arr[index]
   
8.         B = arr[index+1]
   
9.         if A < B:
   
10.             dictionary[(index,index+2)]=(B,A)
    
11.         else:
    
12.             dictionary[(index,index+2)]=(A,B)
    
13.     for index in range(3,M+1):
    
14.         for inner in range(0,M+1-index):
    
15.             choose1 = arr[inner]
    
16.             before1 = dictionary[(inner+1,inner+index)][0]
    
17.             after1 = dictionary[(inner+1,inner+index)][1]
    
18.             result1 = (choose1+after1,before1)
    
19.             
    
20.             choose2 = arr[inner+index-1]
    
21.             before2 = dictionary[(inner,inner+index-1)][0]
    
22.             after2 = dictionary[(inner,inner+index-1)][1]
    
23.             result2 = (choose1+after1,before1)
    
24.             
    
25.             dictionary[(inner,inner+index)] = max([result1,result2])
    
26.     if dictionary[(0,M)][0]>dictionary[(0,M)][1]:
    
27.         return True
    
28.     else:
    
29.         return False

复制代码

蒋博文

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

复制代码

永恒的蓝色梦想

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

1. class Solution:
   
2.     def PredictTheWinner(self, nums: List[int]) -> bool:
   
3.         if len(nums)&1:
   
4.             length=len(nums)
   
5.             dp=[[0]*length]*length
   
6. 
   
7.             for i in range(length):
   
8.                 dp[i][i]=nums[i]
   
9. 
   
10.             i=length
    
11.             while i:
    
12.                 i-=1
    
13.                 for j in range(i+1,length):
    
14.                     dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
    
15.             
    
16.             return dp[0][-1]>=0
    
17.         else:
    
18.             return True

复制代码

Qiummmmmml

等一下发！

TJBEST

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

ouyunfu

1. def f352(L:list)->bool:
   
2.     def f(a, b):
   
3.         if b-a == 0:
   
4.             return L[a]
   
5.         elif b-a == 1:
   
6.             return max(L[a:b+1])-min(L[a:b+1])
   
7.         x,y,z=f(a+2, b),f(a+1, b-1),f(a, b-2)
   
8.         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]))
   
9.     if len(L)==1 or len(L)==2:
   
10.         return True
    
11.     elif len(L)==3:
    
12.         if L[0]+L[2]>L[1]:
    
13.             return True
    
14.         else:
    
15.             return False
    
16.     elif len(L)==4:
    
17.         if L[0]+L[2]!=L[1]+L[3]:
    
18.             return True
    
19.         else:
    
20.             return False
    
21.     else:
    
22.         return f(0,len(L)-1)>0  
    
23. print(f352([1, 5, 2]))
    
24. print(f352([1, 5, 233, 7]))
    
25. print(f352([i for i in range(30)]))

复制代码

l0stparadise

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

风魔孤行者

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

kinkon

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

1. def f352(n):   
   
2.     a, b = 0, len(n) - 1
   
3.     if not len(n)%2:return True
   
4.     res = []
   
5.     while a < b:        
   
6.         if a + 1 == b:
   
7.             if n[a] > n[b]:
   
8.                 res.append(n[a])
   
9.                 a += 1
   
10.             else:
    
11.                 res.append(n[b])
    
12.                 b -= 1      
    
13.         if n[a] > n[b] and n[a] > n[a+1]:                              
    
14.                 res.append(n[a])
    
15.                 a += 1        
    
16.         elif n[b] > n[a] and n[b] > n[b-1]:            
    
17.                 res.append(n[b])
    
18.                 b -= 1               
    
19.         elif n[a] < n[b] and n[a] < n[a+1]:
    
20.             #if n[a+1] <= n[b] and n[b-1] > n[b]:            
    
21.             if n[a+1] <= n[b-1]:                 
    
22.                 res.append(n[a])
    
23.                 a += 1
    
24.             else:
    
25.                 res.append(n[b])
    
26.                 b -= 1               
    
27.         elif n[b] < n[a] and n[b] < n[b-1]:            
    
28.             if n[b-1] <= n[a+1]:               
    
29.                 res.append(n[b])
    
30.                 b -= 1
    
31.             else:
    
32.                 res.append(n[a])
    
33.                 a += 1               
    
34.         elif n[a] > n[b] and n[a] < n[a+1]:            
    
35.             if n[a+1] <= n[b-1]:                 
    
36.                 res.append(n[a])
    
37.                 a += 1
    
38.             else:
    
39.                 res.append(n[b])               
    
40.                 b -= 1               
    
41.         elif n[b] > n[a] and n[b] < n[b-1]:            
    
42.             if n[b-1] <= n[a+1]:                 
    
43.                 res.append(n[b])
    
44.                 b -= 1
    
45.             else:
    
46.                 res.append(n[a])
    
47.                 a += 1               
    
48.         elif n[a] < n[b] and n[a] > n[a+1]:            
    
49.             if n[b] <= n[b-1]:                 
    
50.                 res.append(n[a])
    
51.                 a += 1
    
52.             else:
    
53.                 res.append(n[b])
    
54.                 b -= 1               
    
55.         elif n[b] < n[a] and n[b] > n[b-1]:            
    
56.             if n[a] <= n[a+1]:                 
    
57.                 res.append(n[b])
    
58.                 b -= 1
    
59.             else:
    
60.                 res.append(n[a])
    
61.                 a += 1
    
62.         else:            
    
63.             if n[a] > n[b]:
    
64.                 res.append(n[a])
    
65.                 a += 1
    
66.             else:
    
67.                 res.append(n[b])
    
68.                 b -= 1                                                
    
69.     c = sum([res[i] for i in range(len(res)) if not i % 2])
    
70.     d = sum([res[i] for i in range(len(res)) if i % 2])
    
71.     if c > d: return True
    
72.     return False

复制代码

TJBEST

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

546623863

1. def fun352(scores:list):
   
2.     if(len(scores) == 0):
   
3.         return None
   
4.     elif(len(scores) == 1):
   
5.         return True
   
6.     player1 = 0
   
7.     player2 = 0
   
8.     Sum = sum(scores)
   
9.     def choice(scores:list, Cur:int, Next:int):
   
10.         length = len(scores)
    
11.         if(length == 0):
    
12.             return None
    
13.         elif(length == 1):
    
14.             return 0
    
15.         elif(1 < length < 4):
    
16.             return scores.index(max(scores[0],scores[-1]))
    
17.         if(scores[1] >= scores[-2]):
    
18.             if((scores[1] + min(scores[0],scores[-1]) > scores[-2] + max(scores[0],scores[-1])) or ((scores[1] + Next) >= Sum/2)):
    
19.                 return -1
    
20.             else:
    
21.                 return scores.index(max(scores[0],scores[-1]))
    
22.         else:
    
23.             if((scores[-2] + min(scores[0],scores[-1]) > scores[1] + max(scores[0],scores[-1])) or (scores[-2] + Next >= Sum/2)):
    
24.                 return 0
    
25.             else:
    
26.                 return scores.index(max(scores[0],scores[-1]))
    
27.    
    
28.     while(scores != []):
    
29.         index = choice(scores, player1, player2)
    
30.         player1 += scores.pop(index)
    
31.         index = choice(scores, player2, player1)
    
32.         if(index == None):
    
33.             break
    
34.         else:
    
35.             player2 += scores.pop(index)
    
36.     if(player1 > player2):
    
37.         return True
    
38.     elif(player1 < player2):
    
39.         return False
    
40.     else:
    
41.         return "平局"

复制代码

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

Unicorn#

1. def solve(s):
   
2.     def f(l, r):
   
3.         if r - l == 0:
   
4.             return s[l]
   
5.         elif r - l == 1:
   
6.             return max(s[l:r+1])-min(s[l:r+1])
   
7.         a = f(l+2, r)
   
8.         b = f(l+1, r-1)
   
9.         c = f(l, r-2)
   
10.         return max(
    
11.             min(a - s[l+1] + s[l],
    
12.                 b - s[r] + s[l]),
    
13.             min(b - s[l] + s[r],
    
14.                 c - s[r-1] + s[r])
    
15.             )
    
16.     return f(0, len(s)-1) > 0

复制代码

fan1993423

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

小python1

马上发

fan1993423

1. A_player,B_player=0,0
   
2. def fun352(lst):
   
3.     if not len(lst):return '平局'
   
4.     elif len(lst)==1 and lst[0]>0:return True
   
5.     elif len(lst)==1 and lst[0]==0:return '平局'
   
6.     elif len(lst)==2:
   
7.         if lst[0]==lst[1] :return '平局'
   
8.         else:return True
   
9.     else:
   
10.         def recursive(lst,player,i):
    
11.             global A_player,B_player
    
12.             if len(lst)==1 and i%2:
    
13.                 B_player+=lst[0]
    
14.                 return
    
15.             elif len(lst)==1 and not i%2:
    
16.                 A_player+=lst[0]
    
17.                 return
    
18.             if lst[0]>=lst[1] and lst[-1]>=lst[-2]:
    
19.                 if lst[0]>=lst[-1]:
    
20.                     player+=lst[0]
    
21.                     lst.pop(0)
    
22.                 else:
    
23.                     player+=lst[-1]
    
24.                     lst.pop(-1)
    
25.             elif lst[0]>=lst[1] and lst[-1]<lst[-2]:
    
26.                 player+=lst[0]
    
27.                 lst.pop(0)
    
28.             elif lst[0]<lst[1] and lst[-1]>=lst[-2]:
    
29.                 player+=lst[-1]
    
30.                 lst.pop(-1)
    
31.             else:
    
32.                 if (lst[1]-lst[0])>=(lst[-2]-lst[-1]):
    
33.                     player+=lst[-1]
    
34.                     lst.pop(-1)
    
35.                 else:
    
36.                     player+=lst[0]
    
37.                     lst.pop(0)
    
38.             i+=1
    
39.             if i%2:
    
40.                 A_player+=player
    
41.                 recursive(lst,0,i)
    
42.             else:
    
43.                 B_player+=player
    
44.                 recursive(lst,0,i)
    
45.         recursive(lst,0,0)
    
46.     return True if A_player>B_player else '平局' if A_player==B_player else False

复制代码

塔利班

1. def f352(x):
   
2.     def dp(l,r):
   
3.         if l==r:
   
4.             return x[l]
   
5.         else:
   
6.             return max(x[l]-dp(l+1,r),x[r]-dp(l,r-1))
   
7.     return dp(0,len(x)-1)>=0

复制代码

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

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

复制代码

Windypper

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

蒋博文

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

平局应该算玩家1赢

永恒的蓝色梦想

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