2008年12月19日星期五

GreaseMonkey脚本之“校内共同的好友”

之前看到吴天际同学写了一个"校内共同的好友"的GreaseMonkey脚本,可惜后来接口变了,于是我今天写了一个新的。
http://userscripts.org/scripts/show/38905
目前这个版本还很粗糙――
可以改进的地方有:
1、通信:不用page+1来抓取下一页好友列表,而是通过页面元素计算最后一页的页码,这要可以少抓一页
2、计算:两个集合求交集,预先对一个集合建索引,则复杂度O(n)
3、缓存:可以将部分已经计算过的内容压缩后放到cookie中,减少服务器计算开销(但是会增加通信开销因为cookie总是在HTTP Request Header中带着跑)
4、界面:显示共同好友的小图标

2008年12月11日星期四

从有序数组中找两个数求和等于某个给定的数

问题:
给一个正整数c,一个升序的正整数数组a=a1,...,an,找ai, aj使得ai+aj=c
算法:
i=1
j=n
while i<=j
{
case ai+aj==c, return true
case ai+aj<c, i++
case ai+aj>c, j--
}
return false
思路:
造一个方阵bij=ai+aj,则b对称,且bij<c蕴含bij左上区域都<c,只能向右或向下找,而我们从右上角开始,因此只能向下找。j++后,指针又在可能区域的右上角了。
正确性证明:
首先,算法显然至多n步后返回。
如果算法返回true,则显然ai+aj=c成立。
如果算法返回false,来证不存在bij满足bij=c。
由对称性,只需要证明bij!=c对于任意i<=j成立即可。
归纳法,显然当n=1时成立,若n-1时成立,来看n>=2时。
因为算法返回false,且n>=2,因此至少循环第一次b1n!=c,那么有两种情况
b1n<c,则b1j<c对任意j=1,...,n成立,n阶上三角去掉了第一行,剩下的是n-1阶的上三角,指针移到(2,n),是这个n-1阶上三角的右上角。
b1n>c,则bin>c对任意i=1,...,n成立,n阶上三角去掉了最后一列,剩下的还是n-1阶的上三角,指针移到(1,n-1),还是这个n-1阶上三角的右上角。
故由归纳假设,n时成立。

2008年12月1日星期一

topK

设U是一个全序集,A是U上的一个数组,长度为n。topK算法把最大的K个元素放在数组A的最前面。
思路类似快速排序,每次划分后只递归topK一边,而不是两边:
划分:在A中随便取一个pivot放中间,把大于等于pivot的数放左边,小于pivot的数放右边。设划分后pivot的下标为p。
如果p=K,太好了,左边的K个数刚好就是最大的。
如果p<K,我们还需要更多的比较大的数,从右侧的数中跑topK-p。
如果p>K,说明我们一下找多了,需要精益求精,在左侧的数中跑topK。
用C++写的,注意其中需要T重载一些比较运算符:
template<typename T>
void top(T *a, size_t n, size_t k) {
    if (n <= 0 || k <= 0 || n <= k) {
        printf("top need n>k! n=%d k=%d\n", n, k);
        throw "";
    }
    while (true) {
        int j = rand() % n;
        T pv = a[j];
        swap(a, 0, j);
        size_t p = 1;
        for (size_t i = 1; i < n; i++) {
            if (a[i] >= pv) {
                swap(a, i, p);
                p++;
            }
        }
        j = p - k;
        if (j < 0) {
            a = a + p;
            n = n - p;
            k = k - p;
        } else if (j > 0) {
            while (a[--p] == pv && p>k)
                ;
            swap(a, 0, p);
            if (p == k)
                break;
            else
                n = p;
        } else
            break;
    }
}
边界条件的处理略微有些复杂,我搞了好久才搞好。为了保证循环有限步完成,必须要让问题的规模确实减小。
为了加速处理所有数都相同的输入,p>K时,在不破坏正确性的、且不增加复杂度的情况下p尽量取小些。