内牛满面
leon_a · 共 25 篇文章
庞果英雄会 覆盖数字
庞果覆盖数字原题如下 给定整数区间和整数区间,你可以使用任意多次a,b之间的整数做加法,可以凑出多少个区间内的整数?输入 a,b,x,y,其中1<= a < b <= 1000000000, 1 <= x < y <= 1000000000。输出: 用内的整数做任意多次加法,可以得到多少个内的整数。例如a = 8, b = 10, x = 3 , y = 20我们可以得到 之间的整数 8, 9, 10, 16 ( 8 + 8), 17(8 + 9), 18(9 + 9), 19(9 + 10), 20(10 + 10),因此输出8。问:2+3=5 1+4=5 这算1个还是2个?答:算1次 问…
2013-11-14 15:13 · 数据结构与算法 · 评论(0)
2-3 tree
package com.leon.cc; import com.leon.util.Stack; /** * @author : Leon * @since : 2013-10-9 * @see : */ public class Tree { Node root = new Node(); public void insert(String str) { Node node = search_node(root, str); node.insert(str); while (need_split(node)) { if (node == root) { node = node.split(…
2013-10-09 17:10 · 数据结构与算法 · 评论(0)
编译原理生成LL1预测分析表
package com.leon; import java.util.HashSet; import java.util.Iterator; import java.util.Set; /** * @author : Leon * @since : 2013-8-11 * @see : */ public class LL1 { public String[] grammar_str; private int token_i; private String lambda = "lambda"; public boolean[] mark_lambda(Grammar g) { boolean…
2013-08-11 20:47 · 数据结构与算法 · 评论(0)
谷哥的KOF连招问题
传说问题是这样的 玩过KOF(拳皇)的人都知道,玩的时候会连招是比较强的。题目的大概意思是:每招用一个大写字母表示,如ABC...Z,现给定n个连招公式:S→T,其中S长度为m,T的长度为1。在前m招的时候可以随便连,但m+1招后就必须遵循连招公式。现在要写一个算法,计算最长连招的长度;如果可以无限连招,则返回def。1≤n,m≤100 给了一个例子:n=4,m=3,连招公式为:ABC→C,ABC→D,CCA→A,BCC→A。连招公式的意思是:A、B、C可以连出C,也可连出D,C、C、A可以连出A,B、C、A、可以连出B。这时候可以得到最长连招公式:ABC→C→A→A,即最长连招公式长度为6…
2010-10-09 14:38 · 数据结构与算法 · 评论(0)
ACM/ICPC HDU 1195
本年度还有8篇博客需要完成 开篇前附加一个看完《盗梦空间》的我的假设 这假设和薛定谔的猫处于半死半活的叠加态感觉有点像 世界全都是我做的梦 1:因为世界中的任何一个人“你”,不能对我证明“你”是有意识的还是只是我的虚构。 2:“你”是有意识还是虚构只能由你自己证明 这是我的某一篇论坛回复 原题是hdu的1195;题目是英文的,大意我翻译一下。 有一个紧急开启密码锁的任务。密码由四位数字组成;每个数字从1到9;每次,可以对每一个数字进行加1或者减1;当从1加到9时,由9再加1会变为1;当从9减到1时,由1再减1会变为9;也可以交换两个相邻的数字,每次操作作为一个step 你的任务就是用最少的步…
2010-09-06 10:37 · 数据结构与算法 · 评论(0)
答复: java最优算法讨论
这是我的论坛某一篇回复。虽然与楼主要求不一致,但这种结构在实际开发中很常见,比较有代表意义,因此收入博客。 原问题是这样的 有一字符串,格式为 1,2@1,3@1,7@2@1,5@1,12@9@1,16@10@5@1 上面字符串每个逗号分隔开的单独部分都是一颗树形结构的层级关系表示。比如说5@1是说自己的节点id为5,父级节点id为1.其他类似。 问题是,怎么根据上面一个字符串构建出该字符串对应的tree来。 由此题扩展,回想起我3年前开发过的一个报表功能 该种报表是为了统计各部门盈利状况。其中各个部门之间有从属关系,类似于原题中的2@1;每个叶子部门在数据库中会有当月收入多少,支出多少这样…
2010-06-08 21:01 · 随便鼓捣 · 评论(1)
散列,全散列
这是回复某一篇关于散列,完全散列的帖子写的代码。 再把问题描述一遍: 在两个很大的字符串数组中,求两个数组中共有的字符串 写一个o(m*n)的算法很容易 实际上引入hash,完全把复杂度降到o(m+n) 但是引入hash,需要注意hash冲突;当hashcode冲突时,需要在hash数组上纵向bucket;将重复hashcode存入到纵向bucket。 hash查询时,查询到某一bucket,再进行一次迭代查找hashcode 理想状态无冲突的复杂度为o(m+n) 假设平均冲突为常数k,则复杂度变为o(k(m+n)) 实际情况下,当ary足够大,冲突会变得足够小,k可忽略不计。即o(k(m+…
2010-05-14 11:22 · 随便鼓捣 · 评论(0)
排序小玩意儿
jasperreport没有内置的排序功能;在pdf进行group的时候,除非你在sql中进行了排序,否则group的结果会让人感到很杯具。 所以就写了这个东东。完整代码见附件 几个类: Order:设置按属性排序,DESC,ASC Util:设定支持原生类型 Main:排序类 用法: Order order = new Order().add("city", Order.ASC).add("id", Order.DESC); List result = m.getOrderedData(list, order); 使用规则: 所有排序的属性都实现了Comparable接口(原生类型会转成包…
2010-04-28 09:50 · 随便鼓捣 · 评论(0)
排骨工具箱之二:excel内容比较
excel内容比较工具 写这个工具的原因: 最近重构一本excel报表程序。由于程序上线很久,有很好的稳定性;但是随着最近版本增加的越来越多,程序也开始越来越难维护;因此老程序不动,在工程中重新开辟了一个package放重构后的程序。这样就引入了这样一个问题:重构前的程序和重构后的程序要在打印结果上要求完全一致。 比较生成的excel内容,有两种解决方案: 第一种是写VBA 第二种是用POI 我选择了POI,因为可以很好的结合到junit中。 按如下方式使用,程序见附件 assertFalse(!new CompareExcel(path).compareExcel(sheetIndex, …
2009-12-21 17:15 · 造轮子 · 评论(0)
答复: 阿里巴巴面试感言
好吧,我承认我闲的蛋疼 问题:3000万条的记录取最大的前50条数据 这题的时间复杂度应该是3000W*lg50 需要取前50个数构造heap恒长为50的最小堆 第51个数开始,与根节点比较,如果大于根节点,与根节点交换,并进行一次最小堆的minHeapify过程 内存2G很宽裕 代码如下(PS:我是没时间做3000W的数据,除非我真的蛋疼) package org.leon.testcase; public class Main { public static void main(String[] args) { int[] target = {12,4,3,56,11,122,131,3…
2009-10-09 22:27 · 数据结构与算法 · 评论(4)
排骨工具箱之一:万能toString
看到很多po,vo不写toString()方法,我们在调试程序的时候,需要一条一条的加输出,碰到属性很多的po,vo。我们可能就在崩溃的边缘了 因此写了一个po,vo的万能toString 支持全属性输出以及指定某些属性输出两种模式 以及支持集合及树状显示 用法 全属性:POJODecorator.toPOJOString(obj); 指定方法:POJODecorator.toPOJOString(obj,"getProducttype;getProductname"); 代码见附件
2009-09-24 10:10 · 造轮子 · 评论(0)
正向最大匹配改进算法
AD.: 2年J2EE经验,熟悉常用数据结构算法,熟悉常用开发框架。 手机:15940949592,欢迎骚扰及内部推荐 题外话:为什么用java来写呢,因为可以写的又臭又长 :? :? :? :? 正文: 传送门,引用ahuaxuan大牛的帖子, 使用DFA实现文字过滤 在ahuaxuan的帖子中,实际上也引入了一个基于Trie字典树中文分词的问题。 图1:一个典型的Trie树结构 其中图1 state为1时表示从根结点到state=1的结点成一个词 图1由三个词组成:“上海”,“上海浦东”,“上海浦东发展银行” 将“上海浦东发展银行”进行词语切分,在不使用正向最大匹配及逆向最大匹配的情况下…
2009-05-26 22:11 · 数据结构与算法 · 评论(24)
决策树C4.5算法
数据挖掘中决策树C4.5预测算法实现(半成品,还要写规则后煎支及对非离散数据信息增益计算),下一篇博客讲原理 package org.struct.decisiontree; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.TreeSet; /** * @author Leon.Chen */ public class DecisionTreeBaseC4p5 { /** * root node */ private DecisionTreeNode ro…
2009-05-19 02:05 · 数据结构与算法 · 评论(2)
小工具用法
//http://pipboy.group.iteye.com/ //how to build app as jar file: //run build.xml //how to use this app //example: import java.util.List; import java.util.Map; import org.apache.commons.dbcp.BasicDataSource; import com.pipboy.util.Query; import com.pipboy.util.QueryFactory; public class Main { publi…
2009-01-20 11:32 · 造轮子 · 评论(0)