算法背后的逻辑是什么

Question

我正试图从现实中解决一个问题

“偶数总和”

但是我不能这样做。下面是问题。

即使是总和也是两个玩家的游戏。玩家将获得N个正整数序列并轮流进行。在每个回合中，玩家选择一个非空切片（连续元素的子序列），使得该切片中的值之和是偶数，然后删除切片并连接序列的其余部分。第一个无法做出合法举动的玩家将输掉比赛。

如果你和你的对手玩这场游戏，你想知道你是否能赢，假设你和对手都玩得很好。你先走。

写一个函数：

字符串解（向量

如果给定一个由N个整数组成的零索引数组a，则返回一个格式为“X，Y”的字符串，其中X和Y分别是第一个和最后一个位置（包括最后一个），假设您有获胜策略，则在第一次移动时应移除这些位置以取得胜利。如果有多个这样的获胜切片，则函数应返回具有最小值X的切片。如果存在多个具有最小值X的切片，则该函数应返回最短的切片。如果您没有获胜策略，函数应返回“NO SOLUTION”。

例如，给定以下数组:

A[0] = 4 A[1] = 5 A[2] = 3 A[3] = 7 A[4] = 2

该函数应该返回“1，2”。从位置1到位置2移除一个切片后(5 ^ 3 = 8的偶数和)，剩余的数组为[4，7，2]。然后对手将能够移除(偶数和4的)第一个元素或(偶数和2的)最后一个元素。然后你可以走一步，让数组只剩下[7]，这样你的对手就没有合法的走法，会输。下图显示了一种可能的游戏

请注意，移除切片“2，3”(37 = 10的偶数和)也是获胜的一步，但切片“1，2”的x值较小。

对于以下数组：

A[0]=2a[1]=5a[2]=4

该函数应返回“NO SOLUTION”，因为没有策略可以保证您获胜。

假设：

N是[1..100000]范围内的整数；数组A的每个元素都是[1..1000000000]范围内的整数。复杂性：

预期最坏情况时间复杂度为O(N)；预期最坏情况的空间复杂度为O(N)，超出了输入存储(不包括输入参数所需的存储)。输入数组的元素可以修改。我在网上用python找到了一个解决方案。

def check(start, end):
    if start>end:
        res = 'NO SOLUTION'
    else:
        res = str(start) + ',' + str(end)

    return res

def trans( strr ):
    if strr =='NO SOLUTION':
        return (-1, -1)
    else:
        a, b = strr.split(',')
        return ( int(a), int(b) )


def solution(A):
    # write your code in Python 2.7

    odd_list = [ ind for ind in range(len(A)) if A[ind]%2==1 ] 

    if len(odd_list)%2==0:
        return check(0, len(A)-1)


    odd_list = [-1] + odd_list + [len(A)]
    res_cand = []
    # the numbers at the either end of A are even
    count = odd_list[1]
    second_count = len(A)-1-odd_list[-2]
    first_count = odd_list[2]-odd_list[1]-1
    if second_count >= count:
        res_cand.append(  trans(check( odd_list[1]+1, len(A)-1-count )))

    if first_count >= count:
        res_cand.append(  trans(check( odd_list[1]+count+1, len(A)-1 )))  

    twosum = first_count + second_count
    if second_count < count <= twosum:
        res_cand.append(  trans(check( odd_list[1]+(first_count-(count-second_count))+1, odd_list[-2] )))

    ###########################################
    count = len(A)-1-odd_list[-2]
    first_count = odd_list[1]
    second_count = odd_list[-2]-odd_list[-3]-1
    if first_count >= count:
        res_cand.append(  trans(check( count, odd_list[-2]-1 )))

    if second_count >= count:
        res_cand.append(  trans(check( 0, odd_list[-2]-count-1)) )

    twosum = first_count + second_count
    if second_count < count <= twosum:
        res_cand.append(  trans(check( count-second_count, odd_list[-3])) )



    res_cand = sorted( res_cand, key=lambda x: (-x[0],-x[1]) )

    cur = (-1, -2)
    for item in res_cand:
        if item[0]!=-1:
            cur = item

    return check( cur[0], cur[1] )

此代码有效，我无法理解一个函数到另一个函数的代码和流程。但是，我不明白算法的逻辑。它如何处理并解决问题。这可能是一项漫长的任务，但任何人都可以足够关心向我解释算法。提前致谢。




Answer 1

到目前为止，我已经发现奇数的数量对于找出结果至关重要。特别是计算重要值需要第一个奇数和最后一个奇数的索引。

现在我需要理解比较背后的逻辑，比如“if first_count

更新:嘿伙计们，我找到了我的问题的解决方案，并最终理解了算法的逻辑。

这个想法是基于阵列的对称性。如果阵列是对称的，我们永远也赢不了这场比赛。在这里，对称被定义为中间只有一个奇数，奇数两边的偶数相等的阵列。

如果有偶数的赔率，我们可以直接赢得比赛。

如果有奇数赔率，我们应该始终尝试使数组对称。这就是算法试图做的事情。

现在有两种情况。要么保留最后一个奇数，要么保留第一个奇数。如果你们不明白，我很乐意解释更多。谢谢