问题描述：给定输入N，生成从1开始的：1，2，3，4，......N一组随机序列，序列中的数不能重复出现。比如：N=5，合法的随机序列为{4,3,1,5,2}、{3,1,4,2,5}……非法的序列有{5,4,1,2,1}来源：《数据结构与算法分析-MAW著 第二章习题2.8》 思路1：对于数据a[N]而言，当随机生成第i个数a[i]时，确保a[i]在a[0]至a[i-1]中没有出现过，就把该数放入a[i]，继续生成下一个数a[i+1]算法复杂度为O(N^2logN)---每生成一个a[i]，需要扫描a[0]...a[i-1]。publicstaticint[]algorithm1(intN){int[]a=newint[N];for(inti=0;i<a.length;++i){while(true){a[i]=randInt(1,N);//生成[1,N]之间的一个随机数　　　　　　　　　　　　intj=0;for(;j<i;++j){if(a[i]==a[j]){break;//如果这个随机数已经在前面出现过了,break,...

1，堆作为优先级队列的应用对于普通队列而言，具有的性质为FIFO，只要实现在队头删除元素，在队尾插入元素即可。因此，这种队列的优先级可视为按时间到达的顺序来衡量优先级的。到达得越早，优先级越高，就优先出队列被调度。更一般地，元素不能单纯地按时间到来的先后来分优先级（或者说插入的顺序），在这种情形下，使用堆更容易表达优先级队列。Sometimestheprocessingorderoftheitemsinaqueueneedstobebasedoncharacteristicsofthoseitems,ratherthanjusttheordertheyarecreatedoraddedtothequeue. 2，堆的两个性质：①结构性质--堆从结构上看是一颗完全二叉树。然而，从物理存储上看，堆的实现基本上是使用一个一维数组存储堆中所有的结点。②orderingproperty---这是由堆的定义决定的，如大顶堆：根结点的值要大于左右孩子的值。由于堆具有这两个性质，故在对堆进行操作时，如插入操作、删除操作……都需要维护好这两个性质，因此：这也是为什么...

1，导论什么是数据结构？Adatastructureisanaggregationofdatacomponentsthattogetherconstituteameaningfulwhole。在计算机领域中，技术千变万化，但是基本的数据结构始终只有那几种。而抽象数据类型（ADT)就是用来描述数据结构具有的功能。比如，二叉树就有前序、中序遍历功能；栈，有先进后出功能。对于某一数据结构，放在不同的层次，它有不同的抽象，比如，对于存入整形数组的栈而言，站在使用Stack的角度，它具有提供先入后出功能；而栈可以用List实现，而List又可以用数组实现，而数组元素又可以是由各个Integer组成，而Integer对于编译器而言，又由bit组成。因此，谈论一种数据结构（类型），需要考虑站在的角度。 2，二叉树的构建算法--以二叉树的结点存储String类型的数据为例讨论通常的想法是，创建一个根结点，再创建一颗左子树和右子树，然后把根结点的左孩子指向左子树，右孩子指向右子树。这种说法并没有考虑，结点如何构造？子树根据什么原则来构造？具体的实现代码怎么写？下面就是记录二叉树创建的具体实现算...

在上一篇文章中记录了如何实现图的邻接表。本文借助上一篇文章实现的邻接表来表示一个有向无环图。1，概述图的实现与邻接表的实现最大的不同就是，图的实现需要定义一个数据结构来存储所有的顶点以及能够对图进行什么操作，而邻接表的实现重点关注的图中顶点的实现，即怎么定义JAVA类来表示顶点，以及能够对顶点进行什么操作。为了存储图中所有的顶点，定义了一个Map<key,value>，实际实现为LinkedHashMap<T,VertexInterface<T>>，key为顶点的标识，key是泛型，这样就可以用任意数据类型来标识顶点了，如String、Integer……value当然就是表示顶点的类了，因为我们需要存储的是顶点嘛。即value为VertexInterface<T>。这里为什么不用List而用Map来存储顶点呢？用Map的好处就是方便查询顶点，即可以用顶点标识来查找顶点。这也是为了方便后面实现图的DFS、BFS等算法而考虑的。此外，还定义了一个整型变量edgeCount用来保存图中边的数目，这也是必要的。讨论一个...

1，摘要：本系列文章主要学习如何使用JAVA语言以邻接表的方式实现了数据结构---图（Graph），这是第一篇文章，学习如何用JAVA来表示图的顶点。从数据的表示方法来说，有二种表示图的方式：一种是邻接矩阵，其实是一个二维数组；一种是邻接表，其实是一个顶点表，每个顶点又拥有一个边列表。下图是图的邻接表表示。从图中可以看出，图的实现需要能够表示顶点表，能够表示边表。邻接表指是的哪部分呢？每个顶点都有一个邻接表，一个指定顶点的邻接表中，起始顶点表示边的起点，其他顶点表示边的终点。这样，就可以用邻接表来实现边的表示了。如顶点V0的邻接表如下：与V0关联的边有三条，因为V0的邻接表中有三个顶点(不考虑V0)。  2，具体分析先来分析边表：在图中如何来表示一条边？很简单，就是：起始顶点指向结束顶点、就是顶点对<startVertex,endVertex>。在这里，为了考虑边带有权值的情况，单独设计一个类Edge.java，作为Vertex.java的内部类，Edge.java如下：1protectedclassEdgeimplementsjava.io.Seria...

1，对于待存储的海量数据，如何将它们分配到各个机器中去？---数据分片与路由当数据量很大时，通过改善单机硬件资源的纵向扩充方式来存储数据变得越来越不适用，而通过增加机器数目来获得水平横向扩展的方式则越来越流行。因此，就有个问题，如何将这些海量的数据分配到各个机器中？数据分布到各个机器存储之后，又如何进行查找？这里主要记录一致性Hash算法如何将数据分配到各个机器中去。 2，衡量一致性哈希算法好处的四个标准：①平衡性：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。②单调性：单调性是指如果已经有一些数据通过哈希分配到了相应的机器上，又有新的机器加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的机器中去，而不会被映射到旧的机器集合中的其他机器上。这里再解释一下：就是原有的数据要么还是呆在它所在的机器上不动，要么被迁移到新的机器上，而不会迁移到旧的其他机器上。③分散性：④负载：参考这里 3，一致性哈希的原理：由于一般的哈希函数返回一个int（32bit）型的hashCode。因此，可以将该哈希函数能够返回...

1，AVL树又称平衡二叉树，它首先是一颗二叉查找树，但在二叉查找树中，某个结点的左右子树高度之差的绝对值可能会超过1，称之为不平衡。而在平衡二叉树中，任何结点的左右子树高度之差的绝对值会小于等于1。2，为什么需要AVL树呢？在二叉查找树中最坏情况下查找某个元素的时间复杂度为O(n)，而AVL树能保证查找操作的时间复杂度总为O(logn)。   对于一棵BST树而言，不仅有查找操作，也有插入、删除等改变树的形态的操作。随着不断地插入、删除，BST树有可能会退化成链表的形式，使得查找的时间复杂度变成O(N)，这种情形下，BST树的结构非常不平衡了。为了保持树的平衡，需要对树的形态做一些限制，因此，引入了AVL树，以保证树的左右子树高度之差的绝对值小于等于1。3，AVL树的JAVA代码实现： AVLTree 继承BinarySearchTree并改写添加节点的add方法，在add方法中判断插入元素后是否导致树不平衡，当不平衡时需要通过旋转进行调整。何时进行旋转调整是通过左右子树的高度之差进行判断的。这里通过rebalance方法使得某结点保持...

1，堆是什么？堆的逻辑结构是一颗完全二叉树，但物理结构是顺序表(一维数组)。同时，此处的堆不要与JAVA内存分配中的堆内存混淆。这里讨论的是数据结构中的堆。参考：计算机中的堆是什么？2，数组实现堆的优势及特点由于堆从逻辑上看是一颗完全二叉树，因此可以按照层序遍历的顺序将元素放入一维数组中。注意为了方便，数组的元素存放从索引1处开始（不是0）。采用数组来存放就很容易地找到某个结点i的双亲结点(i/2)，孩子结点(左孩子：2i，右孩子：2i+1)3，基于数组的堆的实现需要哪些结构？privateT[]heap;//用来存储堆元素的数组privateintlastIndex;//最后一个元素的索引privatestaticfinalintDEFAULT_INITIAL_CAPACITY=25;首先需要一个一维数组heap来保存堆中的元素；其次，需要lastIndex标记堆中最后一个元素的索引，这样也知道了堆中存放了多少个元素；最后，需要一个final静态变量定义默认构造堆的大小。4，JAVA中基于一维数组的堆的实现具体代码分析①创建堆，假设有N个元素，需要将这N个元素构建大顶堆，有两种方法来...

1，在词典的实现(2)-借助顺序表(数组)实现词典文章中使用了自定义的数组代替ArrayList，并实现了Map数据结构的基本功能。而借助JAVA类库ArrayList类的一些方法可以更加容易地实现Map。 2，实现思路如下ArrayListDictionary.java中定义了一个ArrayList的对象，该ArrayList对象用来存储Entry类的对象，而Entry类封装了(key，value)。这样，利用ArrayList类的一些方法来间接地操作(key,value)，从而实现各种词典的操作。 ArrayListDictionary.java中部分代码解释如下： publicArrayListDictionary(){listDictionary=newArrayList<Entry>();}在构造方法中初始化ArrayList对象。这样，每生成一个词典对象，就会有一个ArrayList对象。因为，每个词典对象都需要一个ArrayList对象来存储词典中的元素。 privateclassEntry{Kkey;Vvalue;私有...

一，LoadingBalance问题描述：有m台相同的机器及n个作业，其中m={M(1),M(2),……M(m)}、n={J(1),J(2),……J(n)}。每个作业都有一个处理时间，记为t。如，;t(j)表示作业J(j)的处理时间。任意机器在某个时刻只能处理一个作业；一旦某个作业被调度到机器上处理，它就不能被抢占，直至它被处理完才能处理下一个作业。问：如何分配作业，使得处理完所有的作业所需的时间最少？由于该问题是NPC的，因此很难找到该问题的最优解（精确解），下面用贪心算法求解一个近似解。二，LoadingBalance问题的两倍贪心近似解贪心策略：总是优先给当前机器中负载最小的机器分配作业设BS(bestsolution)为LoadingBalance问题的最优解。BS表示处理完所有的作业所需的最少时间，则：1）BS>=max{t(1),t(2)……t(n)}     耗时最长的作业总会在某台机器上执行，BS一定比某个单一作业的执行时间要长（可...

参考《算法导论第二版P222页）一，如何把现实的问题转变成数学问题？即数学建模的思路？1，问题描述：现有一组相互竞争的活动，如何调度能够找出一组最大的活动（活动数目最多）使得它们相互兼容？2，问题转化：首先，按活动的结束时间单调递增进行排序。那么，为什么要按结束时间排序呢？这个问题留到后面解释。其次，定义合适的问题子空间，即定义集合S(i,j)。问题子空间描述的是现实生活中的问题，而集合S(i,j)则是数学概念，通过某种方式定义一个合适的集合将问题子空间的解转化为集合的解（即求出集合中符合某种条件的所有元素）。3，那么问题来了，怎样才能让定义的这个集合问题能够描述现实问题呢？----a，将S(i,j)中元素表示成与活动a(i)、a(j)兼容的活动b，将活动a(1)、a(2)……a(i)、a(i+1)、……a(j)、a(j+1)……a(n)按照结束时间单调递增排序！每个集合元素有一个特征：有开始时间和结束时间。这就是为什么要按结束时间单调递增排序的原因，因为只有这样，才能够成功的建模，将现实问题转化成数学...

1，对元素进行排列时，元素之间需要进行比较，因此需要实现Comparable<T>接口。即，<TextendsComparable<T>>.更进一步，如果允许待比较的类型可以和它的父类型进行比较，则需要写成：<TextendsComparable<?superT>，其中<?superT>表示T的任意超类。2，InsertionSortArray.java类实现了从小到大顺序以插入排序的方式对数据进行排序。3，insertionSort方法负责对每一个元素进行排序，insertInOrder方法将待排序的元素插入到合适的位置，相当于执行具体的操作。具体代码如下：publicclassInsertionSortArray{publicstatic<TextendsComparable<?superT>>voidinsertSort(T[]a,intn){insertionSort(a,0,n-1);//对序列a进行排序，其起始索引为0，最后元素的索引为n-1}//从索引first到last执行插入排序...

1，采用选择排序对元素进行排列时，元素之间需要进行比较，因此需要实现Comparable<T>接口。即，<TextendsComparable<T>>.更进一步，如果允许待比较的类型可以和它的父类型进行比较，则需要写成：<TextendsComparable<?superT>，其中<?superT>表示T的任意超类。2，SelectionSortArray.java实现了选择排序的迭代形式和递归形式。具体代码如下：publicclassSelectionSortArray{/**Task:将数组中前n个对象按升序排列*@paramaComparable对象的数组*@paramn大于0的整数，表示数组的长度*/publicstatic<TextendsComparable<?superT>>voidselectionSort(T[]a,intn){for(intindex=0;index<n-1;index++){intindexOfNextSmallest=getIndexOfSmalles...

 162:PostOffice解题思路#include<bits/stdc++.h>usingnamespacestd;intn,m,a[1001],f[500][500],mi[500][500],i,j;intmain(){cin>>n>>m;for(i=1;i<=n;i++)cin>>a[i];for(i=1;i<=n;i++)for(j=1;j<=m;j++)f[i][j]=9999999;//赋为最大值for(i=1;i<=n;i++){for(j=i+1;j<=n;j++)mi[i][j]=mi[i][j-1]+a[j]-a[(i+j)/2];//从第i个村庄到第j个村庄中只建一个邮局的总路径长度f[i][1]=mi[1][i];//转移到f}for(i=2;i<=n;i++)for(j=2;j<=m;j++)for(intk=j-1;k<i;k++)f[i][j]=min(f[i][j],f[k][j-1]+mi[k+1][i]);cout<<f[n][m...

AC代码#include<iostream>usingnamespacestd;inta[100];intn,c1=0,c5=0,c10=0;intmain(){cin>>n;for(inti=0;i<n;i++){cin>>a[i];if(a[i]==1)c1++;if(a[i]==5)c5++;if(a[i]==10)c10++;}cout<<c1<<endl;cout<<c5<<endl;cout<<c10<<endl;return0;}AC代码#include<iostream>usingnamespacestd;intmain(){chars[205];gets(s);intb=0;for(inti=0;s[i]!=0;i++){if(s[i]==''){if(b==0)cout<<'';b=1;}else{cout<<s[i];b=0;}}cout<<endl;return0;}AC代码#include<cs...