ITeye博客

北京的杨过

sunlujing · 共 33 篇文章

[置顶] 最坏情况O(N) 求数组中第K 大的元素。

求数组中第K的元素的一般方法就是使用快速排序的划分, Partion(seq,start,end) = p, 如果p=k 则ok。如果p >k 则在start, p -1的区间里找第K大的数,Partion(seq,start,p-1) 否则partion(seq,p+1,end) 算法的平均时间复杂度为O(N),最坏情况为N^2,即每次划分把数组变为为(n-1) 和1的两断. 对此算法导论上给出了一个最坏情况下为O(N)的算法 该算法就是每次partion的时候找到一个好的划分,用中位数的中位数作为pivot。 把数组分为 N/5组,每组插入排序之后求得中位数,共 N/5 个中位数,对这N…

2013-06-01 20:23 · j2se · 数据结构 · 算法 · 评论(0)

[置顶] 单源最短路径算法 Dijkstra和Bellman-Ford

常用的单源最短路径算法一共有两个,一个是Dijkstra算法 ,一个是Bellman-ford 算法 Dijkstra 算法 不能处理含有负权边的图,Bellmanford 能够处理含负权边或包含负权回路的图。 首先是Dijkstra算法: 算法的具体思想就不多写了,算法导论上有很详细的介绍,我主要还是贴出一个代码实现。 Dijstra里面需要用到优先级队列这里笔者也给出了一个。 使用堆实现的优先级队列,Dijkstar的复杂度在VlogV。 优先队列: package graphic; import java.util.ArrayList; import java.util.Compara…

2013-05-29 14:56 · 数据结构 · 算法 · 评论(0)

[置顶] Kruskal 算法

Kruskal算法是最小生产树算法 算法的步奏: 初始情况下: 把所有的节点看成是独立的一颗森林。 算法的核心就是尽可能找出权值最小的边把这些分散的森林组合成一个完整的包含所有顶点的森林。 使用的是贪心算法,贪心的证明可以参看算法导论。 使用一个以边的权值为基准的优先级队列来维护所有的边 edges for(Edge edge:edges){ node src = deg.src; node des = des.des; // 判断src 和des 是否在同一个森林 如果不在同一个森林,则找到一条贪心边, 把src 对应的森林 和 des对应的森林 合并成一个森林 } 上述算法需要 判断两个…

2013-05-28 10:51 · 算法 · 评论(2)

[置顶] 图的基本算法(DFS,BFS, topoSort,SCC)

由于要面试的缘故,在看算法导论的图算法一节,决定把基本的算法都用java代码实现出来。 1. 图的表示,使用链接表的形式。 class TreeNode{ int nodeNum ; //节点编号 TreeNode parent = null; //遍历时的父节点 int dis = Integer.MAX_VALUE;// 距离源节点的路径 int discoverTime =0; //在DFS遍历时发现的时间 int finishTime =0;//DFS遍历时结束的时间 Color color = Color.White;//初始时的颜色标记 List<Integer> edges =…

2013-05-27 11:16 · 算法 · 评论(0)

[置顶] java 实现含通配符的字符串匹配

算法目标,对于 字符串 abcd1dd2deeedd9 能偶匹配到字符串 abc*dd?;*代表任意个数的字符串,?代表一个字符. 分两步走, 第一步实现含?而不含*的 字符串匹配,如对dd?的匹配 第二步,实现含有* 的字符串的匹配,如abc* dd?,主要思路是用* split 字符串,分为两个有效的串,abc, dd? 然后使用步骤一种的方法来查看匹配到的index. /** * 找出含?的字符串 * @return */ public int checkSubPattern(String src,int begin,String pat){ boolean isFound=true;…

2012-10-28 17:42 · 算法 · 评论(3)

[置顶] 关于工作流系统我还需要做的事情

我已经告别了我的大学时代,又把我轻轻的脚步迈入了研究生时代,虽然我的方向是计算机网络技术可是我想在我的职业规划中最重要的是在研究生阶段培养起专业的程序员素养。我想这种素养的一部分就是要善于总结,对于自己从事过的某一领域尽可能的做到专业。 在RZ做兼职的一年,基本上完整的跟这项目组完成了工作流系统的开发。现在发现的问题是具系统功能大致齐全,可是比较粗糙,在实用性和稳定行上都有很大问题。这些天一直在看看有关工作流理论方面的东西,试图从根本发现问题。我需要做的工作有如下: 1. 再一次研读blogcn上的一位作者对工作流系统开发的完全记录,比较RZ系统与其系统的不同和差异,向别人学习, 2. 对老…

2011-08-28 12:36 · 工作流 · 评论(0)

[置顶] ClassLoader 深入解析

本文是根据是在《北京圣思园深入JAVA虚拟机系列视频》的基础上自己整理而来,内容范围没有超过其系列所述,在此给予说明。 在进入ClassLoader的分析之前我们先看一个JAVA程序例子。 class Singleton { /* case 1 */ private static Singleton singleton = new Singleton(); public static int counter1 ; public static int counter2 = 0; /** * case 2 * public static int counter1 = 0; * public st…

2011-07-18 15:14 · j2se · 评论(0)

[置顶] 基于serverResource方式的liferay中ajax方式的的实现

在portlet2.0中加入了几大新特性。 资源服务:一种新的通过 portlet 呈现资源的方式。 事件:通过发送事件和接收事件来实现 portlet 之间的通信。 Portlet 过滤器:与 servlet 过滤器类似,根据 Portlet 请求和响应动态的呈现内容的变换。存在以下四种类型的 portlet 过滤器: Action 过滤器 Render 过滤器 Resource 过滤器 Event 过滤器 共享呈现参数:除了 portlet 私有的呈现参数之外,新增了可以在 portlet 之间共享的呈现参数。 Portlet 窗口:提供 portlet 窗口 ID 供 portlet …

2011-05-16 10:28 · liferay · 评论(2)

[置顶] liferay ipc porltet间通信DEMO

portlet2.0 的通信特性 JSR268中定义了portlet之间的通信协议 基本的原理就是事件监听机制,portlet A 触发事件。portlet B对时间进行监听并作出反应。传递的数据放在 事件的 payload 里面。并且事件通信的两个portlet可以不再同一个page,需要修改portlet.event.distribution=layout。 具体参见liferay in action 里 ipc 那一章。 下面展示通过liferay in action 的一个例子。 pitchPortlet view.jsp 上有一个 按钮。通过该按钮 该portlet发送一个事件。 …

2011-04-21 16:56 · liferay · 评论(2)

[置顶] ajax (post方式)调用 rest服务

参考文献:http://kodemaniak.de/?p=62(我是没怎么看懂啊,哪位看懂了给无留个言谢谢了) jquery代码: $.ajax({ type: 'post', url: url, dataType: 'json', contentType: "application/json", success: function(response){ var md5 = response.md5; $("#"+id).html("| "+md5); }, error: function(data) { $.messager.alert("info","error"); } }); res…

2011-04-20 14:21 · 评论(0)

[置顶] lucene的事务性引发的问题

终于ok了。。先开心一下。 我的问题和调试经历。 我使用lucene 为数据库建立索引,在初期的测试中,对数据进行增删改查我并没有使用缓存,而是直接用indexWriter进行commit。结果每一次commit后我马上进行搜索,结果就是不出来。我查看index 文件,每一次都已进行了更新。于是我确定commit后,index已经同步了。可是为什么就是搜索不到结果了????? 我每一次重新启动程序,上一次修改的结果都能被搜索得到,这就说明了搜索本身没有问题,。问题的关键就是,存在某个问题,使索引更新的效果对我不可以见,宝贵的周五就这样浪费了。由于周六周日要兼职。没空。。所以问题一直搁浅到现在…

2011-04-18 17:15 · lucene · 评论(0)

[置顶] 网页的缩略图效果显示

现在许多的浏览器都支持这样的功能,你新建一个标签页,标签页会以列表的形式显示你最近访问的网页。它的效果是 每个网页放入到一个 框里,在框里按照比例显示该网页,给人的感觉就是对该网页的一个截图效果。 最近在做的网管项目,功能特别多,有时候点击一个功能,可能要经过几级菜单的浏览,boss 让我考虑是否可以用这种方式记录下用户前几步访问的网页,在网上找了一下资料,找到一个大致类似的,用 div 中嵌入 iframe的方式做的。 代码如下:有其他思路的大神门,请多多赐教。 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "…

2011-03-10 10:02 · web开发 · 评论(0)

[置顶] AT&T的企业路

有幸看到谷歌研究员,科学家吴军写的“浪潮之巅”,也深深的为作者的广博的知识和思考的智慧所折服,于我这种也初出茅庐都算不上的IT小生,也只能是 用海绵式的吸收知识的方式写下我看到的每一个故事了。(文章只是对作者观点的简要概括) AT&T公司由电话之父亚历山大.贝尔 创建于1877年,百年帝国的辉煌和衰败从那一年开始走入人们的视线。 1925年,一个培养了11位诺贝尔奖获得者,一个发明了unix操作系统,一个发明了c语言并无数划时代技术的实验室应运而生,AT&T百分之三的收入经费支持,研究为主的学术氛围,使得贝尔实验室在很长一段时间里都成为了技术大牛们向往的天堂。 在很长一短时间里,贝尔实验室都…

2011-02-18 15:46 · 评论(0)

[置顶] 我的工作流系统开发总结

大致的内容如下: 工作流技术调研: 工作流的概念 工作流相关术语 工作流系统功能概述 工作流运行的模式列举 业内工作流产品调研 Mocha BPM产品 中软工作流产品调研 天翔myApps工作流产品调研 我们的需求分析 系统模块划分 工单系统的功能性需求列表 需求变更总结 设计方案 数据库设计 关于hibernate实现持久层和session的管理 自定义表单的设计 自定义流程的设计 消息模块的设计 后记 见附件:doc

2011-02-12 10:52 · 工作流 · 评论(0)

shell split 字符串 三种方式和效率

在shell 中以 , split 字符串如下 str="aaa,bbb,ccc,ddd" 我一般会用 echo $str |awk -F, '{print $1}' 这样的方式 或者是 echo $str|cut -d"," -f1 这样的方式 都能达到目的,但是由于文件很大,有很多行,上述方式需要开辟管道,会启动新进程,效率很低下。 在网上找了一下 存字符串的切分方式: arr=(${line//,/ }) year=${arr[0]} userId=${arr[1]} 效率是最高的。

2013-12-05 11:59 · linux · 评论(0)