csc_csc_csc-CSDN博客

原创 KMP算法实现

（1）KMP算法 KMP算法是一种字符串匹配算法。学习这种字符串匹配算法最好是以例子的形式理解其思想。推荐一个用图片说明算法过程的博客，浅显易懂： http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html（2）算法实现#in

2013-05-29 10:34:03 1566

原创网页去噪，获取网页正文相关开源项目

（1）网页去噪网页去噪需要去掉与网页内表达内容不相关的文字，如广告，评论等等。现在对于博客、新闻类的网页去噪已经有很多的应用，比如常用的印象笔记、有道笔记就用到了相关的技术。因为项目的需要，也需要对网页进行去噪，留下有用的内容。所以在网上找了相关的网页去噪的开源项目。（2）参考链接主要参考的链接是这篇“网页正文抽取工具”，

2013-04-23 19:22:30 13290 3

原创 Ubuntu下安装PyQuery出现：ERROR: /bin/sh: 1: xslt-config: not found

（1）安装PyQuery时出现上述错误，并且下面跟着一句提示的话： ** make sure the development packages of libxml2 and libxslt are installed ** 可以判断是因为依赖的原因，用apt-get 来装libxml2，发现已经安装了，然后再apt-get安装

2013-04-23 15:33:50 8253

原创 Python错误： SyntaxError: Non-ASCII character

（1）问题描述在写Python代码的过程中，有用到需要输出中文的地方，但是运行后发现上述错误。 SyntaxError: Non-ASCII character '\xe4' in file ./common.py on line 2, but no encoding declared; see http://www.python.org/peps/pep-0263.html for

2013-04-03 10:54:58 18552 2

原创 Ubuntu: ImportError: No module named BeautifulSoup

（1）问题今天想试一下BeautifulSoup来解析HTML网页，在官网上下载了BeautifulSoup4的版本，但是在运行的时候（Ubuntu中）总是不能识别该库，报 ImportError: No module named BeautifulSoup 错误。（2）解决查找相关错误，判定是BeautifulSoup和Pyt

2013-03-28 22:29:17 5448

原创 Python抓取网页链接

（1）因项目需要，需要从web中抓取相关的网页。正好想学习一下Python，首先看了一下Python简明教程，内容讲的不多，但是能够使你快速入门，我一直认为实例驱动学习是最有效的办法。所以直接通过实际操作怎么去抓取网页来丰富对Python的学习效果会更好。 Python提供了各种各样的库，使得各种操作变得很方便。这里使用的是Python的urllib2和sgmllib库。为了处

2013-03-28 10:39:40 5701

原创二叉树遍历（九度题）

（1）题目描述：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串：ABC##DE#G##F###其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。输入：输入包括1行字符串，长度不超过100。输出：可能有多组测试

2013-02-28 09:49:32 2091

原创斐波那契数列

（1）题目描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。斐波那契数列的定义如下：输入：输入可能包含多个测试样例，对于每个测试案例，输入包括一个整数n(1输出：对应每个测试案例，输出第n项斐波那契数列的值。（2）这是九度上的一个题，要求时间限制1秒，整数的范围是大于0，小于70。如果是直接从n递归到

2013-02-28 09:39:34 2382

原创二叉搜索树的后序遍历序列（判断后序遍历序列是否合法）

（1）题目描述题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。输入：每个测试案例包括2行：第一行为1个整数n(1第二行包含n个整数，表示这个数组，数组中的数的范围是[0,100000000]。输出：对应每个测试案例，如果输入数组是某二叉搜索树的后序遍历的结

2013-02-18 23:47:29 2458 2

原创栈的压入压出（判断栈的压出顺序是否合法）

（1）问题描述题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。输入：每个测试案例包括3行：第一行为1个整数n(1第二行包含n个整数，表示栈的压

2013-02-18 23:25:00 6488 1

转载数据库设计中的反规范（转载）

最近需要了解数据库反规范化相关的知识，发现文章内容实在，转载之，以备参考。原文地址：http://www.uml.org.cn/sjjm/sjjm0%A3%B4.htm 数据库设计是把现实世界的商业模型与需求转换成数据库的模型的过程，它是建立数据库应用系统的核心问题。设计的关键是如何使设计的数据库能合理地存储用户的数据，方便用户进行数据处理。　　数据库设计完全是人的问题，而不

2013-02-17 20:25:12 2040

原创 Github使用gitignore忽略增加指定文件

（1）.gitignore介绍在工程实现过程中，会生成一些中间文件，或者在项目中的部分文件是不需要进行版本管理的。对于这些文件应该对于Github来讲是透明的。Github提供这种功能，可以自己指定哪些文件可以不被管理。具体方法是在版本管理的根目录下（与.git文件夹同级）创建一个 .gitignore（gitignore是隐藏文件，所以前面有个点）

2013-01-29 20:36:15 83102 6

原创利用Github进行版本管理

（1）最近需求一个个人的代码管理工具，之前没有接触过Github，所以想通过这个机会学习一个Github，比较囧的是，刚刚注册就被封了，幸好有国内大牛们的声援，使得Github重新解封。今天下午看了一些Github相关的文档，配置了一下，总结成博客。对github的了解还处于入门阶段。希望各路大神指点迷津……（2）这里直接给出工程性的配置文档，对于github的

2013-01-28 20:57:13 6091 2

原创哈夫曼树

（1）九度上的练习题，通过这个练习题把哈夫曼树复习一遍，并编码实现：题目描述：哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。输入：输入有多组数据。每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2输出：输出权

2013-01-08 20:22:11 1147

原创感知机学习算法实现

（1）感知机是二类分类的线性分类模型，其输入是实例的特征向量，输出为实例的类型。感知机学习的目的是将训练数据进行线性划分的分离超平面，属于是判别模型。感知机学习采用基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，最后求得感知机模型。强调：利用感知机学习策略进行训练的数据集要求必须是线性可分的，否则感知机学习算法不会收敛，迭代结果会发生震荡。

2012-12-14 17:08:52 7915

原创 Stable Matching Problem稳定匹配问题-----稳定婚姻算法

（一）问题的引出：有N男N女，每个人都按照他对异性的喜欢程度排名。现在需要写出一个算法安排这N个男的、N个女的结婚，要求两个人的婚姻应该是稳定的。何为稳定？有两对夫妻M1 F2，M2 F1。M1心目中更喜欢F1，但是他和F2结婚了，M2心目中更喜欢F2，但是命运却让他和F1结婚了，显然这样的婚姻是不稳定的，随时都可

2012-12-13 16:15:52 39073 4

原创利用Jena API构建RDF模型

（1）Resource Description Framework（资源描述框架 RDF）是W3C推荐的标准，与XML、SOAP等web标准并排，是一个用于表达关于万维网上的资源的信息的语言。RDF使用URI来标识任何事物，并通过属性和属性值来描述资源。资源、属性和属性值的组合可以形成一个陈述句，其中资源是陈述句的主体，属性时陈述句的谓语，属性值是陈述句的客体。主语、谓语、客体称为RDF的三元

2012-12-11 15:33:21 6803 3

原创 Dijkstra算法实现

（1）Dijkstra算法解决了有向图上带权的单元最短路径问题，但是算法要求所有的权值必须是非负。算法的思想及其实现均参考《算法导论》一书。 Dijkstra算法的时间复杂度依赖于最小优先队列的具体实现，下述算法采用的是最小堆结构，时间复杂度为O((V+E)lgV)（2）算法实现：（简单案例测试成功，若存在问题请指出，多谢。）#include using

2012-11-26 21:06:10 3625 1

原创 Bellman—Ford算法实现（解决存在负边情况下单源最短路径问题）

（1）BellmanFord算法能够在存在负边权值的情况下，解决单源最短路径问题，其时间复杂度为O(VE)。算法实验思想以及算法正确性分析主要参考《算法导论》中单源最短路径一章。（2）代码中图的实现采用邻接表，图的节点编号从0开始计数。算法输入图的结构，输出从源点到各个节点的最短距离#include #include u

2012-11-26 17:00:29 2235

原创检测是否为连通图（深度优先遍历算法）

（一）九度上一个练习题题目描述：给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。输入：每组数据的第一行是两个整数 n 和 m（0输出：对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。样例输入： 4 31 22 33 23 21 22 30 0样例输出：

2012-11-04 22:19:04 14756

原创搬水果 (贪心算法实现)

（1）题目描述：在一个果园里，小明已经将所有的水果打了下来，并按水果的不同种类分成了若干堆，小明决定把所有的水果合成一堆。每一次合并，小明可以把两堆水果合并到一起，消耗的体力等于两堆水果的重量之和。当然经过 n‐1 次合并之后，就变成一堆了。小明在合并水果时总共消耗的体力等于每次合并所耗体力之和。假定每个水果重量都为 1，并且已知水果的种类数和每种水果的数目，你的任务是

2012-11-01 23:17:38 3647

原创二叉树遍历---已知前序遍历和中序遍历求其后序

（1）九度上一个关于二叉树遍历的问题。通过给定的前序遍历与中序遍历就可以确定二叉树的结构。题目描述：二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。给定一棵二叉树的前序遍历和

2012-10-17 10:30:04 9358 1

原创有多少不同的面值组合

（1）题目要求题目描述：某人有8角的邮票5张，1元的邮票4张，1元8角的邮票6张，用这些邮票中的一张或若干张可以得到多少种不同的邮资？输入：题目没有任何输入输出：按题目的要求输出可以得到的不同邮资的数目（2）分析这个题目，可以将其归结为数组去重的问题。可以使用计数排序来实现。题目中总共的面值为 8*5+10*4+

2012-10-16 17:50:37 2130

原创数组中寻找第K小的数----位图法（bitmap）

（1）位图法所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的(百度百科)。　例如：对{0， 1， 5，3， 7}进行排序，可以在计算机中使用8位表示这几个数，也就是使用一个字节空间可以完成排序。数组中的数： 0 1 3

2012-10-15 19:25:13 3352 1

原创寻找大富翁（Top k问题）

（1）寻找大富翁问题。题目描述：浙江桐乡乌镇共有n个人,请找出该镇上的前m个大富翁.输入：输入包含多组测试用例. 每个用例首先包含2个整数n（0 n和m同时为0时表示输入结束.输出：请输出乌镇前m个大富翁的财产数，财产多的排前面，如果大富翁不足m个，则全部输出,每组输出占一行.这其实是一个Top

2012-10-13 00:31:55 2718

原创编辑距离算法实现

（1）编辑距离是测量一个字符串转换成另外一个字符串需要操作（操作包括：插入删除置换）的最小次数。编辑距离可以用来计算两字符串的相似度，另外也可以通过余弦方法来计算两字符串的相似度（2）算法实现采用动态规划算法，其求解过程类似于求两字符串的最长公共序列（LCS）下面是算法实现： public class

2012-09-18 18:29:41 3995

原创最长公共子序列算法（LCS）

（1）最长公共子序列问题可以使用动态规划来有效的解决。（2）算法实现是参考《算法导论》中的动态规划一章 public static void main(String args[]) { String s1= "abcbdab"; String s2 = "bdcaba"; LCS.getLCSLength(s1, s2); } publ

2012-09-18 16:41:11 5315

原创余弦方法计算相似度算法实现

（1）余弦相似性通过测量两个向量之间的角的余弦值来度量它们之间的相似性。0度角的余弦值是1，而其他任何角度的余弦值都不大于1;并且其最小值是-1。从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。所以，它通常用于文件比较。详见百科介绍（点击打开链接）（2）算法实现的中未使用权重（IDF ---逆文档频率），使用词项的出现次数

2012-09-18 10:22:44 31870

原创 Unicode编码相关的一个标准----UTF8

Unicode给每一个字符分配一个唯一的值，称为码点，但并不指定如何用这些值来表示原始文本。码点的形式为U+nnnn，其中nnnn指的是这个码点的十六进制值。Unicode目前支持超过100 000个字符。UTF-8是一个Unicode相关的标准，是一种使用码点来代表原始文本的简便方法。尽管有许多表示Unicode的方法，但是UTF8具有很大优势，它向后兼容ASCII编码。UTF-8用1-4个

2012-09-17 11:45:01 1831 1

原创 Invalid byte 2 of 2-byte UTF-8 sequence

在使用DOM4j解析文档的时候，遇见上了 Invalid byte 2 of 2-byte UTF-8 sequence 错误。这个错误一看就是编码的问题，用SAXReader解析的是我自己用Dom4j生成的文档，在生成的文档时候没有指定编码格式，所以需要在写入XML文件的时候指定编码格式。具体的代码是： OutputFormat format = new OutputFor

2012-09-12 19:53:05 2615

转载 JVM中的Stack和Heap

介绍Java中内存表示的一篇好文章，通俗易懂。收藏。转自：http://developer.51cto.com/art/201003/188753.htm在JVM中，内存分为两个部分，Stack（栈）和Heap（堆），这里，我们从JVM的内存管理原理的角度来认识Stack和Heap，并通过这些原理认清Java中静态方法和静态属性的问题。一般，JVM的内存分为两部分：St

2012-09-07 10:18:15 696

原创计数排序Java实现

计数排序的下界优于任意一个比较排序算法。它是一个不需要比较两个元素大小的排序算法。计数排序在百度百科中有详细的介绍http://baike.baidu.com/view/1209480.htm。这里编写了计数排序的Java版本： public static void main(String args[]) { int[] a = new int[] { 2,5,3,0,2,3,0

2012-09-04 20:54:05 2563

原创选择排序算法实现（Java）

选择排序的算法描述：首先找出数组A中的最小元素，然后将其与A[0]中的元素进行交换，然后找出A中次小的元素，与A[1]中的元素进行交换.......以此类推。下面是Java版的简单算法实现：public class S_Sort{ public static void main(String args[]) { int[] a = new int[]{11,2

2012-08-29 14:57:50 821

原创 Dom4j错误：java.lang.NoClassDefFoundError: org/jaxen/JaxenException

Dom4j可以使用Xpath来定位元素，具体可以使用selectNodes方法，但是在实际调用该类方法的时候出现了：java.lang.NoClassDefFoundError: org/jaxen/JaxenException，上述错误。通过在网上查找，原来是缺少jaxen包，然后到jaxen的网站上看了这个包的介绍，上面写的是：Jaxen is an open sourc

2012-08-23 16:45:28 21787 5

原创 Ubuntu下安装和配置ANT

（1）手动安装首先需要在Apache官网下载Ant，地址为：http://ant.apache.org/bindownload.cgi 然后将下载后的文件进行解压，然后将解压后的文件放到 /usr （这个路径是自己定义）下。最后配置环境变量，你首先需要确认已经安装了Java环境。在shell中输入： sudo vim /etc/

2012-08-19 22:52:26 12768

转载 Java 处理 XML 的三种主流技术及介绍

在伯乐在线（很好的网站）看到一篇关于Java处理XML的文章，其中讲到了默默无闻的Digester，觉得比较方便，以后会用到，转载记录之。转载地址：http://blog.jobbole.com/25372/简介： XML (eXtensible Markup Language) 意为可扩展标记语言，它已经是软件开发行业中大多数程序员和厂商用以选择作为数据传输的载体。本文作者对于

2012-08-18 20:04:15 1068

原创 JAVA集合学习笔记

（1）Java集合采用实现和接口分离的方法。例如比较熟悉的数据结构队列。一个队列接口的最小形式可能类似下面这样： interface Queue { void add(E element); E remove(); int size(); //............... } 但是实际上

2012-08-17 21:25:08 1052

转载 Java日期处理

学习Java日期处理，看见这一篇比较详细，转载之。转自：http://www.cnblogs.com/hqr9313/archive/2012/04/19/2458221.html时间日期1)java中的时间类有：Date和Calendar2)java中时间类的本质 long（毫秒数） Date = long +历法算法（方法gerYear()） Calenda

2012-08-17 18:55:30 5607

原创 Win7下安装jdk和Tomcat

（1）安装JDK，需要以下几步首先到oracle（刚才写成sun的官网，后面一贴网址突然就想起来了被oracle收购了……）的官网，找到JDK并下载下来：http://www.oracle.com/technetwork/java/javase/downloads/index.html 安装jdk，记住安装jdk的路径，我的路径为D:\Java\jdk

2012-06-28 22:07:06 4270

原创区别pointers和references

C++中提供两种间接参考对象：pointers和references。pointers使用“*”和“->”操作符，references则使用“ . ”。但是什么时候使用哪种方式？通过学习《More Effective C++》的条款1学习总结了以下情况：（1）一个references必须总代表某个对象，不可能存在null references。所以当你使用一个变量，其目的是用来指向代表另外

2012-06-17 15:35:23 1359