三场网络赛终于告一段落了!唉,实力太弱了!跟北大、清华这些家伙差距太远了,比"我在你身边你却不知道我爱你"的距离还要远! 这道题没有来得及提交,自己下来写完的,把样例过了!留在博客上作个记念吧!记念我大学生涯失败的网络赛! 题目是这样的(英文原版): Description&n
近几天来研究伸展树,但一直都没有进展,想既然伸展树是一棵二叉查找树,那么先把二叉查找树的各种操作弄清楚了,再来研究伸展树也许会有突破! 二叉查找树是一种在log复杂度内实现快速查找元素的一种数据结构。其改进的树有红黑树,AVL树,平衡二叉树,节点大小平衡树,伸展树。 同其它数据结构一下,二叉查找树的操作有 查插删改 四种。我个
这是学习《ACM-ICPC程序设计系列—计算几何》自己AC的第一个计算几何的问题。题目是比较简单的,但还是花了我很久的时间。 题目可以抽象成:一个长方形被n条不相交的线段分隔成n+1个区间,给定m个点的坐标,计算出每个区间里各有多少个点。 需要注意的是:输入时,分隔长方形的线段已经排序。(这意味
http://www.cppblog.com/humanchao/archive/2007/12/29/39934.html #include<stdio.h> #include<vector> #include<algorithm> #include<iostream> using namespace std; typede
好了,断续微软面试题的学习!看到题目,我首先想到的是树状数组,后来看PPT才发现用树状数组可以实现查找第k大的元素,细想一下和这道题也差不多。网上的很多实现都是用堆做的,用堆大多数也是用C++的STL,Multiset来实现。网上代码很多,而且我也没弄明白这题,先就不自己写代码了。 在这里,给出一个O(n)复杂度的实现:BFPRT算法。我也
有了第一题作为基础,这一题写起来也相当简单。只是搜索的时候呢,可以剪枝一下。这个是搜索的技巧,用多了就自然有这个习惯了! 建树依然建立二元查找树,然后用深搜,用一个path数组把结点的值存储起来。用深搜打印路径比较方便。没有什么特殊和很难的地方。 这里需要注意的是:这个系列中我在系列(一)中上传的p
题目大意: 输入一个整形数组,数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为 O(n)。 例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为 3, 10, -4, 7, 2, 因此输出为该子数组的和 18。 最笨的方法就是三层for循环
昨天晚上完成第一个问题,今天来完成第二个问题。依然是网上搜索的到思路,觉得其实现比较优雅,就自己写了一遍,把思路整理一下! 有人说用链表来实现链栈,我个人觉得太过于麻烦,还是数组直接,简单! 解决这道题的思路在于:用空间换时间!很关键,很直白,但并不是很个人都能很灵活的运用!比如我就不能! 代码实
一网友对算法感兴趣,不知怎么得到了我的QQ号,加为好友。给我发来了微软面试题100题,让我做一做。我也正好想准备年底找工作的事儿,一举两得,就试试上面题目的难度。 第一道题是把二元查找树转变成排序的双向链表。一开始做这些题,困难还真不少,遇到的第一个问题就是:什么是二元查找树? 二元查找树: 它首先要
学习《浅析倍增思想在信息学竞赛中的应用》(附件下载)上面举例,快速求a^n,比如2^3=8; 用最直观的方法n个a相乘是很慢的,这种实现需要执行n次,而如果用倍增的思想,则可以在logN复杂度中求得结果。 具体的思路和解说参见附件中的ppt,因为ppt中分析得更透彻,我就不班门弄斧了。直接贴上自己实现的代码。 #include<stdio.h>
已经学习了简单的几种排序,在研究后缀数组的时候,发现里面要用到基数排序,就研究了一下。总共花了三个小时左右吧,实现了一种简单的代码。 先总结一下思路吧! 基数排序其实非常简单。 解法 基数排序的方式可以采用LSD(Least sgnificant digital)或MSD(Most sgnificant dig
学习Lucene最恼火的地方在于去它的官网,下载下来的jar包都是最新的,而参考书上面的用的却不是最新的。为了能更好的学习,最好与参考保持一致。下面是搜索到的Lucene各个版本的下载地址:http://archive.apache.org/dist/lucene/java/ 有了这个,以后就不用费心到处找了,也不用去csdn上花积分了……
关于单调队列的解释,这里有篇博文我认为讲得很好: http://xuyemin520.is-programmer.com/posts/25964,可以参考。我自己简单的总结了一下单调队列这种数据结构的性质: 1 、在队列里的元素一定是value单调递增(或者递减),而index单调递增。所以 队列中
这么简单的一个问题,让我纠结了这么久,唉! 问题:从0到n-1这n个数中找出m个数的组合。 代码: #include<stdio.h> #include<vector> using namespace std; vector<int> S; vector<int>
今天在Topcoder上做一道简单题,感觉这道题挺有意思的,就保存起来吧! Problem Statement A company is developing a 3-dimensional computer moni
还是先以POJ上面的问题入手吧!Sorting It All Out, 这道题是什么意思呢?简单的说就是给定像A<B这样的一组关系式。让你判断通过这些关系式能不能决定ABCD……的先后顺序。 一种有三种结果:能确定先后顺序,不能确定先后顺序,根本不可能有先后顺序(也就是出
图的遍历就两种方式:深搜和广搜。 深搜:深度优先搜索算法(Depth-First-Search),是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有
图论中的图是一个很抽象的东西。把抽象化的东西具体化后一般都比较容易理解,比如:一张地图,这当然是很直观的了。问题在于计算机没有那么强大的功能让图直接显示,因此我们需要用特定的方式表示一张图,那计算机中如何表示一张图呢? 一般来说,有三种表示方法。 对于稠密图(就是边很多的图,对应到地图上,就是交通发达的地区图),最好用矩阵表示; 对于稀疏图(与稠密图相对,边很少的图,对应到地
由于ACM的关系,重拾C语言。到学校的图书馆借了一本《C标准库》(人民邮电出版社:P.J.Plauger著 卢红星 徐明亮 霍建同译) 书里讲到<ctype.h>的内容,个人觉得非常好。就摘出来大家共享之。 这一张表格基本上就把<ctype.h>中的内容说完了。非常直观易懂。
我一直想写一些关于图论学习的收获。一直由于这样或者那样的原因都没有开始。无论如何,现在开始吧! 那么到底什么是图呢?我们这里说的图当然不是像照片一样的东东。最权威的定义:图=顶点集合+边集合。换言之,凡是能抽象成点集合和边集合的东西都是图。比如:中国地图。地图上的城市是一个个的点,而任意两个相邻城市之间有路
一个小小的树状数组竟然让我纠结到现在。从开始着手到现在能理解一个很重要的函数,一共花了大概5个小时。这样看来,时间也不算多嘛!@_@……呵呵! 我深刻的感觉到一个知识点是否容易领悟在于找到好的学
研究文本聚类,用的是ICTCLAS的分词系统。结果在处理文本的时候,会出现崩溃。 我起初以为是文本读取的问题,后来发现不是的。到Google上查找了一下"C [ICTCLAS.dll+
为了把LDA算法用于文本聚类,我真的是绞尽脑汁。除了去看让我头大的概率论、随机过程、高数这些基础的数学知识,还到网上找已经实现的源代码。 最先让我看到署光的是Mallet,我研究了大概一个星期,最后决定放弃了。因为Mallet作者提供的例子实在太少了。 &nb
在学习文本处理的的过程中,需要去除标点符号。今天在网上找到了觉得有必要 收藏起来,就转到自己的博客了。 public class Test { public static void main(String... args) { &nbs
在网上找了好久,都没有什么收获。今天搜到了百度搜索研发部的官方博客里面的一篇文章,有一种豁然开朗的感觉,虽然我依然没有明白LDA模型,但我相信,我双离它近了一步。 好了,把网址贴出来吧:http://stblog.baidu-tech.com/?p=1190 通过这篇文章,可以很容易的理解什么是主题 &n
近几天在学习LDA模型。真的是让人纠结!都看了两天了,不知所云! 看到网上一大牛说:“其实这个模型不难理解”真的想吐血!想想也释然了: 好歹也比我多读了八年书嘛!八年,日本鬼子也搞定了,别说一个小小的模型。 好了,抱怨一下也就可以了,模型还是得研究的! 从贝叶斯开始吧! &nb
做中文文本聚类,研究中科院的imdict-chinese-analyzer分词器时,我自己加载的停用词表一直都跑不出正确的结果,于是,就追踪lucene是怎么加载自己的停用词表的。在源代码的WordListLoader.java类中,发现了这样的代码: public static HashS
几个常用JAVA开源项目的地址荟萃 2009-04-07 15:44 Lomboz http://www.objectlearn.com/index.jsp (J2EE plugin for Eclipse) htmlArea http://
由于学习的需要,我找到了能够分析中文句子的句法分析器Stanford Parser. 下载地址:http://nlp.stanford.edu/software/lex-parser.shtml#Download 那么,如何把这个工具运用到eclipse中去呢? 第一步:建立一个project,然后把下载下
今天纠结了一天,还是把这个弄出来了!太有成就感了……呵呵 首先得把IK_Analyzer的jar包放到项目中,然后“当前project”->properities->java build path->add jar 把IKAnalyzer3
Copyright © 2005-2024 51CTO.COM 版权所有 京ICP证060544号