yzmduncan
- 浏览: 330319 次
- 性别:
- 来自: 武汉
-
最新评论
-
di1984HIT：
学习了～
Spring scope="prototype" -
netkiller.github.com：
路还很长看看我的博客 http://netkiller.git ...
写博客是个好习惯 -
ooo456mmm：
JAVA 设计模式之——动态代理 -
hanmiao：
问题是这么问的：请使用 Java 的基本数据类型表示壹下单链表 ...
JAVA数据结构之——单链表的逆序 -
hanmiao：
谢谢，今天刚好有人问我这个问题，结果没有答上来，看了你这篇文章 ...
JAVA数据结构之——单链表的逆序
文章列表
RMQ英文是Range Maximum(Minimum) Query，是用来求取某个区间的最大值最小值，通常用在查询次数比较大的区间最值问题中。
RMQ的原理是动态规划，利用了倍增的思想。我们用A[1...N]表示一组数，[Li,Ri]表示题目涉及到的查询区间。
设F[ ...
Trie树，又称单词查找树，典型用于统计和排序大量字符串，查询效率比哈希表高。(空间复杂度高)
它有3个基本特性： 1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。 2）从根节点到某一节点， ...
用于不相交集合的数据结构——并查集。每个集合通过一个代表来识别，设x表示一个对象，我们希望支持一下操作：
MakeSet(x)：建立一个新的集合，其唯一成员就是x。
Union(x,y)：将包含x和y的动态集合（比如说Sx和Sy）合并为一个新的集合。
FindSet(x)：返回一个指针，指向x对象所属集合的代表(唯一)。
一种加权合并的启发式策略。
第一种启发：按秩合并(Union by rank)，其思想是使包含较少结点的树根指向包含结点较多的树根。
第二种启发：路径压缩(path compression)，它非常简单而有效， ...
学习了上一节线段树的基本操作之后，再用例题详细讨论线段树的Lazy操作的精髓。
1. 矩形面积并。POJ1389 / HDU1542
题意：矩形面积并是给出n个矩形(边都平行于x轴或y轴)，这些矩形可能会相互重合，求出总的覆盖面积。
分析： 通过画图并观察，在x轴方向扫描这些矩形，发现只需要记录前面边的重合（有效）长度，比如有两条边，分别为[2,4], [3,8]，那么他们的有效长度为6。矩形的左边(入边)为1，右边(出边)为-1。现在就需要如何维护这些线段的有效长度了。可以想到用线段树来维护，因为它的插入和删除都是logn级别的。
解：a. 将点y坐标升 ...
线段树是ACM中比较常见的数据结构，它的每一点都代表了一条线段[a,b]，长度为1的为元线段，所有叶子结点的长度均为1。长度范围为[1,L]的一颗线段树的深度为log(L-1)+1。
线段树基本的应用时查询某段的和，最大最小值，成段更新，保证每次操作的复杂度为log(n)。
关于线段树的文章有很多，大家可以参考http://www.notonlysuccess.com/?p=59。
在这里，我用hdu和poj上面的一些关于线段树的简单应用做为例题讲解。
hdu1166（单点更新，区间求和）：
敌军海岸线上排列有n个营地，每个营地有若干个士兵，每个 ...
前些天在做动态规划的题，感觉动态规划博大精深，没有一种特定的模式，学起来很费劲。在这里就动态规划中的背包问题谈谈。
三种背包问题：0/1背包，完全背包，多重背包。
0/1背包：有n件物品和容量为v的背包，求 ...
最大流算法是网络流中基础的算法，解决的方法有很多，比如EK,Dinic,sap等等，在这里介绍一下EK算法。
从源点s开始广度优先寻找一条到t的路径，计算出这条路径的最大流量（短板效应）l，回溯，将这条路径的每条边 ...
KM算法用来求解二分图的最大(小)权匹配，即最优(佳)匹配。
该算法是通过给每一个顶点标号将求最大匹配问题转化为求完备匹配的问题。
设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。
KM算法的正确性基于以下定理：
若由二分图中所有满足A[ i ]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。
首先解释下什么是完备匹配，所谓 ...
二分图算法本身不算复杂，有模板直接套用，难点是将问题如何构造二分图或有向无环图(有向无环图的最小路径覆盖可以转化为二分图最大匹配)。
简单：POJ1469,3041,2536,2771,1325,1422
较难：POJ3020,2226,2594,1034,3216
待续。。
二分图：又叫二部图，图G中顶点集V可以分成互不相交的子集(X,Y),并且图中的每一条边所关联的点分别属于两个不同的顶点集，则图G叫二分图。(不含奇环)
二分图的匹配：给定一个二分图G的子图M，M的边集中任意两条边都不依附于同一个顶点(点单独配对)，则称M是一个匹配。
二分图的最大匹配：边数最大的一个匹配就是二分图的最大匹配。
看上去二分图匹配好像没有什么用途，但以下三个定理会有大用处：
1.二分图的最小点覆盖(x或y中的都行) = 最大匹配；
2.二分图的最大独立集 = 顶点数 - 最大匹配；
（最大独立集是从图中找出最多的顶点数并且顶点两两之间没有边）
3.有向无环图的最小路径覆 ...
排序分为几大类：插入排序，选择排序，交换排序，归并排序，基数排序。衡量排序方法的好坏有三种标准：时间复杂度，空间复杂度，稳定性。
在这里着重讲解一下热点排序：选择排序中的堆排序，交换排序中的冒泡和快速排序，归并排序。
在选择排序中，有一种简单的方法叫做直接选择排序，直接选择排序的基本思想是：从待排序的数据元素中选取关键字最小的数据元素并将它与第一个数据交换位置；接着从不包括第一个位置的数据元素集合中选取关键字最小的，与第二个位置的数据交换，如此重复，直到只剩一个数据元素为止。显然，这种排序方式的时间复杂度为O(n*n)。
在直接选择排序中，待排序的数据元素集 ...
哈希表是存储的是键值对，给出一个键值，哈希表可以在O(1)的时间复杂度查询。也就是说，它通过把关键码值映射到一个表中的一个位置来记录，加快查找速度。这个函数叫散列函数，存放记录的数组叫散列数组。
构造查询效率高的散列表基于以下两个方面：构造散列函数的方法和处理冲突的方法。
构造散列函数，即哈希函数，好的哈希函数，能使冲突和空间降低。一般有直接寻址法，折叠法，除留余数法。在ACM中，见到的字符串hash函数ELFHash。一般采用除留余数法。
处理冲突的方法也有很多：线性探测，链地址法等等。一般采用链地址法。
在ACM中只要设计大规模(10,000以 ...
最近做图的题比较多，除了克鲁斯卡尔和floyd，像广搜，普里姆，Bellman-Ford，迪杰斯特拉，SPFA，拓扑排序等等，都用到图的邻接表形式。
数据结构书上表示邻接表比较复杂，一般形式如下：
typedef struct Node
{
int dest; //邻接边的弧头结点序号
int weight; //权值信息
struct Node *next; //指向下一条邻接边
}Edge; //单链表结点的结构体
typedef struct
{
DataType data; //结点的一些数 ...
poj2503题目意思很简单：就像查找一本字典，根据输入的条目和要查询的单词，给出查询结果（每个单词长度不超过10）。这题有很多实现方式，最容易想到的就是map，但这是acm训练且stl里面的map速度不够快，那就要另谋出路。
数据量为100,000。可以想到的是快排+二分，复杂度是O(nlog2n)。还有就是哈希，哈希查询时间是O(1)，当然，还要考虑哈希冲突，设计合理的字符串哈希函数。
首先是快排+二分，比较简单。
#include <iostream>
const int MAX = 100001;
typedef struct
{
ch ...
今天在POJ上做水题3981，是读取一行字符串并将其中的you换成we输出。以前用c的时候都是用的gets()和char。现在用C++，就了解了下getline与string。
getline用来获取一行，语法是getline(cin,str)，读到文件末尾就返回EOF。按照题目要求，将输入的数据保存在string str中，在str中寻找字符串you，string的find函数：str.find("you")，如果找到第一个you就返回you的开始位置，找不到就返回string::npos，记录这个位置为start，将start位置起的长度为3的内容换为w ...