石子游戏,关于索引如何确定的问题

白本羽

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

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

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

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

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

如果 Alice 赢，返回 1 。
如果 Bob 赢，返回 -1 。
如果游戏平局，返回 0 。

输入：aliceValues = [1,3], bobValues = [2,1]
输出：1
解释：
如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ，得到 2 分。
Alice 获胜。

我的代码:

1. 
   
2. class Solution:
   
3.     def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
   
4.         sum_up = []
   
5.         a_score = 0
   
6.         b_score = 0
   
7.         for i in range(len(aliceValues)):
   
8.             sum_up.append(sum([aliceValues[i],bobValues[i]])) # 总体分数的和的序列
   
9.         for a in range(len(sum_up)):
   
10.             try:# pop会导致max空序列的错误,说明程序已经可以结束,直接返回比较分数
    
11.                 maxnum_index = sum_up.index(max(sum_up)) # 最优策略:总是选总体分数最高的,问题在于总体分数最高是可以重复的,比如有100个10是最高的,index只能找第一个,如果不去掉,从右边找也只是重复一遍
    
12.                 a_score += aliceValues[maxnum_index] # alice先手
    
13.                 aliceValues.pop(maxnum_index)
    
14.                 bobValues.pop(maxnum_index)
    
15.                 sum_up.pop(maxnum_index)
    
16.                 maxnum_index = sum_up.index(max(sum_up))
    
17.                 b_score += bobValues[maxnum_index]
    
18.                 aliceValues.pop(maxnum_index)
    
19.                 bobValues.pop(maxnum_index)
    
20.                 sum_up.pop(maxnum_index)
    
21.             except:
    
22.                 if a_score > b_score:
    
23.                     return 1
    
24.                 elif a_score < b_score:
    
25.                     return -1
    
26.                 else:
    
27.                     return 0

复制代码

每次都要pop,效率太差了,但是确定最大值的索引又搞不来,求大佬优化代码

笨鸟学飞

虽然题目和算法看不太懂，但是你如果仅仅需要确定最大值的索引，为何不试试用列表的排序方法？

1. >>> help(list.sort)
   
2. Help on method_descriptor:
   
3. 
   
4. sort(self, /, *, key=None, reverse=False)
   
5.     Sort the list in ascending order and return None.
   
6.    
   
7.     The sort is in-place (i.e. the list itself is modified) and stable (i.e. the
   
8.     order of two equal elements is maintained).
   
9.    
   
10.     If a key function is given, apply it once to each list item and sort them,
    
11.     ascending or descending, according to their function values.
    
12.    
    
13.     The reverse flag can be set to sort in descending order.

复制代码

实例，索引为-1或者0（看你用什么方法）

1. >>> list1 = [1,3,2,4,6,5,8,7]
   
2. >>> list2 = list1[:]
   
3. >>> list.sort(list1, reverse=False)
   
4. >>> list.sort(list2, reverse=True)
   
5. >>> list1
   
6. [1, 2, 3, 4, 5, 6, 7, 8]
   
7. >>> list2
   
8. [8, 7, 6, 5, 4, 3, 2, 1]

复制代码

qq1151985918

这是我自己写的，没比较过效率，供参考

另外，关于这个游戏介绍，仍然有很多我认为的争议点
1.每次都是A先选吗？那么如果数列是奇数个例如3,5,7
  那么先选的总是占据多选的优势
2.分值问题，如果A认为分值为[1,2,3]而B认为分值为[100,200,300]
  即使是奇数数组仍然难以避免输掉，自己选择自己认为的分值，本身就不公平
  当然这种情况只存在代码讨论阶段，意义不大
3.题目中说的最优策略的具体意义是什么？
  如果只是每次都选择自己认为的自己的最高分，那么显然存在第二点的问题
  如果可以选择对手认为的最高分，那么假如 数组A = [1,2,3,4]，数组B = [9,1,2,3]
  那么 A 先选是第一个选索引值为3的4分，还是选索引值为0的1分？
  按照理解似乎是应该选择 1 分
  如果是选择1分，那么对后选的选手又是极度不公平，后选的B可能很难赢，除非出现例2的情况
4.数组中会不会出现0分的存在？如果存在，例如A = [0,0,0,0,1,2,3] B = [3,0,2,0,1,0,0]
  对于代码而言会出现不一样的挑战

1. 
   
2. class Solution:
   
3.     def stoneGameVI(self, aliceValues: "List[int]", bobValues: "List[int]") -> int:
   
4.         if len(aliceValues) != len(bobValues):
   
5.             raise Exception("请输入两相同长度数组")
   
6.         data_start = [1] * len(aliceValues)
   
7.         data_stop = [0] * len(aliceValues)
   
8.         aliceData, bobData = [], []
   
9. 
   
10.         while data_start != data_stop:
    
11.             max_aliceValues = max(aliceValues)
    
12.             max_index_aliceValues = aliceValues.index(max_aliceValues)
    
13.             aliceData.append(max_aliceValues)
    
14.             data_start[max_index_aliceValues] = 0
    
15.             aliceValues[max_index_aliceValues] = 0
    
16.             bobValues[max_index_aliceValues] = 0
    
17. 
    
18.             max_bobValues = max(bobValues)
    
19.             max_index_bobValues = bobValues.index(max_bobValues)
    
20.             bobData.append(max_bobValues)
    
21.             data_start[max_index_bobValues] = 0
    
22.             bobValues[max_index_bobValues] = 0
    
23.             aliceValues[max_index_bobValues] = 0
    
24. 
    
25.             if max_aliceValues == max_bobValues == 0:
    
26.                 break
    
27.             
    
28.         if sum(aliceData) > sum(bobData):
    
29.             return 1
    
30.         elif sum(aliceData) == sum(bobData):
    
31.             return 0
    
32.         else:
    
33.             return -1
    
34. 
    
35. 
    
36. if __name__ == "__main__":
    
37.     s = Solution()
    
38.     print(s.stoneGameVI(aliceValues=[1, 3], bobValues=[2, 1]))
    

复制代码