LeetCode 287. Find the Duplicate Number | 智商被碾压!

看了LeetCode上牛人的解答,感觉我的智商被碾压了~ 原题 Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. 给定一个包含n+1个整数的数组nums,该数组中的每个整数都在[1,n]的范围内,假设数组中只有一个数是重复的,找到那个重复的数。 Note|提示: You must not modify the array (assume the array is read only).|
Continue reading LeetCode 287. Find the Duplicate Number | 智商被碾压!

LeetCode #4. Median of Two Sorted Arrays

题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/ 参考文献: 求两个有序数组的中位数-算法导论 求两个有序数组的中位数或者第k小元素 思路: 实在是脑子转不过来,看了一下解法,然后就把自己的理解讲一下吧。 有两个规律需要说下: 1.在某个数列头尾删去相同数量的元素,其中位数是不变的。比如[1,2,3,4]删去1和4. 2.如果两个数列的中位数是m1, m2,那么合并后的数列的中位数的值肯定在[m1,m2]范围内。 既然题目是要Log级别的复杂度,就要想到要用折半法把问题的规模降低…举个例子,假设有[1,2,4,6,6,8]和[1,5,7,8,10,25,36]两个数列,很容易算出他们的(前序 )中位数分别是4和8,而他们合并后的中位数的值在[4,8]之间。 然后可以删去无用的值,[1,2]与[10,25,36]. 但由于规律1的限制,如果后面删了3个的话,合并后删减的数列会发生变化(本例中奇偶性都变了),我们只能删去min(2,3)=2个元素…这种删值从理论上讲就是折半了,然后搞一波递归就行了。 最最最基本的思路如下:

由于题设里面俩数组是不等长的,所以里对其中某个数组n<=2时处理方法需要注意… 代码:

 

Glickman 的ELO算法

Glickman的ELO算法被搬到众包中实现,可以参考这篇 Bashir, M., Anderton, J., Wu, J., Golbus, P. B., Pavlu, V., & Aslam, J. A. (2013). A Document Rating System for Preference Judgements. In Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval (pp. 909–912). New York, NY, USA: ACM. http://doi.org/10.1145/2484028.2484170 但是文章里算法描述的部分似乎有写错的地方,可能是作者不小心,把公式(7)的分母部分写错了(原文中的字母j没有换成自己的B)~ Glickman的原文是: Glickman, M. E. (1999). Parameter
Continue reading Glickman 的ELO算法

组合 递归

荒废计算机太久了,以至于这么简单一个问题想了我大半天,其实就是数组求组合输出的方法,写下此日志提醒自己不能忘了老本! 题目的话大概可以这样表述 给出一个数据A={a_0,a_1,a_2…a_n}(其中n可变),打印出该数值元素的所有组合 需要使用递归的方法解决比较好,分而治之 给一大团数据{a0,a1, a2, …, an}: 1. 如果就剩一个元素的话,我就输出它,结束; 2.不输出a0,把除了我之外的余下一团交由递归处理; 3.要输出a0自己,然后余下一团交由递归处理; 其中case 3里面需要注意下一个递归要记住a0是要输出的,所以实践起来就是带了个前缀一样的东西记住。感觉这种排列组合的问题应该也可以用栈来解决,但归根结底还是分治。 用Python随意写了一个:

测试输出:

 

KM算法 详解+模板

本文转载自:http://blog.sina.com.cn/s/blog_691ce2b701016reh.html   先说KM算法求二分图的最佳匹配思想,再详讲KM的实现。 【KM算法求二分图的最佳匹配思想】 对于具有二部划分( V1, V2 )的加权完全二分图,其中 V1= { x1, x2, x3, … , xn }, V2= { y1, y2, y3, … , yn },边< xi, yj >具有权值 Wi,j 。该带权二分图中一个总权值最大的完美匹配,称之为最佳匹配。   记 L(x) 表示结点 x 的标记量,如果对于二部图中的任何边<x,y>,都有 L(x)+ L(y)>= Wx,y,我们称 L 为二部图的可行顶标。 设 G(V,E) 为二部图, G'(V,E’) 为二部图的子图。如果对于 G’ 中的任何边<x,y> 满足, L(x)+ L(y)== Wx,y,我们称 G'(V,E’) 为
Continue reading KM算法 详解+模板

浅谈PCA 人脸识别

版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明 http://leen2010.blogbus.com/logs/124631640.html 前几天讨论班我讲了基于PCA的人脸识别,当时我自己其实也只是知道这个算法流程,然后基于该算法利用c++实现了,效果还不错。后来跟师兄一起讨论的时候,才发现这个PCA还是有相当深刻的意义。 PCA的算法:矩阵C=AAT,A的每一列是一张人脸注(将一张人脸图片用一个列向量表示,即对于128*128的图片,将视为16384维的列向量),A的列数就是图片的张数。算法就是求矩阵C的特征向量,每个向量称之为特征脸[1]。为了简单,只取其中部分的特征向量,这些特征向量对应于某些特征值,通常是前M个大的特征值。这样便得到了M个特征向量。接下来就是将每张图片在这M个特征向量上做投影,得到一个M维的权重向量w=(w1,…wM),一个人可能有多张图片,于是将对应于这个人的权重向量做一个平均作为这个人的权重向量。然后对于每个新来的人脸,先求得一个权重向量,然后与人脸库中每个人的权重向量做比较,如果小于某个阈值,则认为他是人脸库中的这个人;否则视为unknown。当然,文章中还给出了另外一个判断一张图像是否是人脸的方法,这里不再讨论。对于计算的时候我们实际上求的是ATA,至于二者的关系,可以参考文章[1],因为与后面讨论的关系不大,这里不细说了。 有个上述简介,我们就大概知道了PCA到底是怎么做的了。刨根问底一下,C到底是什么,C的特征向量又到底是什么,对应于特征值大的特征向量有有什么意义。 1.C到底是什么?我们先看一下C的(i,j)元素是什么。很简单,就是A的第i行与AT的第j列的乘积。那么A的第i行又是什么呢?就是每张图片的第i个像素构成的一个向量。则C的(i,j)元素就是每张图片的第i个像素构成的向量与每张图片的第j个像素构成的向量的乘积。回忆一下概率论中的协方差cov(x,y)=E((x-x–)(y- y–)),这里x– 是x的平均。如果我们把图片的第i个像素视为一个随机变量Xi,那么人脸库中的每张人脸的第i个像素的取值即为这个随机变量的所有取值。根据注,A的第i行的每个值都已经减去了Xi的均值,因此C的(i,j)元素就是随机变量Xi与Xj的协方差。到此,我们已经知道C是什么了。 2.C的特征向量是什么。我们知道对C求特征向量是找到一个可逆矩阵Q,使得Q-1CQ是一个对角阵D,D的元素即为特征值,Q中的每一列即为特征向量,与特征值所在的列一一对应。注意,因为C是实对称阵,故必然可以对角化。由于C是对称的,C的特征向量是正交的,因此Q便是一个正交阵,故Q-1即为QT。先从简单的角度来看,假设C已经是一个对角阵了,并且对角元素依次递减。即随机变量Xi与Xj(i!=j)时是不相关的,而Xi的方差则随着i的增大而减小。也就是前几个像素是方差比较大的像素,即在第一个像素上,每张图片的值变化最大,第二个像素次之,依此类推。举个例子,假设第一个像素表示人脸的额头上的某个点(也许你会问,第一个像素不是图片的最左上角的那个像素吗?为什么会是额头上的某个点,后面会说明为什么可以这么假设),而在这个点上,有些人有痣,有些人没有,那么这一点的方差就会比相邻的额头上的其他点大,因为其他点上,每个人的额头都差不多,因此其像素值也差不多,方差就小了。现在来考虑QTAATQ=D,这里依然假设D中的元素依次递减。对于QTA,QT的每一行是一个特征向量,QT的第i行与A的每一列相乘得到QTA的每一行,从矩阵的角度也可以看作是用QT对A做一个变换。记住这里的QTA可以看做前面讨论的A,那么变换的结果就是使得QTA前面的行对应的是方差大的像素,而且这个变换会把方差最大的放到了第一行(因为D的降序排列),这里也就解释了为什么前面那个例子可以认为第一个像素是额头上的某个点,因为做了变换。我们选择了QT的前M行作为特征向量,因为他们对应了前M个大的特征值。这里可以举一个直观但是不一定恰当的例子,人的头发部分对应的那些像素,经过QT变换后回到某个像素上,那么这个像素会是QTA中的哪个位置呢,我认为应该是QTA的列中靠下面的像素,因为在头发这个像素的地方每个人基本都是头发(这句话很别扭,我是想说,对于比较正规的人脸库,即每张人脸不会有太大的变化,某个人头发的对应的那几个像素对于其他人来说也都是头发,因此变换后这个像素对于每个人都差不多,方差小,固然会在比较靠后的位置了)。QTA的每一列的前M个元素对应的就是每张人脸的权重向量w。因此每张人脸的权重向量的同一个分量可以看作是新的像素,这些新的像素对应着方差依次减小的像素。对于一张新来的人脸,让他在特征向量上作投影得到权重向量,在这些方差大的像素处,如果跟某个人的比较接近,则认为是这个人,这个也是合理的。至此,也许没能讲清楚特征向量是什么,但我想对应于特征值大的特征向量有什么意义这一点也交代的差不多了。 3.2中交代了说了,这里想不到有什么需要补充的了。 理解了这几个问题之后,PCA简洁明了(这本来就是的)而又有深刻意义了。我突然发现原来看似简单的理论其实水深的很,o(︶︿︶)o !我看文章实在是不够认真,如果没有师兄提问,估计我也不会去想这个问题。再次感谢WF师兄。   [1]Eigenfaces for Recognition. Matthew Turk,Alex Pentland 1991 注:A的每一列是一张人脸,这里的人脸是每张人脸减去了所有人脸的平均后的人脸

第二章 啊哈!算法

原文见: http://blog.csdn.net/silenough/article/details/7040028   A. 给定一个最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在文件中的32位整数(在文件中至少缺少一个这样的数—为什么?)。在具有足够内存的情况下,如何解决该问题?如果有几个外部的“临时”文件可用,但是仅有几百字节的内村,又该如何解决该问题? 因为2^32 大于40亿,所以文件中至少缺失一个整数。我们从表示每个整数的32位的视角来考虑二分搜索,算法的第一趟(最多)读取40亿个输入整数,并把起始位为0的整数写入一个顺序文件,把起始位为1的整数写入另一个顺序文件。这两个文件中,有一个文件最多包含20亿个整数,接下来将该文件用作当前输入并重复探测过程,但这次探测的是第二个位。如果原始的输入文件包含n个元素,那么第一趟将读取n个整数,第二趟最多读取n/2个整数,第三趟最多读取n/4个整数,依次类推,所以总的运行时间正比于n。 如果内存足够,采用位图技术,通过排序文件并扫描,也能够找到缺失的整数,但是这样做会导致运行时间正比于nlog(n). 1. 考虑查找给定输入单词的所有变位词的问题。仅给定单词和字典的情况下,如何解决该问题?如果有一些时间和空间可以在响应任何查询之前预先处理字典,又会如何? 首先计算给定单词的标识,若果不允许预处理,那么久只能顺序读取整个文件,计算每个单词的标识,并于给定单词的标识进行比较。   [cpp] view plaincopy //压缩一个单词,形成其标识,设定单词中相同字母不会超过99个 void compress(char * pWord, int len, char * pFlag) {     sort(pWord, pWord+len); //对单词进行排序     int i = 0;     int nCount;            //计数重复字母的个数     char chCount[3];       //存放整数到字符的转换值,整数最大为99     while (*pWord != ‘’)     {         char chTemp = *pWord;         char *pTemp = pWord + 1;         nCount = 1;         while (true)         {             if (chTemp == *pTemp++)             {                 ++nCount;             }             else             {                 *(pFlag + i++) = *pWord;             //  ++i;                 memset(chCount, ‘’, 3);                 _itoa(nCount, chCount, 10);                 if (nCount >= 10)                 {                     *(pFlag + i++) = *(chCount + 0);                 //  i++;                     *(pFlag + i++) = *(chCount + 1);                 //  ++i;                 }                 else                 {                     *(pFlag + i++) = *(chCount + 0);                 //  ++i;                 }                 pWord = pWord + nCount;                 break;             }         }     }
Continue reading 第二章 啊哈!算法