Codility EvenSums游戏

Question

我正在努力完成难度挑战，以提高我的编程技能。挑战的细节在这里。< br >我也会将问题陈述复制到这里。

偶数和是两个玩家的游戏。玩家被赋予一个由N个正整数组成的序列，并轮流进行。在每个回合中，玩家选择一个非空的切片（连续元素的子序列），使得该切片中的值之和是偶数，然后移除该切片并连接序列的其余部分。第一个不能进行合法移动的玩家输掉比赛。

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

编写函数：

字符串解（向量

给定一个由 N 个整数组成的零索引数组 A，html" target="_blank">返回一个格式为“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]=2 A[1]=5 A[2]=4函数应该返回“NO SOLUTION”，因为没有策略可以保证您获胜。

假设:

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

预期最坏情况时间复杂度为O(N)；预期最坏情况的空间复杂度为O(N)，超出了输入存储(不包括输入参数所需的存储)。输入数组的元素可以修改。

首先，我对问题陈述有一个误解，即为什么在给定的示例中，第一个玩家在第一次移动时不能将4作为偶数范围，所以函数应该返回0,0而不是1,2。

第二，我解决这个问题的想法是计算输入数组中偶数区间的个数，如果数是偶数，那么一号玩家赢了，我应该找到一号玩家可以取的第一个偶数区间。

但是我无法在分配的时间内解决它，并且无法再次参加测试。

这是我尝试的代码：

    string solution(vector<int> &A) {
    int num_even_ranges = 0;
    int sum = 0;
    for (int i = 0; i < A.size(); i++)
    {
        sum += (A[i]%2);
        if (sum % 2 == 0 || A[i]%2 == 0)
        {
            num_even_ranges++;
            sum = 0;
        }
    }
    if (num_even_ranges % 2 == 0)
        return "NO SOLUTION";
    sum = 0;
    int start = 0;
    for (int i = start; i < A.size(); i++)
    {
        sum += A[i];
        if (sum % 2 == 0 && i > start)
        {
            return to_string(start) + "," + to_string(i);
        }

        if (i + 1 < A.size())
        {
            if (A[i] % 2 == 0 && A[i+1] % 2 == 1)
            {
                sum = 0;
                start = i + 1;
            }
        }
    }
}

我对这个问题的解决方案是正确的吗？如果不是，这个有趣问题的正确解决方案是什么？

Answer 1

移动（0,0）是有效的，因为在每个回合中，玩家只能使用和为偶数的子序列进行移动。

"在每个回合中，玩家选择一个非空切片（连续元素的子序列），使得该切片中的值之和为偶数"

注意：每次移动后，我们仅考虑剩余序列的操作/移动

After player1's first move(0,0), the remaining sequence will be [5,3,7,2],
then player2's first move(0,1), the remaining sequence will be [7,2],
then player1's second move(1,0), the remaining sequence will be [7]
Now player 2 is unable to make any legal move! So player 1 win's 

因此这是一个成功的策略！

Answer 2

我得到了Javascript的解决方案，请参考下面的代码

Javascript代码:

function len(obj){
if(obj instanceof Array || typeof obj === "string")
    return obj.length;
else {
    var count = 0;
    for(var i in obj){
        if(obj.hasOwnProperty(i))
        count++;
    }
    return count;
}
}

function check(start, end) {
if (start > end) {
    res = 'NO SOLUTION';
}
else {
    res = start.toString() + ',' + end.toString();
}

return res;
}

function trans(strr){
if (strr =='NO SOLUTION') {
    return [1, -1]
}
else {
   a = strr.split(',');
}

return [parseInt(a[0]), parseInt(a[1])];
}

function solution(A){
odd_list = [];
for(var ind=0; ind<A.length; ind++)
{
    if(A[ind]%2==1) {
        odd_list.push(parseInt(ind));    
    }
}

if (len(odd_list)%2 == 0) {
    return check(0, len(A) - 1);
}

 tempList = odd_list;
 odd_list = [];

 odd_list.push(-1);

 for(var i=0; i< tempList.length; i++) {
     odd_list.push(tempList[i]);
 }

 odd_list.push(len(A));

 var res_cand = [];
 count = odd_list[1];
 second_count = len(A) - 1 - odd_list[odd_list.length-2];
 first_count = odd_list[2]- odd_list[1] - 1;

 if (second_count >= count) {
    res_cand.push(trans(check(odd_list[1] + 1 , len(A) - 1 - count ))); 
 }

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

twosum = first_count + second_count;

if (second_count < count && count <= twosum) {
    res_cand.push(trans(check(odd_list[1] + (first_count - (count -     second_count )) + 1, odd_list[odd_list.length-2] )));
}

count = len(A) - 1 - odd_list[odd_list.length-2];
first_count = odd_list[1];
second_count = odd_list[odd_list.length-2] - odd_list[odd_list.length-3] - 1;

if(first_count >= count) {
    res_cand.push(trans(check( count, odd_list[odd_list.length-2] - 1 )));
}

if (second_count >= count) {
    res_cand.push(trans(check( 0, odd_list[odd_list.length-2] - count - 1)))
}

twosum = first_count + second_count;

if(second_count < count && count <= twosum) {
    res_cand.push(trans(check(count-second_count, odd_list[odd_list.length-3])))
}

cur = [-1, -2];

res_cand =  res_cand.sort(sortFunction);

for(var i= res_cand.length-1 ; i >= 0 ; i--) {
      var row = res_cand[i]; 
      if(row[0] !== -1) {
        cur = row;  
      }
}

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

function sortFunction(a, b) {
if (a[0] === b[0]) {
    return 0;
}
else {
    return (a[0] < b[0]) ? -1 : 1;
}
}

你可以在下面的小提琴链接中得到答案。

https://jsfiddle.net/3ed1kuoj/

Answer 3

关于你的第一个问题，如果第一个玩家拿4（0，0），剩下的数组是：5，3，7，2。然后对手可以拿下3，7，2，第一个玩家将失去，因为剩下的5个是奇数。所以这不是有效的解决方案。