Tag: 算法

算法训练——GCJ-2008-R1A-B-Milkshakes

题目链接: https://code.google.com/codejam/contest/32016/dashboard#s=p1 分析:注意到每个customer最多只能有一种奶昔是”malted”的,这点是解决这题的关键。可以推出以下结论: 如果所有用户至少有两种喜欢的奶昔,那么必然有一种是”unmalted”,那只要保证所有奶昔种类都是”malted”就解决了。 如果有部分用户只喜欢一种奶昔,如果该奶昔是”unmalted”的,那么可以不用管它。 如果有用户喜欢一种奶昔,且”malted”,那么需要处理

leetcode212_字典树

水一篇文章。最近项目里在用字典树配合redis做搜索和字符串匹配,这部分不是我做的,但为了熟悉一下练练手,刷一道关于字典树的题目。纠结要不要把刷leetcode的题目搬上来,想想还是放上来吧,毕竟这题只有16%的通过率。况且字典树这个东西以后还是会经常用得到的,算是给自己以后留个参考吧。 题目地址 Word Search II 字典树、回溯法我觉得这题主要还是字典树。当然说回溯法也可以,毕竟在搜索的时候根据情况,适时停止,进入下一个分支。不过我觉得更合适的说法是在dfs中增加了条件判断而已。要说最经典的回溯问题,据我近两年的刷题经验来看,当属 八皇后 问题了,八皇后在leetcode中也有。

期望最大化(EM)算法matlab实现

一、前言看了吴军博士的《数学之美》感觉受益颇多,好书!第二版第27章讲的是期望最大化(EM)算法,看完就感觉如醍醐灌顶,而且原理上也不难,趁国庆的机会,把它实现了,加深一下理解。 EM算法 的范畴很广,之前几章的 最大熵算法、隐含马尔科夫模型的训练算法 都包括在内。用它做一些文本的自收敛分类效果很好,而且运算复杂度也不高,是一个很不错的选择。当然,关于文本的分类,前几章也有介绍一些其它的算法,也可以去参考一下。

next_permutation

产生一个数列的全排列,自己想了一个实现算法,和stl里面的实现算法一样,具体的思路都在注释中。代码中还实现了一种递归的做法,参考了网上的资料,递归的做法代码简短很多,但可操作性而言,没有next方式好。因为实际应用中需要针对每个permutation作相应的操作。用递归的话需要把操作写在permutation的实现中,耦合性很高。另外,递归的方式受限于系统栈空间的大小,N只能在一定范围内处理。理论上,next的方式N可以无限大。

Just for fun.用线程池并行处理ACM多组输入加快运算速度(对于算法提高不推荐)

做一道google code jam的题目来试试看我的线程池构想,看看速度会不会快很多。 其实这题我的算法并不是最优的,所以才会导致10分钟还出不了答案,要是真在code jam上比赛的话妥妥的跪了。但就算算法不好,我如果充分利用CPU的资源,使用多线程框架,会不会出结果时间快很多呢?试试看吧! 这个纯粹是玩玩的,如果要提高算法能力的话,不建议这么搞 code jam 原题地址戳这里注:需要翻墙的哦