相门码农-CSDN博客

原创二部图-匈牙利算法实现

两篇参考网址http://blog.csdn.net/dark_scope/article/details/8880547 相亲举例http://m.blog.csdn.net/blog/fyxz1314/37651567 偏公式增广路径：非匹配边->匹配边->非匹配边组成的路径递归：将之前匹配边的女生赋给新的男生，之前匹配边的男生重新找到心仪的女生，如此递归。#include

2015-05-09 23:08:12 617

原创 atoi的C++版

2015-05-06 10:08:33 593

原创快速排序C++版

2015-05-06 09:59:55 453

原创编译多个目录源码的Makefile写法

文件组织如下：--Makefile--src目录--main.cpp--func.cpp--func.h--head目录--head.cpp--head.h--obj目录Makefile写法如下DIR_OBJ = ./objDIR_SRC = ./srcSRC = $(wildcard ${DIR_SRC}/*.cpp ${DIR_SRC}

2015-04-24 00:57:01 6461

原创安装vim的YouCompleteMe插件

1. 安装vim7.4，从官网下载vim7.4.tar.gz（因为YouCompleteMe只支持vim7.3.584以上版本） ./configure --enable-multibyte --enable-pythoninterp=yes --enable-python3interp=yes make & make install ex

2015-04-16 17:05:48 1345

原创影响逻辑斯蒂回归性能的因素

我们考察步长、迭代次数、是否包含默认类别、二元或多元、损失函数比率等因素。并与最大熵分类器进行对比。1. 是否包含默认类别，就是说在进行K元分类时，是否包含第K+1个默认类别。包含默认类别的输出h(x) = exp (W*X) / {1.0 + sum_exp (W*X)}，对于iClassIndex 不包含默认类别的输出h(x) = exp (W*X) / {

2015-04-14 21:47:59 1074

原创逻辑斯蒂回归多元分类的随机梯度下降

先介绍二元分类的批量梯度下降，伪代码如下：for loop: 1...iLoopNum

2015-04-13 20:59:44 4164 1

转载使用MIT JWI（Java WordNet Interface）查询WordNet反义词

使用MIT JWI（Java WordNet Interface）查询WordNet反义词 2013-01-22 22:33:28| 分类：治学 | 标签：jwi wordnet antonym 反义词查询 |举报|字号订阅与JWNL的Synset不同，MIT JWI查询WordNet的基本概念是Word。在MIT JWI中，一个Word（

2014-02-16 20:58:48 2063

转载 HashMap 与 TreeMap的区别

HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素

2014-02-16 19:25:27 525

转载 WordNet发展概况

·关于WordNet的不成熟的想法可以追溯到20多年前，而这一想法开始逐渐具体化和清晰化则是1985年后才开始的。从85年开始，WordNet作为一个知识工程全面展开。不过，当时的WordNet和经过10多年后今天的WordNet还是很不一样的。·这一工程最初的前提之一是"可分离性假设"（Separabilityhypothesis），即语言的词汇成分可以被离析出来并专门针对它

2014-02-16 15:03:04 4890 1

原创用于词义消岐的Lesk算法

该算法由Michael E. Lesk于1986年提出，是一个基于词典的词义消岐方法。该算法认为：一个词在词典中的词义解释与该词所在句子具有相似性。这种相似性可以由相同单词的个数来表示，比如“cone”和"pine"的意思分别为： CONE1. solid body which narrows to a point2. something of this shape whe

2014-02-15 22:16:18 8686 2

转载 10个你应该知道的Java正则表达式的例子

正则表达式是一个编程的艺术，很难调试，学习和理解，但强大的功能，仍吸引不少开发者编写正则表达式。让我们探索一下下面10个实际应用中的正则表达式。1. 用户名正则表达式模式^[a-z0-9_-]{3,15}$^ # 行开始 [a-z0-9_-] # 匹配列表中的字符，a-z,0–9,下划线，连字符

2013-07-24 21:22:58 600

转载 15分钟轻松定制基于VIM的IDE

1 背景VIM被人追捧为“无所不能”的文本编辑器，是很多Unix和Linux程序员的最爱。VIM最大的特点是扩展性极强，功能定制异常灵活。灵活性和复杂性之间通常是矛盾关系，VIM复杂的定制参数和大量的命令也使得很多新手望而却步（我曾经也是其中之一）。本文不打算介绍详细介绍VIM的定制和扩展方法，而是试图在最短的时间内、通过最简单的手段将VIM定制为一个适合程序开发的IDE。本文介绍的定

2013-07-23 16:36:42 756

转载词干提取（stemming）和词形还原（lemmatization）

词形还原（lemmatization），是把一个任何形式的语言词汇还原为一般形式（能表达完整语义），而词干提取（stemming）是抽取词的词干或词根形式（不一定能够表达完整语义）。词形还原和词干提取是词形规范化的两类重要方式，都能够达到有效归并词形的目的，二者既有联系也有区别现将共同点和联系总结为以下４方面：　　（１）目标一致。词干提取和词形还原的目标均为将词

2013-06-15 17:05:01 1241

转载 stanfor-parser使用参考

1、到斯坦福官方网站http://nlp.stanford.edu/software/lex-parser.shtml下载软件包，解压。2、在eclipse中新建一个java project，把解压得到根目录下的stanford-parser.jar和stanford-parser-2.0.4-models.jar（不同版本文件名可能有差异）两个包导入项目到项目引用包中，然后把解压得到根目

2013-06-09 16:53:26 4565

转载前向算法实现

typedef struct{　　int N; /* 隐藏状态数目;Q={1,2,…,N} */　　int M; /* 观察符号数目; V={1,2,…,M}*/　　double **A; /* 状态转移矩阵A[1..N][1..N]. a[i][j] 是从t时刻状态i到t+1时刻状态j的转移概率 */　　double **B; /* 混淆矩阵B[1..N][1..M]. b[j][k

2013-06-02 19:35:53 771

转载 NLP常用工具

各种工具包的有效利用可以使研究者事半功倍。以下是NLP版版友们提供整理的NLP研究工具包。同时欢迎大家提供更多更好用的工具包，造福国内的NLP研究。*NLP Toolbox CLT http://complingone.georgetown.edu/~linguist/compling.html GATE http://gate.ac.uk/ Natural La

2013-05-16 15:56:37 636

转载 C++ String类的实现

面试的时候被问及了String类的实现，结果没写好... 就当是重新复习一下吧。下面的程序并没有把String类的所有成员方法实现，只参考教程写了大部分重要的成员函数。 [cpp] view plaincopy#include #include using namespace std; class

2013-04-22 20:13:44 584

转载 C++学习笔记（15）——静态绑定与动态绑定

本博客（http://blog.csdn.net/livelylittlefish）贴出作者（三二一、小鱼）相关研究、学习内容所做的笔记，欢迎广大朋友指正！静态绑定与动态绑定静态绑定：编译时绑定，通

2013-04-22 20:10:38 522

原创 POJ《A Knight's Journey》方法：DFS

题目大意：骑士遍历给定p*q棋盘，列是从'A'开始，找到一条字典序最小的遍历路径。// 236k 47ms#include #include using namespace std;typedef class {public: int row; char col;} location;bool visit['Z'+1][27];int row, col;int x,

2013-04-19 10:26:52 568

转载 BM模式匹配算法-原理（图解）比较清楚的一篇

由于毕业设计（入侵检测）的需要，这两天仔细研究了BM模式匹配算法，稍有心得，特此记下。首先，先简单说明一下有关BM算法的一些基本概念。 BM算法是一种精确字符串匹配算法（区别于模糊匹配）。 BM算法采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。 BM算法的基

2013-04-16 14:15:50 1027

转载 insert into 和select * into的性能比较

但是Mysql不支持select into table，只支持select into var，因此要用create table tb as select * from xx where两者之间存在很大的性能差异，是由于数据库的日志模式不一样，simple和完整模式会导致差异。　　　　8万数据量，采用insert into 需要3秒左右，select * into 300毫秒。差十倍

2013-04-16 10:04:43 4159

转载 snort中的BM算法(c语言实现)

/* 函数：int* MakeSkip(char *, int) 目的：根据坏字符规则做预处理，建立一张坏字符表参数： ptrn => 模式串P PLen => 模式串P长度返回： int* - 坏字符表*/int* MakeSkip(char *ptrn, int pLen){ int i; //为建立坏字符表，申请256个int的空间 /

2013-04-15 19:04:42 1173

转载 BM算法

BM算法后缀匹配，是指模式串的比较从右到左，模式串的移动也是从左到右的匹配过程，经典的BM算法其实是对后缀蛮力匹配算法的改进。所以还是先从最简单的后缀蛮力匹配算法开始。下面直接给出伪代码，注意这一行代码：j++；BM算法所做的唯一的事情就是改进了这行代码，即模式串不是每次移动一步，而是根据已经匹配的后缀信息，从而移动更多的距离。1j = 0；

2013-04-15 12:47:13 648

原创 POJ3461《Outplo》方法：KMP

题目大意：求p字符串在s字符串中出现的次数。解题思路：典型的KMP，但是要注意这里的nextval数组要多求一位，比如aka的nextval数组为-1,0,-1,1，从而在akakaka中找aka子串时，在s[3]时，可以与p[2]比较。如果只要求在源串中找子串的位置，nextval数组是不需要多求一位的。// 1276k 110ms#include #include using

2013-04-13 21:41:06 574

转载 const char, char const, char*const的区别 .

const char*, char const*, char*const的区别问题几乎是C++面试中每次都会有的题目。事实上这个概念谁都有,只是三种声明方式非常相似很容易记混。 Bjarne在他的The C++ Programming Language里面给出过一个助记的方法：把一个声明从右向左读。 char * const cp; ( * 读成 pointer to

2013-04-13 13:12:58 475

转载由KMP算法谈到BM算法

六之续、由KMP算法谈到BM算法作者：滨湖，July、yansha。说明：初稿由滨湖提供，July负责KMP部分的勘误，yansha负责BM部分的修改。全文由July统稿修订完成。出处：http://blog.csdn.net/v_JULY_v 。引言在此之前，说明下写作本文的目的：1、之前承诺过，这篇文章六、教你从头到尾彻底理解KM

2013-04-13 12:58:26 574

原创 POJ2513《Colored Sticks》方法：字典树+欧拉图+并查集

转自http://blog.csdn.net/lyy289065406/article/details/6647445题目大意：给定25W条木棒，木棒两个端点为表示颜色的字符串，比如blue, red，能否根据端点颜色相同这个条件，将这些木棒连接起来。解题思路：就是找一条欧拉图，充要条件是图是连同的，且有0或2个结点度数为奇数。居然用map将字符串映射到整数也超时，因为它是基于hash的，

2013-04-12 10:32:22 626

原创 POJ3253《Fence Repair》方法：优先队列

题目大意：需要切成20000块木块，每切一次的费用就等于该模板长度。解题思路：因此首先将待切木板排序，每次取2块最小的木板，比如有8, 5, 8三块木板，首先切21的木板，然后切5，再切8，21+5+8=34。反过来就是5, 8, 8，第一次5+8=13, 8,13，第二次8+13=21。和为13+21=34。将这些小块木板合起来的最小费用等于将大块木板分割的最小费用。// 480k 49

2013-04-09 10:27:25 702

原创 POJ3432《Count Squares》方法：哈希

题目大意：跟POJ2002一摸一样，就数据由1000变为2000，找正方形形。解题思路：已知： (x1,y1) (x2,y2) 则： x3=x1+(y1-y2) y3= y1-(x1-x2) x4=x2+(y1-y2) y4= y2-(x1-x2) 或 x3=x1-(y1-y2) y3= y1+(x1-x2) x4=x2-(

2013-04-05 10:52:30 697

原创 POJ2002《Squares》方法：哈希

题目大意：给定平面上的一些坐标点(1000个)，找出这些点能构成多少个正方形，坐标取值不大于20000。解题思路：若遍历4个点的坐标，肯定超时。因此先取两个点坐标，然后用哈希值查找正方形的另两个点坐标，key = (x*x+y*y)%prime，这里prime取1999(不大于2n的素数)，并用链地址法解决地址冲突。因为每个正方形按不同顺序被枚举了4次，所以要除以4。// 620k 136

2013-04-01 10:40:27 601

原创 POJ1840《Eqs》方法：哈希

题目大意：给定系数，求a1*x1^3+a2*x2^3+a3*x3^3+a4*x4^3+a5*x5^3 = 0方程式解的个数。系数和x范围都是[-50, 50]但不包括0。解题思路：不能暴力穷举，因为穷举的话会有5层循环，每层循环100个数，总共就有100^5种情况，肯定超时。因此上式转化为-(a1*x1^3+a2*x2^3) = a3*x3^3+a4*x4^3+a5*x5^3，循环层数就变

2013-03-26 14:40:00 657

原创 POJ3274《Gold Balanced Lineup》方法：哈希

题目大意：最多有10w个牛，每个牛有最多30个特征，比如特征 10，可以表示为二进制形式1010，现在要求出在一个连续区间，牛的每个特征数目相等时，连续区间的最大长度。解题思路：sum[i][j]表示从第1个到第i个牛，特征j出现的总数，即要求sum[a][0] - sum[b][0] = sum[a][1] - sum[b][1] = sum[a][k-1] - sum[b][k-1]。式子

2013-03-25 19:30:51 553

原创 POJ3349《Snowflake Snow Snowflakes》方法：哈希函数

题目大意：给定10W组数，每组数由6个数字组成，分别代表雪花的每一边长，现在需要找出是否有两个一样的雪花，即顺时针或逆时针的一组数要相同。解题思路：因为数据量过大，因此不能将每组数和其他10W组数比较，因此用到哈希函数，以每组数的和作为key，然后用除以prime 100003的余数作为下标值，存的还是这个数的序号，取质数作为除数是为了减小冲突。// 6200k 3625ms#inclu

2013-03-24 16:07:24 694

原创 POJ1002《487-3279》方法：sort

题目大意：给定一些用字符，连接符，数字组成的号码，将这些号码按照规定格式，最终都转换为数字格式。输出重复的号码和次数。解题思路：全存为数字后，快排，若某个号码出现多于2次则输出。// 620k 782ms#include #include #include #include using namespace std;void initCtoi(char *c){ for

2013-03-23 23:14:09 576

原创 POJ1804《Brainman》方法：归并排序找逆序数

题目跟POJ2299差不多，只不过数据集变小了，用冒泡排序也可以。// 204k 204ms#include using namespace std;const int inf = 1000001;int ans; // 逆序数void combine(int *a, int top, int mid, int end){ int len1 = mid-top+1; i

2013-03-22 13:10:10 610

原创 POJ2299《Ultra-QuickSort》方法：归并排序找逆序数

题目大意：求一个数的逆序数，比如54321的逆序数为4+3+2+1+0=10，逆序数 = 在只交换相邻两数的前提下，需要的交换次数。解题思路：因为这题数据量为50W，时间限制为7000ms，用冒泡排序找相邻交换次数肯定超时，因此用归并排序找相邻交换次数。之所以不用快速排序，是因为它不符合相邻元素交换的要求。// 3748k 2454ms#include using namespace

2013-03-22 13:02:56 631

原创 POJ2388《Who's in the Middle》方法：排序

题目大意：找10000个数中的中位数。解题思路：用O(nlogn)的排序算法，O(n^2)会超时，STL中的sort函数是对qsort的优化，时间复杂度O(nlogn)。//252k 47ms#include #include #include #include using namespace std;int main(){ int n; cin >> n; int

2013-03-21 10:22:36 579

原创 POJ1007《DNA Sorting》方法：排序

题目大意：给定一组DNA序列，只包含A,C,G,T，按每个序列的逆序数排序。比如DCBA，逆序数为3+2+1=6。解决方法：求每一个DNA序列逆序数，从序列的后面向前遍历，eg.如果遇到C，就加上之前A和B的数量，同时自身加一，然后根据逆序数快排，如果逆序数相等，则按照原始顺序，可用qsort。//208k 0ms#include #include #include using

2013-03-20 09:57:36 678

原创 POJ1936《All in All》

直接暴力求是否是子串，就是在子串中加入一些字母。LCS的方法以后再想吧。#include #include #include using namespace std;int main(){ //freopen("temp.txt", "r", stdin); long i, j, lens, lent; char s[100001], t[100001]; while (

2013-03-19 10:22:29 632

空空如也

空空如也