Codility挑战 - 为什么这个解决方案有效？

给定一串数字，计算任何回文的字形的子字数（一致的子序列）。

实施例：

对于输入字符串 “02002” 的结果应该是11，即：

“0”， “2”， “0”， “0”， “2”，“00 ”， “020”， “200”， “002”， “2002”， “02002”

我可以看到下面的作品是解决办法，但我不明白为什么。特别是我不明白内部循环的重点。任何人都可以解释这背后的逻辑吗？

#include <stdlib.h> 
#include <string.h> 
#include <stdio.h> 

#define M 1000000007 
#define COLORS 10 
#define SUBSETS (1 << (COLORS)) 

int solution(char *S) { 
    int len, result; 
    int *values; 
    int v, idx, middle, mask; 

    result = 0; 
    values = calloc(SUBSETS, sizeof(int)); 
    //new_values = calloc(SUBSETS, sizeof(int)); 
    len = strlen(S); 
    mask = 0; 

    for (idx = 0; idx < len; idx++) { 
     v = S[idx] - '0'; 
     mask ^= (1 << v); 
     values[mask^(1 << v)] += 1; 
     result = (result + values[mask]) % M; 
     for (middle = 0; middle < COLORS; middle++) { 
      result = (result + values[mask^(1 << middle)]) % M; 
     } 
    } 
    return result; 
}

更多详情如果需要：https://codility.com/programmers/task/winter_lights/。

来源

2017-05-05 Marko

时间来学习如何调试......顺便说一句，我可以看到的唯一的回文是'“2002”'... – LPs

@LPs，我调试它多次，但仍无法理解为什么它的工作原理。然后再读这个问题，它是回文的一个字母。 – Marko

对于要算i使得灯从i到idx可以形成回文每个idx。这意味着每种类型的光源都有偶数，或者除了一个（位于回文中间）以外，还有偶数个所有光源。

代码使用特技计数i，以避免为O（n^2）的行为。在处理索引为idx的光之后，阵列values对于每个m包含i<idx的数量，使得从0到i的光序列包含每个光的偶数或奇数（取决于m的位）。因此，例如，包含values[3]灯初始序列的数目（最多idx具有奇数个灯0和1，且偶数个其他灯）。

利用这种阵列中，在idx计数终了的混洗回文很容易：如果掩模高达idx是mask，然后用偶数所有灯的回文的数量是相同的，与左序列的数目相同的面具（即：values[mask]）。类似地，除了与奇数一个光（middle）的具有偶数个的光的回文的数量是相同的，与掩膜mask^(1<<middle)左序列的数目。

来源

2017-05-05 09:53:27

您能否澄清一下：例如，值[3]包含灯的初始序列的数量（最多为idx，灯号0和1为奇数，其他灯号为偶数）？ – Marko

3 = 0b00000011。位0和1被设置。 –

我还没有得到这个角色，为什么这是真的：如果面膜达IDX是面膜，然后用偶数所有灯光的回文的数量是一样的左序列具有相同的掩模数（即：values [mask]） – Marko

Codility挑战 - 为什么这个解决方案有效？

回答

相关问题