Codility - Iota 2011 - shortest_adj_seq

题目见 https://codility.com/demo/take-sample-test/iota2011/

思路比较明显：根据给出数据，构造无向图，求出起点到终点的最短路径即可。

显然Dijkstra算法，每条边的长度为1，可以根据此优化，一层一层往后遍历，这样就不需要单独记录每个点与起点的距离，只需记录当前是第几层，否则的话在最大的数据集上会超时（可能是跟我用了好几个map和set有关，不过有轮子可用就不想自己造了…… ）

代码见 https://github.com/phiphy/codility/blob/master/shortest_adj_seq-iota_2011.cpp

Codility - Theta 2011 - gas stations

题目见 https://codility.com/demo/take-sample-test/theta2011/

比较简单的题，思路很直接，贪心法，往后扫描，在当前的加气站如果比后面的加气站便宜的话就尽量多加。只是边界条件要特别小心，很容易出错。

代码见 https://github.com/phiphy/codility/blob/master/gas_stations-Theta_2011.cpp

Codility - Epsilon 2011 - minfuds

题目见 https://codility.com/demo/take-sample-test/epsilon2011/

最近比较忙，偶尔几天才能抽出一个小时左右来想题。而这个题又一直有个小问题，只能拿80分，找了很久没找到，很苦恼。今天突然想到自己构造数据来检查，哈哈，终于一个小时内就找到问题了，修改一提交，100！

由于n条直线最多有O(n^2)的交点，而题目要求的时间复杂度是O(nlgn)，明显暗示就是需要排序…… 所以，首先根据斜率对直线排序，斜率相同的情况下再按截距反向排。从前往后扫描排序好的直线，求出相邻直线的交点，如果该交点比前一个交点的x值还要小，则需要重新计算交点 （这个画个图最清楚了，我很懒就不画了，哈哈），求出的是定义maximum的所有交点。再从后往前扫描排序好的直线，得出定义minimum的所有交点。最后同时对两部分交点扫描，求出每个交点对应在另外一部分的值，计算y值之差后更新全局变量。

说得很乱了，要睡觉了，困。。。

代码见 https://github.com/phiphy/codility/blob/master/minfuds-Epsilon_2011.c

如果有人看到代码不懂的话，可以联系我，不过估计是没有的……

声援朱令，白宫请愿

https://petitions.whitehouse.gov/petition/invest-and-deport-jasmine-sun-who-was-main-suspect-famous-thallium-poison-murder-case-victimzhu-lin/Rd8C54p1

望法网恢恢，疏而不漏，中国能早日步入法制社会，民主社会。民主、科学还需要再喊多少年呢？

Codility - Delta 2011 - min_abs_sum

题目见 https://codility.com/demo/take-sample-test/delta2011/

这是一道很有意思的题目。有N个数的数组A，令有N个数的数组S，S中元素取值为1或-1，则定义 val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }| ，现在要求 val(A, S) 的最小值。很显然，本质是将数组A分成两部分，使得两部分的差最小。不幸的是，数组均分问题是很困难的，其实是NPC的，而题目要求时间复杂度为 O(N*max(abs(A))²) ，并且空间复杂度为 O(N+sum(abs(A))) ，似乎不可能实现…… 但是呢，题目给定了A中元素的取值范围是 [-100, 100] 中的整数，利用这个性质，就能极大地降低复杂度。

首先对数组做处理，负数转换成对应正数，零去掉，计数排序统计有多少个不同元素及其对应个数，并累加所有数的和sum，不妨记b=sum/2，不同元素个数为m，则目标转换为在m个不同元素中挑出若干个元素（每个元素可以重复多次，但少于它们的出现次数），使得它们的和不大于b并尽量接近。到了这里，应该有点熟悉的感觉了吧。对了，其实这就是0-1背包问题！

记 f[i][j] 为只允许选前 i 个元素，总和不超过 j ，则有 f[i][j] = max { f[i-1][j], f[i][j-D[i]]+D[i] }, 其中 D[i] 为第 i 个元素对应的值。由于每种元素的数量不是无穷多，因此对每个 f[i][j] ，都需要记录第 i 种元素的消耗数量，保证小于该元素的出现次数。

代码见 https://github.com/phiphy/codility/blob/master/min_abs_sum.c

Keywords: 0-1 knapsack

Codility - Gamma 2011 - count_palindromic 回文子串

这是一道Codility上的题目，见 https://codility.com/demo/take-sample-test/gamma2011/ 大意就是给定一个字符串，求出它的所有长度大于2的回文子串的个数。这与求字符串的最长回文子串的问题是等价的。

首先想到的就是遍历字符串的所有长度大于2的子串（共有2+3+...+n-1 = (n+1)(n-2)/2个），对每个子串判断是否为回文串，时间复杂度为O(n^3)

然后，我们注意到，所有的回文子串都有一个中心位置，而对于长为n的字符串，能作为回文子串中心位置的只有2n-1种可能（对于本问题，其实只有2n-3种可能，需要去除第一个和最后一个字符所在的位置），因此，只需遍历这些可能的位置，找出以该位置为中心的回文子串的数目，时间复杂度是O(n^2)。

看起来，似乎这种方法是最优的，毕竟，有2n-3个位置需要判断，而每次判断的时间复杂度是O(n)，因此最终时间复杂度是O(n^2)，看起来是不能再改善了。

但是呢，世界就是这么奇妙，就像神奇的KMP字符串匹配算法一样，居然能把字符串匹配的时间复杂度做到O(n+m)。对本问题，其实是存在O(n)时间复杂度的算法的！

为了统一处理奇数长度和偶数长度的回文串，我们在每个原字符串的每个字符之间加上一个分隔符#，并且在字符串开头加上一个终结符$，因此，当原字符串是baababa时，转换后的字符串是$#b#a#a#b#a#b#a#，这样，当回文中心是#字符时，回文长度为偶数；当回文中心不是#时，回文长度为奇数。

该算法的基本思想就是扫描处理后的字符串S，记录以每个字符为中心时的最长回文串，同时更新全局的最长回文串记录。描述如下：

待处理字符串为S，长度为N

P为长为n的数组，P[i]记录以字符i为中心的最长回文串的半边长度加1（回文串长度为 2*(P[i]-1) + 1）

K为之前的回文串到达的最右位置，j为该回文串的的中心位置

for i = 1..len(s)-1

    初始化P[i]

    逐渐增加P[i]，直至不满足回文串条件

    统计该回文串中回文数目

    if i+P[i] > K

        K = i + P[i]

        j = i

但看描述，似乎与O(n^2)的算法一样，但该算法的关键是初始化P[i]，如果每次循环之前P[i]能尽量大，那么每次循环的比较次数就很少，从而降低了复杂度。（具体时间复杂度分析比较复杂，本文不作精确分析）

那么如何确定一个较大的P[i]值呢？

不妨假设当前扫描到第i个字符，根据全局K和j值，我们有：

index            2j-i       j       i        K

char/str     A   S[i]  B  S[j]  B  S[i]  A  S[K]

由于以j为中心的回文串的最右位置为K（不包含），当K大于i的情况下，不妨假设i与K之间的字符串为A，j与i之间的字符串为B，那么根据回文串性质有2j-i与j之间字符串为B，2j-i之前存在字符串A。

可以利用2j-i与i位置的对称性，不妨假设P[2j-i] = x，那么说明B字符串的前x-1个字符与A字符串的后x-1个字符相同，因此对于i来说，只需要从i+x开始判断即可，如果i+x大于K，那么则从K开始递增。

具体代码（针对Codility题目）如下，亦可参见 https://github.com/phiphy/codility/blob/master/count_palindromic_slices.c

int imin(int x, int y) { return x < y ? x : y; }

int solution ( char *t ) {

    if (!t)

        return 0;

    int n = strlen(t);

    if (n < 2)

        return 0;

    int i, j, k, r = 0;

    int m = n + n + 3;

    char *s = (char *)malloc(sizeof(char) * m);

    int *p = (int *)malloc(sizeof(int) * m);

    for (s[0] = '$', s[1] = '#', i = 0, j = 2; i < n; ++i) {

        s[j++] = t[i];

        s[j++] = '#';

    }

    s[j] = '\0';

    for (k = 0, i = 1; i < m-1; ++i) {

        p[i] = k > i ? imin(p[2*j-i], k-i) : 1;  // update p[i], as large as possible

        while (s[i+p[i]] == s[i-p[i]])

            ++p[i];

        if (p[i] > 1) {

            r += (p[i]/2 - (s[i]!='#'));

            if (r > 100000000) {

                r = -1;

                break;

            }

        }

        if (p[i]+i > k) {

            k = p[i] + i;

            j = i;

        }

    }

    free(s); s = NULL;

    free(p); p = NULL;

    return r;

}

听说这道题也可以用后缀数组解决，不过我暂时还不懂后缀数组，这段时间研究一下。

生成字符串的全排列

递归的方法比较简单，略过。

非递归方法首先需要将字符串排序，然后循环查找下一个比当前字排列大的字符串。举例来说，当前字符串是1 5 7 6 4 3 2，我们知道下一个应该是1 6 2 3 4 5 7，怎么找到的呢？

从右边往左扫描，找到第一个比左边字符大的字符，本例中我们找到了7，然后将7左边的字符（5）与与右边的字符（6 4 3 2）比较，找到（6 4 3 2）中比5大的字符，本例中是6，将5与6交换，然后反转7右边的字符（将5 4 3 2反转成2 3 4 5）。

思路清楚之后，程序就很简单了，并且能处理重复字符的情况（如果用递归的方法，需要检测重复字符进行处理）。

void permutation(char *s, int n)

{

    std::sort(s, s + n);

    printf("%s\n", s);

    int i, j;

    while (1) {

        for (i = n-1; i>=1 && s[i]<=s[i-1]; --i)

            ;

        if (i == 0)

            break;

        for (j = n-1; j>i && s[j]<=s[i-1]; --j)

            ;

        std::swap(s[i-1], s[j]);

        for (j = n-1; i < j; ++i, --j)

            std::swap(s[i], s[j]);

        printf("%s\n", s);

    }

}