[算法]几个有趣的关于数列的O(1)空间O(n)时间小算法

1 数列L中有n个整数。其中有k个数字出现了两次，1个数字出现了一次(所以n=2k+1)。找出只出现一次的那个数字。
解： 将n个数字xor以后，重复出现的就会消失。剩下的就是只出现一次的。

2 数列L中有n个数。已知其中有一个数字出现了至少 n/2+1次。找出这个数字。
解： 用链表存储这n个数字。p指向当前考察的数字。p从链表头开始。如果p和p->next的数字相同，p=p->next，如果不同，则将p和p->next一同从链表中删除。当p->next是链表尾的时候，p就是所求数字。

3 数列L中有n=2k个数字a1,a2,...,an,b1,b2,...,bn。将其变换为a1,b1,a2,b2,...,an,bn。可以将这个问题理解为扑克里的洗牌。
解： 很难的题目。这里有一篇论文http://webhome.cs.uvic.ca/~jellis/perfect.html。

[Linux]Wine的一点使用经验

因为实在受不了Adacious的频繁出问题而分外想念win下的foobar，我装了wine。现在wine加上foobar运行的非常良好。下面记一下安装和使用wine的时候的一些问题。

安装

ubuntu上很简单:

apt-get install wine

中文支持

安装了wine以后，在~/.wine底下会有一个driver_c目录，这里是wine心目中的C盘。你可以之后再映射过来正真的D盘阿E盘阿，但这个C盘无法改变(至少我是没找到)。在这个driver_c目录下， 有一个windows/font 目录。可是刚刚装完的时候这里是空的。你可以把你喜欢的windows字体拷过来或是做上符号连接，比如重要的英文字体tahoma.ttf 以及重要的中文字体simsun.ttf。然后键入"wine regedit"调用wine的注册表，修改[HKEY_LOCAL_MACHINE\Software\Microsoft\Windows NT\CurrentVersion\FontSubstitutes]。把MS Shell Dlg 以及MS Shell Dlg2的键值由默认的tahoma改为simsun，这样就可以正确的显示中文了

程序中字体过小

这是由于dpi值设置的不够大。可以选择在winecfg的Graphics标签里调整dpi值大小(默认是96)。或者继续wine regedit修改[HKEY_CURRENT_CONFIG\Software\Fonts]里的LogPixels键值。LogPixels默认是60(十六进制,也就是十进制的96)。比如我就调整到了120。这样程序里的对话框以及文件选择框之类的的字就足够大了。

菜单/状态栏/消息框中的字体依然过小

调整过dpi之后，有可能发现程序里的字是大了，但是菜单之类的字体还是很小。这个问题我google了很久 "Wine", "MenuFont","tiny"之类，看到一些人问但是都没有答案。早先版本的wine可以通过设置win.ini里MenuFontSize等来解决。但新版本的不可以。下午参考着wine源码搞定了这个问题。原来wine会从注册表当中直接读取MenuFont/StatusFont/MessageFont信息。比如MenuFont信息既包括了字体也包括了大小。这几个键值在"[HKEY_CURRENT_USER\Control Panel\Desktop\WindowMetrics"]。但是是用二进制的形式存储的。所以你在user.reg当中可以找到"MenuFont"=hex:f5,ff,ff,ff...这样的字串。如果需要把字体调大，可以把第一个f5弄小一点，比如我调到f2就很好了。