128kj
- 浏览: 600454 次
- 来自: ...
-
最新评论
-
lgh1992314：
相同的元素呢
一种离散化方法 -
HelloSummerR：
圆心的位置是随机的，于是圆的部分会落到canvas外，那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio：
好久没见到sokuban了，这有个java版的，带源码，可以参 ...
求推箱子的最小步数（java) -
肖泽文：
太好了，谢谢你。。有中文注释！
HTML5 推箱子游戏过关演示动画 -
swm8023：
删除操作，将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)（JAVA）
文章列表
深度优先搜索DFS(Depth First Search)
（一）深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。
（二） 深度优先搜索就是在搜索树的每一层时始终先只扩展一个子节点，不断地向纵深前进直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。
深度优先搜索亦称为纵向搜索。由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。所以，深度优先搜索策略是不完备的。
另外，应用此策略得到的解不一定是最佳解（最短路径）。
三、深 ...
如果已经知道搜索的开始状态和结束状态，要找一个满足某种条件的一条路径（一般是最短路径），为了避免无谓的“组合爆炸”产生，就可以采取双向广度搜索算法，也就是从开始状态和结束状态同时开始搜索，一个向前搜，一个向后找。 直至在两个扩展方向上出现同一个子结点，搜索结束，这就是双向搜索过程。出现的这个同一子结点，我们称为相交点，如果确实存在一条从初始结点到目标结点的最佳路径，那么按双向搜索进行搜索必然会在某层出现“相交”，即有相交点，初始结点一相交点一目标结点所形成的一条路径即是所求路径。
这样做的好处是什么？
我们不妨假设每次搜索的分支因子是r，如果最短的路径长为L的话（也就是 ...
我们经常使用的数的进制为“常数进制”，即始终逢p进1。例如，p进制数K可表示为
K = a0*p^0 + a1*p^1 + a2*p^2 + ... + an*p^n （其中0 <= ai <= p-1），
它可以表示任何一个自然数。
对于这种常数进制表示法，以及各种进制之间的转换大家应该是很熟悉的了，但大家可能很少听说变进制数。
这里介绍一种特殊的变进制数，它能够被用来实现全排列的Hash函数，并且该Hash函数能够实现完美的防碰撞和空间利用（不会发生碰撞，且所有空间被完全使用）。这种全排列Hash函数也被称为全排列数化技术。
一、变进制数：
我们考查这样一 ...
例：输出由数字0,1,2..n组成的全部可重复全排列
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
public class Permutation{
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n=in.nextInt();
System.out.prin ...
广度优先搜索是以某一节点为出发点，先拜访所有相邻的节点。 再依序拜访与刚才被拜访过的节点相邻但未曾被拜访过的节点，直到所有相邻的节点都已被拜访过。 因此，进行广搜 时，需要使用queue ，以便记录拜访的顺序。一般有下面的模板:
public void bfs(int v) {
//队列用来保存被访问节点的分支节点
Queye< Integer> que = new LinkedList< Integer>();
que.offer(v);//起点入队列
while (!que.isEmpty()) {
v = que.pol ...
有两种常用的方法可用来搜索图：即深度优先搜索和广度优先搜索。它们最终都会到达所有连通的顶点。深度优先搜索通过栈或递归来实现，而广度优先搜索通过队列来实现。
广度优先搜索：
它首先访问起始顶点的所有邻接点，然后再访问较远的区域。它是用队列来实现的。
下面图中的数字显示了广度优先搜索顶点被访问的顺序。
图的广度优先搜索，要遵守以下规则：
(0) 选取某一顶点作为开始搜索的起点（当前顶点）入队列，标记为已访问。
(1) 访问当前顶点的下一个未被访问的邻接点，这个点必须是当前顶点的邻接点，标记它，并把它插入到队列中。
(2) 如果因为已经没有未访问的邻接点而不能执行规则1 ...
再次强调：
图的广度优先搜索，要遵守以下规则：
(0) 选取某一顶点作为开始搜索的起点（当前顶点），标记为已访问。
(1) 访问当前顶点的下一个未被访问的邻接点，这个点必须是当前顶点的邻接点，标记它，并把它插入到队列中。
(2) 如果因为已经没有未访问的邻接点而不能执行规则1时，那么从队列头取一个顶点，并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2，则搜索结束。
【题（poj 1101)】：给出一个地图，标有X的地方不能经过，给出一对坐标（2，3），（5，3），问这对坐标能否相连通（连连看），如果能则输出最少要经过的路段（路段是指一段直线，如果中途发生转折则就是两个路段）； ...
为图的每个顶点所发出的边建立一个单链表，用一顶点数组存储每个单链表的头指针。
import java.util.*;
class VNode{
int from;//边的起点
Edge first;//以from为起点的第一条边
public VNode(int from){
this.from=from;
first=null;
}
}
class Edge{
int to;//边的终点
Edge next;//具有同一起点的下一条边
public Edge(int to){
this. ...
凸多边形最优三角剖分
一凸8边形P的顶点顺时针为{v1，v2，… ，v8}，任意两顶点间的线段的权重由矩阵D给出。
若vi与vj是P上不相邻的两个顶点，则线段vivj 称为P的一条弦。求P的一个弦的集合T，使得T中所有的弦恰好将P 分割成互不重迭的三角形，且各三角形的权重之和为最小（一个三角形的权重是其各边的权重之和）。
/*
int graph[][]={
{0, 14, 25, 27, 10, 11, 24, 16},
{14, 0, 18, 15, 27, 28, 16, 14},
{25, 18, 0, 19, 14, 19, 16, ...
前序遍历的第一个元素为根节点，在中序遍历中找到这个根节点，从而可以将中序遍历分为左右两个部分，左边部分为左子树的中序遍历，右边部分为右子树的中序遍历，进而也可以将前序遍历除第一个元素以外的剩余部分分为两个部分，第一个部分为左子树的前序遍历，第二个部分为右子树的前序遍历。
由上述分析结果，可以递归调用构建函数，根据左子树、右子树的前序、中序遍历的结果输出后序遍历的结果。
//根据前序遍历和中序遍历重建二叉树的Java实现
class Node {
Node left = null;
Node right = null;
char valu ...
【题目】
假设一棵二叉树的后序遍历序列为 DGJHEBIFCA ，中序遍历序列为 DBGEHJACIF ，则其前序遍历序列为 ( ) 。
A. ABCDEFGHIJ
B. ABDEGHJCFI
C. ABDEGHJFIC
D. ABDEGJHCFI
由题，后序遍历的最后一个值为A，说明本二叉树以节点A为根节点（当然，答案中第一个节点都是A，也证明了这一点）
下面给出整个分析过程
【第一步】
由后序遍历的最后一个节点可知本树根节点为【A】
加上中序遍历的结果，得知以【A】为根节点时，中序遍历结果被【A】分为两部分【DBGEHJ】【A】【CIF】
于是作出第一幅图如下
【第二步】
将已经确定 ...
最长单调递增子序列的长度问题
所谓子序列，就是在原序列里删掉若干个元素后剩下的序列，以字符串"abcdefg"为例子，去掉bde得到子序列"acfg"，。现在的问题是，给你一个数字序列，你要求出它最长的单调递增子序列的长度（LIS）。
设给定序列为 array[]，大小为 n， 最长单调子序列必定以序列array[]中的某一个元素结尾，这是废话。
设lis[i]为以array[i]结尾的最长单调子序列的长度，那么array[]的LIS的长度就是
max{lis[i]} (0<=i<n)
显然此问题具有最优子结构性质:
...
矩阵链乘法最优结合问题
一、《问题的引出》
看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50
按此顺序计算需要的次数（（A1*A2）*A3）:10X100X5+10X5X50=7500次
按此顺序计算需要的次数（A1*（A2*A3））:10X5X50+10X100X50=75000次
所以问题是：如何确定运算顺序，可以使计算量达到最小化。
二、问题描述
已知：给定n个矩阵构成的一个矩阵链(A1, A2, ..., An)，矩阵Ai的维数为pi-1×pi
求：决定该矩阵链的乘法结合顺序（即加括号），使得矩阵链乘法 ...
一、最长公共子序列（LCS）问题：
给定两个序列 X = {x1, x2, ......, xm } 和 Y = {y1, y2, ......, yn }，找出 X 和 Y 的最长公共子序列。
一个给定序列的子序列是在该序列中删去若干个元素后得到的序列。给定两个序列 X 和 Y ，当另一序列 Z 既是 X 的子序列又是 Y 的子序列时，称 Z 是序列 X 和 Y 的公共子序列。
例如，若 X = {A， B， C， B， D， A， B }，
Y = {B， D， C， A， B， A }，
序列{B， C， A }是 X 和 Y 的一个公共子序列，序 ...
一、数组的最大子段和问题：
给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。
当所给的整数均为负数时定义子段和为0，依此定义，所求的最大值为：
Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n
例如，当（a1,a2,a3,a4,a4,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为20。'
我们令一个数组b，b[j]表示前j个元素能组成的最大和。如果b[j-1]大于零，则不管a[j]的情况，b[j-1]都可以向 ...