algorithm - 算法背后的逻辑是什么

Question

我正试图从可容忍性中解决一个问题

"Even sums"

但是我做不到。这是下面的问题。

偶数是两个玩家的游戏。给玩家一个 N 个正整数的序列，并轮流轮流进行。在每一轮中，玩家选择一个非空切片(连续元素的子序列)，使该切片中的值之和为偶数，然后移除该切片并连接序列的其余部分。第一个无法做出合法 Action 的玩家输掉了游戏。

你和你的对手玩这个游戏，你想知道你是否能赢，假设你和你的对手都玩得最好。你先动。

写一个函数:

string solution(vector< int>& A);

给定一个由 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]，这样你的对手就没有合法的下法并且会输。 following picture 上显示了一种可能的游戏

请注意，删除切片“2,3”(3 + 7 = 10 的偶数和)也是一个获胜步骤，但切片“1,2”的 X 值较小。

对于下面的数组:

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

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

假设:

N为[1..100,000]范围内的整数；数组 A 的每个元素都是 [1..1,000,000,000] 范围内的整数。复杂性:

预期的最坏情况时间复杂度为 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 >= count”和“second_count < count <= twosum”。

更新:大家好，我找到了问题的解决方案，终于理解了算法的逻辑。

这个想法在于数组的对称性。如果阵列是对称的，我们永远无法赢得比赛。这里对称的定义是这样的数组，中间只有一个奇数，奇数两边的偶数相等。

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

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

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