jimmee
- 浏览: 539919 次
- 性别:
- 来自: 杭州
-
最新评论
-
GGGGeek：
看完了博主的博文，如果没猜错的话应该是浙大吧？很多优秀的人因为 ...
转《D君的故事》 以时刻警示自己 -
游牧民族：
楼主写的不错，学习了，最近对爬虫比较感兴趣，也写了些爬虫相关的 ...
通用爬虫框架及heritrix爬虫介绍 -
jimmee：
jerome_s 写道ice 你怎么看？ 粗略的看了一下ice ...
MessagePack, Protocol Buffers和Thrift序列化框架原理和比较说明 -
jerome_s：
ice 你怎么看？
MessagePack, Protocol Buffers和Thrift序列化框架原理和比较说明 -
jimmee：
nk_tocean 写道照着做了，但是不行啊，还是乱码.先确认 ...
hive编写udf处理非utf-8数据
文章列表
所谓深度优先：从图中某个初始顶点v出发,首先访问初始顶点v,然后选择一个与顶点v相邻且没被访问过的顶点w为初始顶点,再从w出发进行深度优先搜索,直到图中与当前顶点v邻接的所有顶点都被访问过为止。显然,这个遍历过程是 ...
- 2009-12-01 21:03
- 浏览 3500
- 评论(0)
1. 查找-合并算法
查找：检查两个对象是否属于同一个集合
合并：用一个集合替代两个对象分别对应的集合。
1.1. 快速查找
数据结构：使用一个大小为N的数组id[]，p和q是连通的如果他们对应的id值一样。
例如：
节点： i 0 1 2 3 4 5 6 7 8 9
初始： id[i] 0 1 2 3 4 5 6 7 8 9
当前值：id[i] 0 1 9 9 9 6 6 7 8 9
根据当前值，可以看出0是一个集合，1是一个集合，2，3，4，9属于一个集合，5 ...
怎么判断链表中是否有环？
- 博客分类：
- 算法
1.判断一个单向链表是否有环：
给定链表的头指针：Node*head。
设2个指针，一个指针每次移动1步，另一个指针每次移动2步，如果2个指针相遇那么说明有环，如果有一个指针到NULL了就说明没有环：
bool CircleInList(Link* pHead)
{
if(pHead == NULL || pHead->next == NULL)//无节点或只有一个节点并且无自环
{
return (false);
}
if(pHead->next == pHead)//自环
{
return (true);
}
Link *pTemp1 = pHead;//step 1
Link ...
- 2009-11-13 22:22
- 浏览 2585
- 评论(0)
I came across an interesting programming puzzle today, and I'd like to share a couple of variants on it.
To start with, let's say we have an array A that contains some numbers. For simplicity, let's say that the array is 1-based. How can we efficiently find out if any of those numbers are duplicates ...
- 2009-11-13 21:32
- 浏览 1436
- 评论(0)
1.length(),charAt(),substring()的运行时间是常量时间内完成。
2.toLowerCase()和replace()的运行时间与字符串的大小是线性关系。
3.compareTo()和startWith()需要的时间与所要解决问题所使用的字符数量成比例。在最佳情况下，是常量，在最坏的情况下，是线性的，但是indexOf可能很慢。
4.字符串连接需要的时间与在结果中的字符总数成比例。
5.给出倒序字符串的一种线性算法
public static String reverse(String s){
int N=s.length();
char [] a=n ...
4.图
图(Graph)G由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E),其中V是顶点的有限集合,记为V(G),E是连接V中两个不同顶点(顶点对)的边的有限集合,记为E(G)。
图一般可以采用三种方式来表示：使用一个二维数组；使用邻接表；使用边数组 ...
3.树的说明
树：T＝{K,R}。K是包含n个结点的有穷集合(n>0),关系R满足以下条件:
(1)有且仅有一个结点k0∈K,它对于关系R来说没有前驱结点,结点k0称作树的根。
(2)除结点k0外,K中的每个结点对于关系R来说都有且仅有一个前驱结点。
(3)K中每个结点对于关系R来说可以有多个后继结点。
我这里主要讨论的是二叉树，因为这个是用的最广泛的，二叉树也称为二次树或二分树,它是有限的结点集合,这个集合或者是空,或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。
二叉树的节点定义形式如下：
class TreeNode<E ...
2.栈和队列
所谓的栈，是一个含有至少两个基本操作的抽象数据类型：插入新的元素；删除最近时间插入的元素。遵循FILO（First in，last out，先进后出）的原则。
所谓的队列，也是一个含有至少两个基本操作的抽象数据类型：插入新的元素；删除最久时间插入的元素。遵循FIFO（First in，first out，先进先出）的原则。
关于栈和队列的具体实现，我们即可以借助于数组，也可以采用链表来实现。
1） 栈的数组实现方式
public class MyStack<E> {
public int count;
public Object [] items;
...
我这里主要是对基本的数据结构进行说明，包括数组，链表，栈，队列，树，图。
1.数组和链表的说明
数组的这个可以说是大家最广泛使用的数据结构了。数组的最主要的特点是可以支持随机存取，也就是说，我们查询一个值时，可以在O(1)时间内完成。如果我们在数组中删除一个元素，一般都是把后面元素向前移动，返回被删除的元素，如果插入一个新元素，我们把元素向后移动，留出一个空位，插入新元素。可见，删除和插入的时间复杂度为O(n)。
数组的特点时，我们在使用时需要先指定空间的大小（其实，我也可以采用一些变相的操作，来达到动态扩展空间的目的）。然而，使用链表，则可以动态的增加新的内存空间以保存新的元素。其实链表就像用 ...
在当我们学会了一门语言的时候（也就是说，记住了该语言的语法，词法，还有一些常用的函数），就意味着已经掌握了编写程序的基本工具。无论用的是社么语言，都差不多。只是工具之间有长有短。比如说，delphi,VB之类做wind ...
- 2009-11-04 12:54
- 浏览 1610
- 评论(0)
如果我们不采用比较的方式来实现排序，可以采用其他方式实现排序么？是的，可以。
1.桶排序
例如，我们有一个数组，里面的元素如下：
索引：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
元素：0 3 3 0 1 1 0 3 0 2 0 1 1 2 0
根据上面给出的数 ...
- 2009-11-04 02:38
- 浏览 1203
- 评论(0)
接下来，我准备说一下快速排序，归并排序和堆排序。
在讲快速排序和归并排序前，首先说一下分而治之的思想，就是说，先将要处理的问题简化，即将复杂的大问题分解为简单的小问题，然后分而治之。一般步骤如下：1）将问题分解为小的子问题。每个子问题与大问题同型，但规模更小。2）递归解决这些子问题。3）将子问题的解答合并获得大问题的解答。在这个策略下，实际编程时也是将工作分为这三步。大家要理解的是这种思想，例如，在问题分解时，我们不一定就每一步都分解成两个子问题，可能是三个子问题或者更多个子问题。其次，讲一下基于比较算法的时间复杂度下限。n个数有n！种排列顺序，一棵比较2叉树有对应的n！个叶节点，要排好序，需要 ...
一般来说，排序算法有10种，今天先说4种，并给出基本的代码。如有错误，欢迎大家指正。如果大家比较忙，忙着去泡妞的话，可以直接跳到最后看我的小结部分。
为了便于后面的讨论和理解，这里先做一个约定，就是把你要 ...