罗杰斯的博客

最近在为找工作做些准备，做了些题看了些算法，其中有一个程序员面试题精选100题好像是比较有名的（现在还没出满100题），我把自己的答案放上来，如果有人来讨论一下那更好了。我是用的C来做题，有些C++ only的题就跳过了。还有一些别的算法比如RMQ的st解法，kmp等代码都在里面。打包下载地址在这里jingxuan.tar.gz。

顺便有几个算法想单独地说一下：

1. O(n)时间求最长回文。主要思路就是从第一个字符开始扫描，记录下以当前字符结尾的最长回文长度。代码如下

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

int
find(const char *s)
{
    if (!s)
        return -1;

    int lens = strlen(s);

    int i, same = 1, pre = 1, max = 0;
    for (i = 1; i < lens; i ++) {
        int l = 0, s1;
        s1 = i - pre - 1;
        if (s1 >= 0 && *(s + s1) == *(s + i))
            l = pre + 2;

        if (l == 0)
            l = *(s + i - 1) == *(s + i) ? 2 : 1;

        if (*(s + i) == *(s + i - 1))
            same += 1;
        else
            same = 1;

        s1 = l > same ? l : same;
        if (s1 > max)
            max = s1;

        pre = s1;
    }

    return max;
}

int
main(int argc, char **argv)
{
	printf("%d\n", find("aaa"));
	printf("%d\n", find("goooog"));
	printf("%d\n", find("guouyy"));

	return 0;
}

2. 怎么在O(n)的时间，O(1)的空间找出一串数字中两个不同的只出现一次的数字（别的都出现两次）。这题普遍一点的解法是用位数组，不过还可以考虑把整个数组分成两个子数组，每个分别含有一个只出现一次的数字。代码如下

#include <stdio.h>
#include <assert.h>

int n1, n2;

int
find_once(int array[], int length)
{
    assert(length > 0);
    assert(array != NULL);

    int all = 0, pos = 0, i = 0;
    unsigned int tmp;

    for (i = 0; i < length; i ++)
        all ^= array[i];
    assert(all != 0);

    tmp = (unsigned int)all;
    pos = (tmp - (tmp & (tmp - 1)));

    for (i = 0; i < length; i ++) {
        if (array[i] & pos != 0)
            n1 ^= array[i];
        else
            n2 ^= array[i];
    }

    return 0;
}

int
main(int argc, char **argv)
{
    int a[10] = {1, 2, 1, 2, -1, -1, 3, 3, 0, -4};

    find_once(a, 10);
    printf("%d %d", n1, n2);

    return 0;
}

3. 全排列、组合、幂集算法，分重复不重复两种情况（待添加）

4. 后缀数组（待添加）

5. kmp算法（见上一篇博文）