128kj
- 浏览: 600517 次
- 来自: ...
-
最新评论
-
lgh1992314：
相同的元素呢
一种离散化方法 -
HelloSummerR：
圆心的位置是随机的，于是圆的部分会落到canvas外，那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio：
好久没见到sokuban了，这有个java版的，带源码，可以参 ...
求推箱子的最小步数（java) -
肖泽文：
太好了，谢谢你。。有中文注释！
HTML5 推箱子游戏过关演示动画 -
swm8023：
删除操作，将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)（JAVA）
文章列表
Graham扫描法
基本思想：通过设置一个关于候选点的堆栈来解决凸包问题。
操作：输入集合P中的每一个点都被压入栈一次，非凸包中的顶点的点最终将被弹出堆栈，
当算法终止时，堆栈中仅包含凸包中的顶点，其顺序为个各顶点在边界上出现的逆时针方向排列的顺序。
(1)设P0是P中Y坐标最小的点，如果有多个这样的点则取最左边的点作为P0；
(2) 设<P1,P2,……,Pn >是P中剩余的点，对其按逆时针方向相对P0 的极角进行排序，
如果有数个点有相同的极角，则去掉其余的点，只留下一个与P0 距离最远的那个点；
(3)
//前三个点先入栈
ch[0] = ...
接上文：学习凸包(二）:分治法求解http://128kj.iteye.com/blog/1748622
通过前面两文学习，基本上明白了凸包,先做个练习POJ 1113.
POJ 1113题意：
从前有一个吝啬的国王要求他的总设计师在他的城堡周围建一道围墙。这国王非常吝 ...
接上文:学习凸包(一）:暴力算法求解http://128kj.iteye.com/blog/1748442
import java.util.*;
class Line {//线
Point p1, p2;
Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
public double getLength() {
double dx = Math.abs(p1.x - p2.x);
double dy = Math.abs(p1.y - p ...
原理：两个指针先都指向头指针的下一节点,一个指针先走K-1步，然后俩指针再一起走，后走的指针所指为所求，注意边界处理。
class Node{
Node link;
int data;
public Node(){}
public Node(int m) {
data = m;
}
}
public class MyLinkList {
...
凸包:令S是平面上的一个点集，封闭S中所有顶点的最小凸多边形，称为S的凸包。
如下图中由红线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。
算法代码:
import java.util.*;
class Line {//线
Point p1, p2;
Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
}
class Point{//点
int x;
int y;
}
public class BaoLiTuBao {
List& ...
今天遇到了一个关于Arrays.binarySearch()方法的返回值的问题:
下面程序输出什么?
import java.util.*;
public class Quest {
public static void main(String[] args) {
String[] colors = {"blue","red","green","yellow","orange" ...
关于二维树状数组请参看:http://128kj.iteye.com/blog/1746732
poj2029题意：
在一块h*w的地上,有n棵柿子树,划t*s的一块矩形地,使得其划到的柿子树最多,输出最多的数量.
样例:
16 //有多少棵树
10 8 //地的规模h*w
2 2 //(2,2)处有 ...
接前文:二维树状数组学习之一：彻底理解http://128kj.iteye.com/blog/1746732
POJ1195题意：大概题意如下：给出一个n*n的矩阵，初始化为均为0，还有关于这个矩阵的几种操作，操作如下：
命令0：n (给出矩阵的维数)
命令1：(X Y A) 对位于坐标（X Y）的值加A；
命令2：（L B R T）求出位于L<=x<=R，B<=y<=T的子矩阵的值的和；
命令3：退出不做任何操作。
分析如下：典型的二维树状数组，典型的动态操作题目。查询子矩阵(x,y,xx,yy)的元素和，注意一下就可以了:
sum(xx, yy)-sum( ...
当要频繁的对数组元素进行修改,同时又要频繁的查询数组内任一区间元素之和的时候,可以考虑使用树状数组.
通常对一维数组最直接的算法可以在O(1)时间内完成一次修改,但是需要O(n)时间来进行一次查询.而树状数组的修改和查询均可在O(log(n))的时间内完成.
一、回顾一维树状数组
假设一维数组为A[i](i=1,2,...n),则与它对应的树状数组C[i](i=1,2,...n)是这样定义的：
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 ...
//邻接表实现图的广搜和深搜(java模板）
import java.util.*;
public class GraphSearch{
private int n; //图的顶点数，顶点为0,1,2,,,,n-1
private List<ArrayList<Integer>> G;// 邻接表实现图。
private boolean[] visited;//判断顶点是否被访问过
public GraphSearch(int n,List<ArrayList<Integ ...
关于树状数组：参看：http://128kj.iteye.com/blog/1743633
POJ3321 题意：
一棵具有n个节点的树，一开始，每个节点上都有一个苹果。现在给出m组动态的操作：
(C,i)是摘掉第i个节点上面的苹果(若苹果不存在，则为加上一个苹果)，(Q,i)是查询以第i个节点为根的子树有几个苹果(包括第i个节点)。
输入是叉之间的关系，
1 2
1 3
就是主干上面两个叉分别是2 和3.
样例：
Sample Input
3
1 2
1 3
3
Q 1
C 2
Q 1
Sample Output
3
2
分析：
用树状数组求和，这个数 ...
经常要用到,放到这里备用!!
//邻接矩阵实现图的广搜和深搜
import java.util.*;
public class Graph {
private int[][] G;//邻接矩阵
private int k;//顶点数目
private boolean[] visited;//判断顶点是否被访问过
public Graph(int k,int[][] G){
this.k=k;
this.G=G;
visited = new boolean[k]; ...
哈希表中，一串连续的已填充单元叫做填充序列。增加越来越多的数据项时，填充序列变的越来越长，这叫做聚集。
为了消除原始聚集和二次聚集，可以使用另外的一个方法：再哈希法：一种依赖关键字的探测序列，而不是每个关键字都一样，那么，不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列。
方法是把关键字用不同的哈希函数再做一次哈希化，用这个结果作步长，对指定的关键字，步长在整个探测中是不变的，不同的关键字使用不同的步长。
数组实现的哈希表，开放地址法之再哈希法:
import java.io.*;
class DataItem {//数据项 ...
import java.io.*;
class DataItem { //数据
private int iData; // data item (key)
public DataItem(int ii) {
iData = ii;
}
public int getKey(){
return iData;
}
}
class HashTable{//数组实现的哈希表，开放地址法之线性探测
private DataItem[] ...
public class LinkedListNode {//链表节点
public LinkedListNode previous;//前一节点
public LinkedListNode next;//后一节点
public Object object;//节点中存的值
public long timestamp;
public LinkedListNode(Object object, LinkedListNode next, LinkedListNode previous)
{
...