128kj
- 浏览: 600489 次
- 来自: ...
-
最新评论
-
lgh1992314：
相同的元素呢
一种离散化方法 -
HelloSummerR：
圆心的位置是随机的，于是圆的部分会落到canvas外，那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio：
好久没见到sokuban了，这有个java版的，带源码，可以参 ...
求推箱子的最小步数（java) -
肖泽文：
太好了，谢谢你。。有中文注释！
HTML5 推箱子游戏过关演示动画 -
swm8023：
删除操作，将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)（JAVA）
文章列表
一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。
在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。这样就可以得到AVL 树。
平衡调整的4种基本类型：
AVL树及JAVA实现
public class AvlTree<T extends Comparable<? super T>>
{
private static class A ...
形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ，其严格定义是：
一棵空树是平衡二叉树；若 T 是一棵非空二叉树，其左、右子树为 TL 和 TR ，令 hl 和 hr 分别为左、右子树的深度。当且仅当
①TL 、 TR 都是平衡二叉树； ...
一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示，其中每一个结点都是一个对象。结点中除了数据外，还包括域left,right和p,它们分别指向结点的左儿子、右儿子，如果结点不存在，则为NULL。
它或者是一棵空树；或者是具有下列性质的二叉树：
1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉查找树；
显然满足了上面的性质，那么二叉查找树按中序遍历就是按从小到大的顺序遍历，这也就是为什么叫排序树的原因，当然上面的小于和大于都可以根据自己的需求改 ...
一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示，其中每一个结点都是一个对象。结点中除了数据外，还包括域left,right和p,它们分别指向结点的左儿子、右儿子，如果结点不存在，则为NULL。
它或者是一棵空树；或者是具有下列性质的二叉树：
1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉查找树；
显然满足了上面的性质，那么二叉查找树按中序遍历就是按从小到大的顺序遍历，这也就是为什么叫排序树的原因，当然上面的小于和大于都可以根据自己的需求改变的。 ...
poj2503题意:
给出一个最多有１０００００对单词的英语和外语的字典,然后给你一个外语单词 要求你查字典翻译成英语，如果词典里查不到就输出eh。
样例:
Sample Input
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay
atcay
ittenkay
oopslay
Sample Output
cat
eh
loops
解法一:使用jdk中的Hashtable(或HashMap)
import java.util.Scanner;
import java.util.Hashtable;
...
例:给出一个字符文本，每行一个字符串，统计不同的字符串出现的百分比,最后按ASCII排序输出不同字符串和出现的百分比。
分析：对输入字符串建立字典树，在叶子结点记录该字符串出现的次数。这样的话，最后DFS搜索就可以查找每个字符串出现的次数。
样例:
Sample Input
Red Alder
Ash
Aspen
Basswood
Ash
Beech
Yellow Birch
Ash
Cherry
Cottonwood
Ash
Cypress
Red Elm
Gum
Hackberry
White Oak
Hickory
Pecan
Hard Maple
White Oak
Soft Ma ...
Trie树提供给了一种能够在字符串的长度n时间内判断出来是否在已有集合中已经存在这个字符串了。POJ 1056是判断前缀码的问题。如果所有字符串都不是其他的字符串的前缀的话，那么就是可以直接编码的。
POJ 1056题目大意：
给你几个二进制代码，如果有其中一个代码是另一个的前缀，输出is not immediately decodable，反之，输出immediately decodable。
样例：
Sample Input
01
10
0010
0000
9
01
10
010
0000
9
Sample Output
Set 1 is immediately dec ...
字典树 又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的 ...
POJ 2442 题目大意：
给出m个序列，每个序列有n个非负整数，每次从每一个序列中取出一个数（共m个数）求和（显然有 n^m 个和），求这些和数中前n个最小的数。
样例：(第一行是测试次数1，第二行是m和n,接下来是m个序列）
Sample Input
1
2 3
1 2 3
2 2 3
Sample Output
3 3 4
解题步骤：
1.将第一序列读入array1数组中，并按升序排序。
2.将第二序列数据读入array2数组中，并按升序排序。
将array2[0] + array1[i] ( 0<=i<=n-1)读入heap优先队列中建堆。
...
优先队列，顾名思义，就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结合体，不仅可以存储数据，还可以将这些数据按照我们设定的规则进行排序。
优先队列主要方法:
void add(Object o);//进队
void offer(Object o);//进队
Object poll();//出队
Object peek();//查看队列首元素
boolean isEmpty();
int size();
在下面例子中用基于数组的堆实现优先队列，即堆中的元素保存在一个数组中。堆是一种二叉树，所遵守的唯一规律为：所有的子节点都要大于（小于）父节点。而 ...
堆有最大堆和最小堆之分，最大堆就是每个节点的值都>=其左右孩子（如果有的话）值的完全二叉树。最小堆便是每个节点的值都<=其左右孩子值的完全二叉树。
设有n个元素的序列{k1,k2,...,kn},当且仅当满足下列关系时,称之为堆。
堆的三种基本操作(以下以最大堆为例)：
⑴最大堆的插入
由于需要维持完全二叉树的形态，需要先将要插入的结点x放在最底层的最右边，插入后满 足完全二叉树的特点；
然后把x依次向上调整到合适位置满足堆的性质,例如下图中插入80,先将80放在最后,然后两次上浮到合适位置.
时间：O(logn)。 “结点上浮”
...
继续上文：学习使用jdk1.7中内置数据库Derby(二)http://128kj.iteye.com/blog/1727385
三） 运行网络模式的Derby数据库
这种模式下，需要使用两个控制台窗口，一个用于启动Derby数据库服务端，另一个做为访问Derby数据库的客户端。
可以通过DERBY_HOME\bin目录下的startNetworkServer.bat来启动Derby数据库服务端，只需要在命令行中输入：
startNetworkServer.bat
数据库就启动了，启动成功会在控制台输出如下信息：
D:\db>startNetworkServer
Fri ...
继续上文"学习使用jdk1.7中内置数据库Derby(一)"http://128kj.iteye.com/blog/1725848
Derby提供了三个工具脚本：1）sysinfo；2）ij；3）dblook。运行这三个脚本时，如果你没有设置classpath环境变量，这些脚本会自动进行设置。
1） sysinfo
使用sysinfo可以显示你的Java环境信息和Derby的版本信息。使用方法就是在命令行下直接输入：
sysinfo.bat
2） dblook
使用dblook可以将全部或者部分数据库的DDL定义导出到控制台或者文件中。使用方法：
dbloo ...
Java内嵌数据库Derby环境配置和使用
Derby数据库是一个纯用Java实现的内存数据库，属于Apache的一个开源项目。由于是用Java实现的，所以可以在任何平台上运行；另外一个特点是体积小，免安装，只需要几个小jar包就可以运行了。jdk1.6和jdk1.7内嵌了Derby数据库,安装在jdk的安装目录下的子
目录db中,以下以jdk1.7为例说明,db目录中有:
1） bin目录，包含了一些工具脚本和设备环境的脚本；
2） lib目录，包含了Derby数据库的jar文件；
一、Derby数据库有两种运行模式：
1） 内嵌模式。Derby数据库与应用程序共享同一个JVM， ...
POJ1734
题意：给定一个N个点的无向图，求一个最小环(各边权值和最小的环)并输出路径。
样例:
Sample Input
5 7 （图有五个点,七条边)
1 4 1 (顶点1与4之间有一条边,权值为1,以下同)
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
Sample Output
1 3 5 2
思路：朴素的求法是：枚举每一条边（假设为e(i,j)），删除它，再求(i,j)之间的最短距离(用Dijkstra算法），该环就是dis(i,j) + e(i,j)。这样就需要依次枚举每条边，然后求一次最短路，时间复杂度为：O(N* ...