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挑戰 - 爲什麼這個解決方案有效？

回答

相關問題