确定第一个玩家是否可以赢得比赛

问题描述 投票:0回答:1

考虑以下游戏。有一系列正数。每个玩家依次移除一个切片(连续的元素序列),使得它的总和是偶数。输掉的球员是无法移动的球员。对于[4, 5, 3, 7, 2]示例,获胜策略(对于第一个玩家)是删除[5,3]slice。您需要确定第一个玩家是否有获胜动作(如果是,则返回slice_startslice_end索引)。

时间/空间复杂性:O(n)

我想出的一件事就是从左到右计算累积和,反之亦然。在[4,5,3,7,2]示例中我们得到:acc_l = [4,9,12,19,21]acc_r = [21,17,12,9,2]

所以我几乎可以肯定这两个辅助阵列应该派上用场,但我无法完全理解它。

我很乐意帮忙!

arrays algorithm data-structures computer-science
1个回答
-2
投票

计算整个数组的总和。检查它是偶数还是奇数。还要计算数组中偶数和奇数的数量(一次通过)。这应该可以帮助你找到答案。

© www.soinside.com 2019 - 2024. All rights reserved.